List all possible combinations of k integers between 1...n (n choose k)

Question

Out of no particular reason I decided to look for an algorithm that produces all possible choices of k integers between 1...n, where the order amongst the k integer doesn't matter (the n choose k thingy).

From the exact same reason, which is no reason at all, I also implemented it in C#. My question is:

Do you see any mistake in my algorithm or code? And, more importantly, can you suggest a better algorithm?

Please pay more attention to the algorithm than the code itself. It's not the prettiest code I've ever written, although do tell if you see an error.

EDIT: Alogirthm explained -

• We hold k indices.
• This creates k nested for loops, where loop i's index is indices[i].
• It simulates k for loops where indices[i+1] belongs to a loop nested within the loop of indices[i].
• indices[i] runs from indices[i - 1] + 1 to n - k + i + 1.

CODE:

public class AllPossibleCombination
{
    int n, k;
    int[] indices;
    List<int[]> combinations = null;

    public AllPossibleCombination(int n_, int k_)
    {
        if (n_ <= 0)
        {
            throw new ArgumentException("n_ must be in N+");
        }
        if (k_ <= 0)
        {
            throw new ArgumentException("k_ must be in N+");
        }
        if (k_ > n_)
        {
            throw new ArgumentException("k_ can be at most n_");
        }

        n = n_;
        k = k_;
        indices = new int[k];
        indices[0] = 1;
    }

    /// <summary>
    /// Returns all possible k combination of 0..n-1
    /// </summary>
    /// <returns></returns>
    public List<int[]> GetCombinations()
    {
        if (combinations == null)
        {
            combinations = new List<int[]>();
            Iterate(0);
        }
        return combinations;
    }

    private void Iterate(int ii)
    {
        //
        // Initialize
        //
        if (ii > 0)
        {
            indices[ii] = indices[ii - 1] + 1;
        }

        for (; indices[ii] <= (n - k + ii + 1); indices[ii]++)
        {
            if (ii < k - 1)
            {
                Iterate(ii + 1);
            }
            else
            {
                int[] combination = new int[k];
                indices.CopyTo(combination, 0);
                combinations.Add(combination);
            }
        }
    }
}

I apologize for the long question, it might be fit for a blog post, but I do want the community's opinion here.

Thanks,
Asaf

Solution 1

Asaf,

You are asking us to evaluate your algorithm, but you don't explain your algorithm -- not even in code comments. So you want everyone to spend an hour or more reverse engineering the algorithm from the code, just so we can understand your question before we answer it?

Please edit your question to explain your algorithm.

One thing is obvious -- the memory footprint of your code is horrendous. For even modest values of n, the number of combinatations will easily be in the billions, which will require more memory than most computers have. Plus you are using dynamically grown arrays, which keep reallocating and copying themselves as they grow. Plus your program generates subsets in different arrays and merges them. All in all, your program will require many times the amount of memory that would be ideally needed to store the list, and it will spend most of it's time just copying data back and forth.

If you must have all the values in an array at once, at least start off by computing the size of the array you need -- n! / (n-k)! / k! -- and then just filling it in.

Even better would be code that "lazily" just computed each member of the sequence as it was needed. See this question from the related questions sidebar

Solution 2

This guy seems to have done serious work in combinatorics using C# (CodeProject) :

Permutations, Combinations, and Variations using C# Generics

Comments

[sidgeon smythe]

Duplicate of stackoverflow.com/questions/127704/…

[Asaf R]

You're right on both - the footprint and explaining the algorithm. I don't mind the first as I wrote this for pure fun. I edited to add an explanation.

[Asaf R]

As I understand it, this code prints the amount of possible combinations (aka nCr) for each r up to k. I fail to see how to change it to print every combination, without ending up to something similar to my algorithm (k nested for loops). Can you please elaborate on this?