Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
506
questions
0
votes
1answer
30 views
How to compute total number of subsequences of length k from a word of length N?
A subsequence of a word is obtained by dropping some letters from it. The letters
that are dropped need not be consecutive. For instance, ba, bna and banaa are all
subsequences of the word banana.
We ...
0
votes
0answers
41 views
Help with an algorithm task
I've been given a task that I had issue solving.
Problem statement:
John likes jumping so he is about to build a new jumping terrain. The
terrain consists of N blocks, and in each block he can ...
1
vote
0answers
36 views
coloring of an interval graph with constraints
Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
2
votes
1answer
23 views
Combinations and Permutations of M sets of distinct items?
I'm wokring on this problem for a while. I want to know:
The correct name of this problem, so I can look it up in textbooks\online.
Here is the problem descirption:
The (un-ordered) combinations to ...
0
votes
0answers
54 views
How to solve this dynamic programming puzzle on matrix?
We are given 4 integers N,M ,Q and Z.
Initially,the matrix has all zeroes in it.
We have to perform Q operations on the matrix.
In each operation, any cell of the matrix can be selected(same cell ...
2
votes
1answer
31 views
What is the density of a regular language $L$ over an alphabet $\Sigma$ in $\Sigma^n$?
In other words, what is the likelihood that a recognizer of a given regular language will accept a
random string of length $n$?
If there is only a single non-terminal $A$, then there are only ...
4
votes
0answers
30 views
Karger's min-cut (contraction): Combinatorial argument for success probability?
The contraction algorithm for min-cut is: pick an edge $(u,v)$ uniformly at random, and "contract" it by merging $u$ and $v$ into a single vertex, deleting self-loops. Continue until two vertices ...
1
vote
1answer
26 views
Average number of full nodes in rooted m-ary tree
I am looking for a formula to express the average number of full nodes (i.e. nodes having exactly $m$ children) in a $m$-ary tree having $n$ nodes, i.e.,
$$ \mu_{n}^{(m)} = \frac{\# \text{full nodes ...
2
votes
0answers
66 views
Set of maximum overlaps
Assume I have a list of $N$ surfaces $\{S_i\}, i \in [1,N]$ which may or may not overlap.
I also have a boolean function $F(S_{i_1},\dots,S_{i_k})$ (with $1 \le k \le N$) which tests whether all ...
0
votes
2answers
44 views
generating all pairs
suppose I have 6$\{0,1,2,3,4,5\}$ numbers.I should generate following 4 pairings of numbers where there will be 3 pairs in each pairing s.t
each number should be in one pair and also every number ...
1
vote
1answer
92 views
algorithm for number of subsequences containing at most k numbers with no element repeated in each of the subsequence
For e.g if the array is 2,2,3,3,5 and k=3
there are total 18 subequences
1 subequence of length 0(i.e empty subsequence)
5 subsequences of length 1
8 subsequences with length 2
4 subsequences with ...
2
votes
2answers
103 views
Algorithm to count the number of subsets of size k with sum of all its elements minimum possible
An array is given eg:-1 2 2 2 and we need to count the number of subsets for it of size k which has the sum of elements minimum possible
here the subsets of size k=3 are:-
122
122
122
222
we see ...
3
votes
1answer
69 views
Problem in downvote system
Problem
For my game, I'm building a system where players have power/weight, and they can downvote each other, players with 66% of downvote weight are banned. The weight of the votes is calculated ...
0
votes
0answers
41 views
Algorithm and Time Complexity for k-Sum problems
In fact, there are three different k-Sum problems:
Problem1: Given unsorted integer array $\{a_1, a_2, ..., a_n\}$ and a target number $T$, determine whether there exist at least one solution $\{a_{...
0
votes
0answers
8 views
Count compound words with an ambiguous decomposition
I have a set of words $D$, and I make compound words by concatenating a fixed number $n$ of words from $D$ (repetitions are allowed). Let's call such words $n$-compounds. I want to know how many ...
3
votes
2answers
62 views
Which order is “lexicographic order”?
To choose 3 items out of 5 items [1, 2, 3, 4, 5], Donald Knuth's lexicographic algorithm (The Art of Computer Programming, Vol 4A, 2011, p. 358, Algorithm L (...
2
votes
0answers
31 views
8-puzzle problem [duplicate]
8-puzzle problem: The puzzle consists of an area divided into a grid, 3 by 3. On each grid square is a tile, except for one square which remains empty. A tile that is next to the empty grid square can ...
1
vote
1answer
27 views
Recover boolean vector from dot products
Question:
I want to determine a boolean vector $b \in \{0,1\}^n$ consisting of zeros and ones, but cannot access it directly. I can only call a black-box computer code which will take the dot product ...
1
vote
1answer
27 views
Selecting the right partition in NAUTY
Graph isomorphism solver Nauty has two main procedures, individualization and refinement, to get to a discrete partition. During refinement procedure, we take some cell of the current partition and ...
0
votes
0answers
18 views
maximum eigenvalue across subsamples
I have an $N$-dimensional vector of data, say $X_{t}$, with $1 \leq t \leq T$.
Of this vector $X_{t}$, I want to consider sub-vectors, say $X_{t}^{b}$, which are $m$-dimensional combinations of ...
0
votes
0answers
28 views
count all possible paths of length n in an undirected graph with use of dynamic programming [duplicate]
Given is an infinitely large grid graph. Use dynamic programming to calculate the number of possible paths
of a given length n from a given start node, so that fjor every path applies:
a) no vertex ...
4
votes
2answers
66 views
Count paths of length $n$ that a player can take
I'm writing a video game, and I'm trying to find an efficient way of calculating this. The goal is to count the number of paths of length $n$ that a character can take, where the character can move ...
2
votes
1answer
57 views
Conditions for a binary tree being balanced
Prove or disprove for each of the following two properties, whether a family of trees that satisfy the property is balanced.
If you disprove, the counterexample should consist of an infinite ...
1
vote
1answer
155 views
combinatoric grouping optimization problem based on time interval overlap, weight constraint, and distance minimization
Let each element be an individual. Consider that an individual is defined such that each individual has a time range, weight, and location.
The goal is to group together individuals whose time ranges ...
5
votes
2answers
139 views
Finding row wise sum of transpose of hv-convex binary matrix
I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m).
...
2
votes
2answers
50 views
Number of possible heaps on $\{1,…,2^h-1\}$
Let $C_h$ be the number of possible heaps for the set of keys $\{1,...,2^h-1\}$. Determine a recurrence relation for $C_h$ via the substitution method and prove it.
Definition
A binary tree ...
1
vote
0answers
71 views
Tree Optimization, Combinatorics, algorithm [closed]
My Partners and me, we are trying to optimize frequency process...
I used Java to show our Problem, but the question is about algorithm NOT about Java implementation. Although implementations in java ...
2
votes
0answers
26 views
Linear order minimizing weighted distance from special element
Let's say I have a set of beads, $b_0,\dots,b_n$, and let $b_0$ be the 'special bead'. I want to lay out the beads on a string to minimize the total cost, defined as $\sum_{i=1}^n w_i \cdot d(b_0, b_i)...
1
vote
0answers
67 views
Approporiate algorithm for a graph theory problem
So I have recently ran into a graph theory problem and was unable to find a matching algorithm for the problem or reword the problem to match some existing algorithm.
The problem is pretty ...
1
vote
2answers
55 views
Maximal cliques in a multipartite graph - efficient?
I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class.
Now I am looking for the optimal subset such that each of the N classes is represented ...
0
votes
0answers
34 views
Minimum Ratio Spanning Tree
Problem statement:
Given an undirected graph $G = (V, E)$ with edge $e_i$ having two associated positive values $c_1, c_2$. Find a spanning tree $ST$ such that (ratio of the spanning tree): $$\frac{...
5
votes
0answers
51 views
Number of strings at given edit distance
I would like to know the number of strings at edit distance $n$ of a string $s$.
I guess this is textbook knowledge... but I cannot find the textbook in question.
More formally, I have an alphabet $\...
0
votes
1answer
56 views
How many possible ways to go right and up in an array
Let's say we have a 2D matrix, and we begin at $(0, 0)$.
We must travel $m$ steps to the right and $n$ steps up, in any order. Each step moves the position right or up by $1$.
For example if $n = 5$...
0
votes
1answer
53 views
Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint
I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative ...
6
votes
0answers
109 views
Algorithms to generate random nowhere-neat rectangulation?
I want to generate random rectangular partition of a given $m*n$ rectangle under the constraint that it must be nowhere-neat partition. Nowhere-neat partition means that a dissection of a rectangle ...
1
vote
1answer
102 views
How to calculate combination from given n,r and rank?
Suppose that $S=\{1,2,...,n\}$ and we are given an integer $r\leq n$.
An $r$-combination of $S$ is obtained by selecting $r$ distinct integers out of the $n$. We order all $r$-combinations for a ...
1
vote
1answer
12 views
Software metric for data growth
I'm writing a paper for some software that uses combinatorics to generate large result sets. I would like to describe that if I put in $n$ elements, I will get in return $2^n$ elements.
Is there a ...
0
votes
0answers
27 views
Handling $AND$ and $OR$ cases in MILP?
Suppose I want to have an integer program for handling the cases
$x_1>1\wedge x_2>1\wedge x_3>1\wedge\dots\wedge x_n>1\iff\delta=1$
$x_1>1\vee x_2>1\vee x_3>1\vee\dots\vee x_n&...
2
votes
1answer
61 views
Maximal size of a set of ordered words such that no pair of letters occurs twice
Consider an alphabet $\Sigma=\{1,\dots,n\}$.
An ordered word is a word $w=w_1w_2\dots w_k\in\Sigma^*$ such that $w_1<w_2<\dots<w_k$. In other words, an ordered word is a strictly increasing ...
0
votes
1answer
42 views
When do we use parallel algorithms for enumerating combinations?
I know that combination is used in many areas. But do we really need parallel version of algorithms for that? If so, where do they used?
Here is a famous example of parallel algorithms, Adaptive and ...
2
votes
1answer
125 views
Permutation of n-size array with possible repeated elements. E.g [1, 2, 1]
What would it be a recursive algorithm to get permutations for any list of n elements that might contain or not repeated elements?
For the following 3-element list ...
0
votes
1answer
40 views
invariant of bin packing
We are given an array of integers and a number K. We need to pack these integers into bins. The condition is that we have to use exactly K number of bins and each bin should have equal capacity. We ...
1
vote
1answer
75 views
Counting models satisfying a boolean formula
I'm trying to implement the #2-SAT algorithm from the paper "Counting Satisfying Assignments in 2-SAT and 3-SAT" (Dahllöf, Jonsson and Wahlström, Theor. Comput. Sci. 332(1–3):265–...
9
votes
2answers
175 views
Find an optimal ordering
I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated!
Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k} $, for example,
...
0
votes
1answer
63 views
Number of possible min heaps
The number of possible min-heaps containing each value from {1, 2, 3,
4, 5, 6, 7} exactly once is --------------
According to me, the answer should be 48. The first element 1 is fixed as root. The ...
1
vote
1answer
24 views
Minimum number of tree operations to normalize a labeled tree
Given a binary tree with labels on the leaves, like $(bc)(ad)$ or $((af)e)(c(db))$, which we can interpret as a product of terms with respect to a commutative associative operation, how many ...
3
votes
0answers
76 views
Adjacent Gray code
Gray code is permutation of $\{0,1,2,\dots,2^n-1\}$ such that each of consecutive number is differs only one bit in binary representation.
Example for $n = 3$
$000\\
001\\
011\\
010\\
110\\
111\\
...
3
votes
1answer
54 views
Sampling numbers from a weighted set that sum to constant value
So I have a multi-set of positive integers $S = \{n_1, n_2, \dots\}$ with associated weights $W = \{w_1, w_2, \dots\}$. I want to sample some numbers, without replacement, from $S$ according to ...
2
votes
2answers
163 views
Efficient n-choose-k random sampling
Is there an efficient method of sampling an n-choose-k combination at random (with uniform probability, for example)?
I have read this question but it asks for generations of all combinations, not ...
1
vote
1answer
71 views
Placing items into compatible bucket types to find an optimal total value
Suppose we have a list of buckets, each with a unique type and a maximum capaciy. We also have a list of items, each with a value and a list of compatible bucket types. An item is compatible with a ...
