c++ next_permutation算法

Question

比方说，一个有8个参与者的课程，我必须以所有可能的方式输出前3个位置。例如：

123 124 125 126 127 128 213等等..

我知道有next_permutation算法，但它返回所有可能的排列和所有数字(从1到8)，但我需要所有参与者的前3位ex：

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

Answer 1

这个程序产生你想要的输出，不一定是你想要的顺序。如果您希望它按特定顺序排列，则可能需要捕获输出并对其进行排序。要查看它的运行情况，look here。

#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 */
   // http://stackoverflow.com/a/5097100/8747
   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;
}

Answer 2

您所追求的东西不是排列，这就是仅靠next_permutation不能解决您的问题的原因。

首先，您需要确定123是否与321相同。如果它们是相同的，那么你就有了普通的combinations。如果它们不同，那么就是k-permutations (不同于普通的排列)。

std::next_permutation给你下一个排列，而不是下一个k-排列。这里没有std::next_combination。

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

有了正确的术语，应该很容易找到解决方案。

Answer 3

我误解了你的问题。

你想要的不是next_permutation，而是我称之为next_combination的东西。

所以，我在谷歌上搜索了这个术语和…link 1 (代码项目)、link 2、link 3、link 4。