c# - 列出1 ... n之间的k个整数的所有可能组合(n选择k)

出于某种特殊的原因，我决定寻找一种算法，该算法可以产生1 ... n之间的k个整数的所有可能选择，其中k个整数之间的顺序无关紧要(n选择k个东西)。

出于完全相同的原因，这完全没有理由，我也用C#实现了它。我的问题是:

您在我的算法或代码中看到任何错误吗？而且，更重要的是，您可以提出更好的算法吗？

请比代码本身更注意算法。尽管可以告诉您是否看到错误，但这不是我编写过的最漂亮的代码。

编辑: Alogirthm解释了-

我们持有k个索引。

这将创建k个嵌套的for循环，其中循环i的索引是indexs [i]。

它模拟k个for循环，其中index [i + 1]属于嵌套在index [i]循环内的循环。

索引[i]从索引[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);
            }
        }
    }
}

对于这个较长的问题，我深表歉意，它可能适合写博客文章，但我确实希望在这里得到社区的意见。

谢谢，
阿萨夫

最佳答案

在C++中，给出以下例程:

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

然后，您可以继续执行以下操作:

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