C++的下一个排列算法

Question

假设有一门课程有8个参与者，我必须以所有可能的方式输出前3名。 例如：

123 124 125 126 127 128 213 等等...

我知道有“下一个排列”算法，但它返回所有可能的排列，包括1到8的所有数字，但我需要包含所有参与者的前三名。

1  2  3  4  5  6  7  8  
1  2  3  4  5  6  8  7

- ddacot

---

为什么有两个127？那111呢？ - kennytm

http://msdn.microsoft.com/en-us/library/e7d3xas6.aspx - vicatcu

122是什么意思？是指第一名被Person #1获得，而第二名则由Person #2自己并列获得。 - Robᵩ

可能是n choose k实现的重复问题。 - Robᵩ

@Rob 哈哈，有些回答真的很差劲，我在你的帖子下面评论证明了这一点。 - ddacot

Answer 1

你需要的不是排列，这就是为什么单独使用next_permutation无法解决你的问题。

首先，你需要确定123和321是否相同。如果它们相同，那么你有普通的组合。如果它们不同，那么你有k-排列（与普通排列不同）。 std::next_permutation给出的是下一个排列，而不是下一个k-排列。没有std::next_combination。

幸运的是，如果你编写自己的next_combination（或在互联网上找到一个），你可以将其与std::next_permutation一起使用，轻松地表达next_k_permutation算法。

掌握正确的术语后，应该很容易找到解决方案。

- n. m.

Answer 2

这个程序可以产生你想要的输出结果，但不一定按照你期望的顺序。如果你希望按特定顺序输出，可能需要先捕获输出然后进行排序。点击这里查看运行示例。

#include <algorithm>
#include <iostream>

template <typename Iterator>
inline bool next_combination(Iterator first,
  Iterator k,
  Iterator last);

int main () {
  int array[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
  do {
    do {
       std::cout << array[0] << array[1] << array[2] << "\n";
    } while(std::next_permutation(array, array+3));
  } while(next_combination(array,array+3,array+8));
}

template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Thomas Draper */
   // https://dev59.com/Cm445IYBdhLWcg3wAFcC#5097100
   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;
}

- Robᵩ

Answer 3

我误解了你的问题。

你需要的不是 next_permutation，而是我所要称之为 next_combination。

因此，我在谷歌上搜索了这个术语… link 1 (codeproject)，link 2，link 3，link 4。

- Benoit

---

不，这并不能解决我的问题，让我给你看看124 125 126 127 128 129 134 //为什么它从134开始而不是132然后是134等等？ - ddacot

@ddacot：所以你想要每个组合的每个排列。 - Benoit

Answer 4

首先，您需要找到所有的NC3组合，然后对它们进行排列，以找到所有可能的排名方式。

N选3可以通过生成 Banker's sequence（我最喜欢的）来完成。有一种巧妙的方法可以每次使用logN复杂度生成所有NC3组合。

一旦您开始获得组合，您可以轻松地使用next_permutation()调用对所有6个排列进行排列。

- srbhkmr