C# dictionary order of combinations

Question

I need to iterate, for some values of k, on all combinations of taking k items out of a vector V containing N items. For example if N = 6 and k = 3 then I have to call F() on items V1, V2 and V[3], then on items V1, V2 and V[4], ending with V[4], V[5] and V[6].

Now, going through all combinations of the index is easy. Say k = 3 and N = 6. Then the first element can go from 1 to N-(k-1), the second from 2 to N-(k-2), the k'th from k to N (i.e. N-(k-k)).

So, for k = 3 the loop would be:

for (uint a = 1, a <=  N-2, a++)
  for (uint b = a + 1, b <= N-1, b++)
    for (uint c = b + 1, c <= N, c++)
     F(V[a], V[b], V[c])

and, for k = 4, the iteration would be:

for (uint a = 1, a <=  N-3, a++)
  for (uint b = a + 1, b <= N-2, b++)
    for (uint c = b + 1, c <= N - 1, c++)
       for (uint d = c + 1, d <= N, d++)
          F(V[a], V[b], V[c], V[d])

The question, however, is: How do you accomplish this k-level nesting for an arbitrary k without hard coding it (or using code generation)?

Edit: For background (a.k.a. THIS IS NOT HOMEWORK :)) please see Hans Engler's answer to my Math Stackexchange quesion: 0-1 knapsack like - the set of all non-contained affordable binary selections

Edit: I'll provide a sample. Suppose V= {1,2,3,4,5}.

For k=2 I want F to be called in the following order: F(1,2), F(1,3), F(1,4), F(1,5), F(2,3), F(2,4), F(2,5), F(3,4), F(3, 5) and F(4,5).

For k=3 I want F to be called in the following order: F(1,2,3), F(1,2,4), F(1,2,5), F(2,3,4,), F(2,3,5), F(3,4,5)

Answer 1

Your code samples are generating unique combinations, not permutations. Combinations are unique regardless of order. For example, if your data looks like this - 123, 231, 321 then you would be working with permutations. Combinations fall under the domain of the binomial coefficient.

I have written a class in C# to handle common functions for working with the binomial coefficient. It performs the following tasks:

1. Outputs all the K-indexes in a nice format for any N choose K to a file. The K-indexes can be substituted with more descriptive strings or letters.

2. Converts the K-indexes to the proper index of an entry in the sorted binomial coefficient table. This technique is much faster than older published techniques that rely on iteration. It does this by using a mathematical property inherent in Pascal's Triangle.

3. Converts the index in a sorted binomial coefficient table to the corresponding K-indexes. I believe it is also faster than older iterative solutions.

4. Uses Mark Dominus method to calculate the binomial coefficient, which is much less likely to overflow and works with larger numbers.

5. The class is written in .NET C# and provides a way to manage the objects related to the problem (if any) by using a generic list. The constructor of this class takes a bool value called InitTable that when true will create a generic list to hold the objects to be managed. If this value is false, then it will not create the table. The table does not need to be created in order to use the 4 above methods. Accessor methods are provided to access the table.

6. There is an associated test class which shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known bugs.

To read about this class and download the code, see Tablizing The Binomial Coeffieicent.

The following code will iterate through the set of combinations in order:

int N = 6;  // Total number of elements in the set.
int K = 3;  // Total number of elements in each group.
int[] V = new int[N]; // Holds the vector of numbers.
// Create the bin coeff object required to get all
// the combos for this N choose K combination.
BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
int[] KIndexes = new int[K];
// Loop thru all the combinations for this N choose K case.
for (int Combo = 0; Combo < NumCombos; Combo++)
{
   // Get the k-indexes for this combination.
   BC.GetKIndexes(Loop, KIndexes);
   // Do whatever processing with the V array that needs to be done.
   // Code to print the values out in C#:
   String S = V[KIndexes[0]].ToString() + ", " + V[KIndexes[1]].ToString() + ", " + 
      V[KIndexes[2]].ToString();
   Console.WriteLine(S};
}

You should be able to port this class over fairly easily to the language of your choice. You probably will not have to port over the generic part of the class to accomplish your goals. Depending on the number of combinations you are working with, you might need to use a bigger word size than 4 byte ints.

Answer 2

This does smell like Homework, which is ok, but you should indicate that it is homework.

In any case, when you see yourself diving into a series of loops without a clear end, it's likely that recursion will help. Consider the class below. I'll leave the guts of the function F() empty, but point you down a reasonable path (I think):

class Program
{
    private void F(int[] vector, int k)
    {
        if (vector.Length > 0)
        {
            // TO DO: operate on the first k elements of vector
            // Question: what conditions will throw an exception?
            Console.WriteLine("now operating on vector of length: " + vector.Length);

            // Re-define vector and re-apply F()
            vector = vector.Skip(1).Take(vector.Length - 1).ToArray();
            F(vector, k);
        }

    }


    static void Main(string[] args)
    {
        int[] vector = { 0, 1, 1, 2, 3 };
        int k = 3;

        try
        {
            Program p = new Program();
            p.F(vector, k);
        }
        catch (Exception ex)
        {

            Console.WriteLine("Unhandled exception: " + ex.Message);
            System.Environment.Exit(1);
        }
        finally
        {
            if (System.Diagnostics.Debugger.IsAttached)
            {
                Console.Write("Any key to continue...");
                Console.ReadKey();
            }
        }
    }
}