11

出于没有特别的原因，我决定寻找一种算法，该算法可以产生 1...n 之间的所有可能的 k 整数选择，其中 k 整数之间的顺序无关紧要（n 选择 k 事物）。

出于完全相同的原因，这根本不是原因，我也在 C# 中实现了它。我的问题是：

您在我的算法或代码中看到任何错误吗？而且，更重要的是，你能推荐一个更好的算法吗？

请更多地关注算法而不是代码本身。这不是我写过的最漂亮的代码，但如果你看到错误，请告诉我。

编辑： Alogirthm 解释-

  • 我们持有 k 个指数。
  • 这会创建 k 个嵌套的 for循环，其中循环 i 的索引是 indices[i]。
  • 它模拟 k for循环，其中 indices[i+1] 属于嵌套在 indices[i] 循环中的循环。
  • indices[i] 从 indices[i - 1] + 1 运行到 n - k + i + 1。

代码：

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

我为这个冗长的问题道歉，它可能适合博客文章，但我确实希望社区的意见在这里。

谢谢，
阿萨夫

4

4 回答 4

9

In C++ given the following routine:

template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Thomas Draper */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator itr1 = first;
   Iterator itr2 = last;
   ++itr1;
   if (last == itr1)
      return false;
   itr1 = last;
   --itr1;
   itr1 = k;
   --itr2;
   while (first != itr1)
   {
      if (*--itr1 < *itr2)
      {
         Iterator j = k;
         while (!(*itr1 < *j)) ++j;
         std::iter_swap(itr1,j);
         ++itr1;
         ++j;
         itr2 = k;
         std::rotate(itr1,j,last);
         while (last != j)
         {
            ++j;
            ++itr2;
         }
         std::rotate(k,itr2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

You can then proceed to do the following:

std::string s = "123456789";
std::size_t k = 3;
do
{
   std::cout << std::string(s.begin(),s.begin() + k) << std::endl;
}
while(next_combination(s.begin(),s.begin() + k,s.end()));
于 2009-10-25T20:18:09.173 回答
2

阿萨夫，

您要求我们评估您的算法，但您没有解释您的算法——甚至在代码注释中也没有。因此，您希望每个人都花一个小时或更长时间从代码中对算法进行逆向工程，这样我们才能在回答之前理解您的问题？

请编辑您的问题以解释您的算法。

有一件事是显而易见的——代码的内存占用是可怕的。即使 n 的值很小，组合的数量也很容易达到数十亿，这将需要比大多数计算机更多的内存。另外，您正在使用动态增长的数组，随着它们的增长，它们会不断重新分配和复制自己。另外，您的程序会在不同的数组中生成子集并将它们合并。总而言之，您的程序将需要许多倍于理想情况下存储列表所需的内存量，并且它将花费大部分时间来回复制数据。

如果你必须同时拥有一个数组中的所有值，至少从计算你需要的数组的大小开始——n！/（NK）！/k！——然后就填好了。

更好的是“懒惰”的代码只是根据需要计算序列的每个成员。从相关问题侧栏中查看此问题

于 2009-02-14T04:40:17.867 回答
1

这家伙似乎在使用 C# (CodeProject) 的组合学方面做了认真的工作：

使用 C# 泛型的排列、组合和变体

于 2010-03-19T16:24:03.943 回答
-1

这是我不久前用 C 语言编写的一个相对简单/高效的 nCr 程序：

main(n,k){float t=0,r=1;for(scanf("%d, %d",&n,&k);t++<k;r*=(1+n-t)/t);printf("%.0f\n",r);}

好的...可读版本。=] （不确定这是否与上述1：1对应。）

void nCr(int n, int k) {
    float curK = 0, r = 1;
    while(curK < k) {
        ++curK;
        printf("%.0f\n", r);
        r *= (1 + n - curK) / curK;
    }
}

而不是打印，你可以yield或任何东西（我不知道 C#）到你的列表中。

于 2009-02-14T04:20:59.413 回答