-2
$\begingroup$

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]
Had to adjust for 0 based arrays

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;
        }
    }
}
$\endgroup$

closed as unclear what you're asking by Yuval Filmus, Evil, David Richerby, Gilles Aug 2 '17 at 13:01

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ This is a question statement showing absolutely no effort. $\endgroup$ – Yuval Filmus Jul 25 '17 at 19:49
  • $\begingroup$ @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. $\endgroup$ – paparazzo Jul 25 '17 at 19:52
  • $\begingroup$ There's a related question with a discussion of Cover's enumerative coding algorithm here: cs.stackexchange.com/questions/67664/… $\endgroup$ – Pseudonym Jul 25 '17 at 23:45
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Jul 28 '17 at 15:08
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Aug 2 '17 at 11:56
1
$\begingroup$

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

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.

Again, the algorithm can be made iterative, and Knuth (same place) has even more information.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.