Find all the variations of K elements from a set of n

Question

I am stuck with this problem of trying to generate all the variations of K elements from the set [1..N]. I also had an idea that I can do that with k levels of nested loops and tried to do that recursively, but without success.

I have this function:

public static void PrintVariation(int n, int k, int[] array) 
{ 
   //when k = 2 

   for (int i = 0; i < n; i++) 
   { 
      for (int j = 0; j < n; j++) 
      { 
         Console.WriteLine("{0}, {1}", array[i], array[j]); 
      } 
   } 
}

But what am I supposed to do when k has a random value?

The same problem in [python](http://stackoverflow.com/questions/8683092/calculating-combinations-of-length-k-from-a-list-of-length-n-using-recursion). — Daniel Fischer, Jan 03 '12 at 14:26
You can read some interesting ideas here: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n — zmbq, Jan 03 '12 at 14:44
For any K, *recursion* comes handy, instead of nesting loops in a non-recursive function. See my answer and try to use that recursively. — JOG, Jan 04 '12 at 13:44

JOG · Answer 1 · 2012-01-04T13:50:16.760

0

Here is my hint: I think you are on the right track using recursion.

private List<Element[]> getVariations(int k, Element[] elements)
{
    // ... ^_^
    // use getVariations with less elements in here
}

edited Jan 04 '12 at 13:50

answered Jan 03 '12 at 14:34

JOG

5,590
7
34
54

1

Hmm, a hint with lots of `[]` while we have those handy `<>` – H H Jan 03 '12 at 14:46
`<>` it is then. This is just a hint. ^^ – JOG Jan 03 '12 at 15:08

score 0 · Answer 2 · edited Sep 01 '17 at 10:02

0

I'm not sure I follow you though, but this is what I think you should do:

Create a function that will 'generate a variation of K elements from the set [1..N]' It should return that variation.
Call that function in a for-loop in another method that would add it to a generic collection. You may add another routine that would check if the variation generated by the function already exists in the collection and skip adding that variation to the collection.

edited Sep 01 '17 at 10:02

Paolo Forgia

6,572
8
46
58

answered Jan 03 '12 at 14:49

Kristianne Nerona

755
9
24

i have this function: public static void PrintVariation(int n, int k, int[] array) { //when k = 2 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { Console.WriteLine("{0}, {1}", array[i], array[j]); } } } but what i suppose to do when k has a random value ?? – user1127964 Jan 03 '12 at 15:15

score -1 · Answer 3 · answered Jan 03 '12 at 15:21

public static List<List<T>> GetVariations<T>(int k, List<T> elements)
{
    List<List<T>> result = new List<List<T>>();
    if (k == 1)
    {
        result.AddRange(elements.Select(element => new List<T>() { element }));
    }
    else
    {
        foreach (T element in elements)
        {
            List<T> subelements = elements.Where(e => !e.Equals(element)).ToList();
            List<List<T>> subvariations = GetVariations(k - 1, subelements);
            foreach (List<T> subvariation in subvariations)
            {
                subvariation.Add(element);
                result.Add(subvariation);
            }
        }
     }
     return result;
 }

Find all the variations of K elements from a set of n

3 Answers3