Find the index of a specific combination without generating all ncr combinations

2
votes

I am trying to find the index of a specific combination without generating the actual list of all possible combinations. For ex: 2 number combinations from 1 to 5 produces, 1,2;1,3,1,4,1,5;2,3,2,4,2,5..so..on. Each combination has its own index starting with zero,if my guess is right. I want to find that index without generating the all possible combination for a given combination. I am writing in C# but my code generates all possible combinations on fly. This would be expensive if n and r are like 80 and 9 and i even can't enumerate the actual range. Is there any possible way to find the index without producing the actual combination for that particular index

public int GetIndex(T[] combination)
                    {
                        int index = (from i in Enumerable.Range(0, 9)
                                      where AreEquivalentArray(GetCombination(i), combination)
                                      select i).SingleOrDefault();

                        return index;

                    }
1
c#-4.0ienumerablecombinations

1 Answers

1
votes

I found the answer to my own question in simple terms. It is very simple but seems to be effective in my situation.The choose method is brought from other site though which generates the combinations count for n items chosen r:

public long GetIndex(T[] combinations)
        {
            long sum = Choose(items.Count(),atATime);
            for (int i = 0; i < combinations.Count(); i++)
            {
                sum = sum - Choose(items.ToList().IndexOf(items.Max())+1 - (items.ToList().IndexOf(combinations[i])+1), atATime - i);
            }

            return sum-1;

        }
private long Choose(int n, int k)
        {
            long result = 0;
            int delta;
            int max;
            if (n < 0 || k < 0)
            {
                throw new ArgumentOutOfRangeException("Invalid negative parameter in Choose()");
            }
            if (n < k)
            {
                result = 0;
            }
            else if (n == k)
            {
                result = 1;
            }
            else
            {
                if (k < n - k)
                {
                    delta = n - k;
                    max = k;
                }
                else
                {
                    delta = k;
                    max = n - k;
                }
                result = delta + 1;
                for (int i = 2; i <= max; i++)
                {
                    checked
                    {
                        result = (result * (delta + i)) / i;
                    }
                }
            }
            return result;
        }