List all possible combinations of k integers between 1...n (n choose k)
- by Asaf R
Hi,
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
