# Combination generator - sets of size k from n [closed]

unique numbers $1 - n$
combinations (sets) of size $k$
$k < n$

do not re-use an $n$ in a set [1, 1, 1] is not valid

How to generate all unique sets of size $k$?
[1,2,3] = [3,2,1] order does not matter

the number of sets will be ${\binom{n}{k}}$

input
$n = 4, k = 2$
output
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

I have found that is often called n chose k

hard coded it looks like

for (i = i; i <= n - 1; i++)
for (j = i + 1; j <= n - 1; j++)


I tried coding the first solution from Yuval Filmus but it does not work for me
It returns [1,2], [1,2]

public static void Combinations(int n, int k)
{
bool[] A = new bool[n];
int[] B = Enumerable.Range(1, k).ToArray();
Generate(1, A, B, k, n);
}
public static void Generate(int l, bool[] A, int[] B, int k, int n)
{
Debug.WriteLine(string.Join(", ", B));
if (l == k + 1)
{
Debug.WriteLine("l == k + 1");
return;
}

for (int i = 0; i < n; i++)
{
if (!A[i])
{
A[i] = true;
B[l - 1] = i + 1;
Generate(l + 1, A, B, k, n);
A[i] = false;
}
}
}

• This is a question statement showing absolutely no effort. Jul 25 '17 at 19:49
• @YuvalFilmus I can make it work if I hard code the loops for k. I have been working on it. It is a much harder problem than I thought it would be. I found one article but it had a notation I could not understand. An ugly way to is generate and sort the k and only take unique. I want to do better but cannot figure it out. Jul 25 '17 at 19:52
• There's a related question with a discussion of Cover's enumerative coding algorithm here: cs.stackexchange.com/questions/67664/… Jul 25 '17 at 23:45
• Please clarify (with attribution) what the problem statement is, and what your approach. Please try to explain your algorithmic idea in words as well, and ask a question. It should also go in the title.
– Raphael
Jul 28 '17 at 15:08
• I made an objectively correct factual statement, answering your direct question. There is literally no question in your post. It is unclear what you are asking because you literally have not asked anything. Your (repeatedly) expressed opinion of me is inappropriate and irrelevant. Aug 2 '17 at 11:56

Here is a recursive solution in python:

n, k = 4, 2

def dfs(A, start):
if len(A) == k:
print(A)

for i in range(start, n + 1):
A.append(i)
dfs(A, i + 1)
A.pop()

dfs([], 1)

• Unfortunately I don't know python. I know C# and can usually figure out Java. Jul 25 '17 at 20:10
• Perhaps you can convert your code to pseudocode? Not everybody knows what range, append, pop and other elements of python are. Jul 25 '17 at 20:25
• Code-only answers are generally discouraged here, be it pseudo or real code. What is the idea? Why do you think it's correct?
– Raphael
Jul 28 '17 at 15:09

## Ordered combinations

Here is a simple recursive routine, which has access to a Boolean array $A$ of length $n$, whose initial entries have the value false, and to an integer array $B$ of length $k$. The routine is called with $\ell = 1$.

Generate($\ell$):

• If $\ell=k+1$, output $B$, and exit the current recursive call.
• Go over elements $i$ from $1$ to $n$:
• If $A[i]$ is false:
• Set $A[i]$ to true.
• Set $B[\ell]$ to $i$.
• Call Generate($\ell+1$).
• Set $A[i]$ to false.

The array $B$ consists of the current tuple, and the array $A$ keeps track of which elements are currently used (this is an optimization, since the information can be gleaned from $k$).

It is possible to convert this algorithm to an iterative one, and to improve its complexity for large $k$ (in particular, for the extreme case $k=n$). Take a look at Section 7.2 of Volume 4A of Knuth's Art of Computer Programming (see here for table of contents).

## Unordered combinations

These are somewhat simpler, since we don't need the array $A$. The recursive routine is called with $\ell=1$:

Generate($\ell$):

• If $\ell = k+1$, output $B$, and exit the current recursive call.
• If $\ell = 1$, set $\max$ to 0, otherwise set $\max$ to $B[\ell-1]$.
• Go over all elements $i$ from $\max+1$ to $n-(k-\ell)$:
• Set $B[\ell]$ to $i$.
• Call Generate($\ell+1$).

This generates unordered combinations (like you asked in the question), each of them itself ordered. In the code, $\max$ is just the maximum element in the current tuple. You can also pass it as a parameter as in bstrauch24's answer.

• Thanks I kind of follow. It looks like I would exit after generating the first set. I guess I will start there. Jul 25 '17 at 20:09
• It's a return statement (in C parlance). It only exits the current call. Try programming it in your favorite programming language. Jul 25 '17 at 20:10
• I know this is not a coding site but I could not make it work. Thanks Jul 25 '17 at 21:33
• Need to exit with ℓ=k+1 or get an index out of bounds exception. Jul 26 '17 at 0:14
• @Paparazzi That's what I'm doing. I changed the wording since it seemed to have been confusing. Jul 26 '17 at 1:15