2

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

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

                        return index;

                    }
4

1 回答 1

1

我用简单的语言找到了我自己问题的答案。这很简单，但在我的情况下似乎很有效。虽然选择方法是从其他站点带来的，但它会为选择的 n 个项目生成组合计数 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;
        }
于 2013-04-05T17:12:24.940 回答