查找特定组合的索引，而不生成所有ncr组合 [英] Find the index of a specific combination without generating all ncr combinations

问题描述

我正在尝试查找特定组合的索引，而不生成所有可能组合的实际列表.例如:从1到5的2个数字组合产生1,2; 1,3,1,4,1,5; 2,3,2,4,2,5..so.on.如果我的猜测是正确的话，每个组合都有从零开始的索引.我想找到该索引，而不生成给定组合的所有可能组合.我正在用C#编写代码，但是我的代码会即时生成所有可能的组合.如果n和r分别为80和9，而我什至无法枚举实际范围，这将是昂贵的.有没有可能找到该索引的方法，而不产生该特定索引的实际组合

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;

                    }

推荐答案

我用简单的术语找到了自己问题的答案.这很简单，但在我的情况下似乎很有效.select方法是从其他站点引入的，尽管它会为n个选定的r生成组合计数:

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;
        }

这篇关于查找特定组合的索引，而不生成所有ncr组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！