All Questions
Tagged with enumeration combinatorics
12 questions
5
votes
0
answers
93
views
Rank and unrank for Heap's Algorithm
I am looking for an unranking (and ranking) algorithm for permtuations that is consistent with the order that Heap's Algorithm generates permutations.
I have been researching a bit on ranking and ...
- 151
2
votes
1
answer
58
views
Looking for all "valid" combinations taken from a set of things, where subsets of "valid" things are always "valid"
I have a problem where I need to find all subsets of a set that satisfy some validity function. The function has the property that if a subset is invalid, so are all its supersets, and if a subset is ...
- 919
1
vote
1
answer
177
views
Iterating over combinations of 4 timestamps from 2 timelines *efficiently*
I need help in finding a more performant algorithm.
I have two timelines in the form of two indexed lists where each element is a floating-point value that represents seconds. The values in each list ...
- 11
0
votes
0
answers
85
views
How can I generate all combinations of 2 sets of unique numbers? How are those called?
I want to generate 2 sets from N elements.
Sets must be unique in the combination of sets
Numbers must not repeat across the 2 sets
Sets can have any amount of numbers, but must not be empty
...
- 101
1
vote
0
answers
44
views
What do you call a greedy algorithm that solves a combinatorial problem by optimizing the best k>1 choices altogether?
Suppose you have a problem which goal is to find the permutation of some set $S$ given in input that minimizes an objective function $f$ (for example the Traveling Salesman problem).
A trivial ...
- 623
2
votes
2
answers
131
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 is ordered ...
- 145
0
votes
1
answer
68
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 ...
- 21
3
votes
1
answer
651
views
Counting Colorings of a Grid
Given a $n \times m$ grid, define a valid coloring as mapping from the grid cells to a set of $k$ available colors such that no two adjacent cells have the same color. Cells are considered as adjacent ...
- 389
2
votes
2
answers
769
views
Enumerate partitions of a set with blocks of equal size
Given a set $\{1,\ldots,ck\}$, is there a known algorithm to efficiently list all partitions in with $c$ blocks of cardinality $k$?
In The art of computer programming (Fascicle 3B) by Knuth, there's ...
- 155
0
votes
4
answers
1k
views
Is it feasible to generate every possible RGB image?
This topic is normally brought up in computer science as a demonstration of how to calculate permutations but it stops there since we usually end up calculating that there are more images of a decent ...
- 168
6
votes
1
answer
88
views
Distribution of the number of bits changed during generation of all binary tuples
Knuth's TAOCP chapter 7.2.1 discusses generating all the $n$-bit binary strings.
I am interested in the total number of bits that change during this process.
During generation we store an $n$-bit ...
- 3,512
1
vote
1
answer
1k
views
How to enumerate all combinations of $n$ binary variables s.t. their sum is $k$?
Suppose we are given $n$ variables $X_i, i=1,\dots,n$, each taking values from $\{0,1\}$, and a constant integer $k$ with $ 0\leq k \leq n$.
What are some efficient ways to enumerate all possible ...
- 5,015