5

我有一个包含 N 个项目的列表，我想知道如何遍历列表以获取每个组合。没有双打，所以我需要得到所有的N！订货。额外的内存没问题，我正在尝试最简单的算法，但我遇到了麻烦。

4

5 回答 5

15

见std::next_permutation   

于 2010-01-26T19:19:19.480 回答
8

扩展其他人的答案，这是改编自cplusplus.com的 std::next_permutation 示例

#include <iostream>
#include <algorithm>
using namespace std;

void outputArray(int* array, int size)
{
  for (int i = 0; i < size; ++i) { cout << array[i] << " "; }
}

int main ()
{
  int myints[] = { 1, 2, 3, 4, 5 };
  const int size = sizeof(myints);

  cout << "The 5! possible permutations with 5 elements:\n";

  sort (myints, myints + size);

  bool hasMorePermutations = true;
  do
  {
    outputArray(myints, size);
    hasMorePermutations = next_permutation(myints, myints + size);
  }
  while (hasMorePermutations);

  return 0;
}
于 2010-01-26T19:36:21.993 回答
2

为此，C++ STL 具有next_permutation 。

于 2010-01-26T19:21:04.383 回答
0

使用递归的简单算法：

伪码

getPermutations(CurItemList , CurPermList)

if CurItemList.isempty()
    return CurPermList
else
    Permutations = {}

    for i = 1 to CurItemList.size() 
        CurPermList.addLast(CurItemList.get(i))

        NextItemList = CurItemList.copy()
        NextItemList.remove(i)

        Permutations.add(getPermutations(NextItemList, CurPermList))

        CurPermList.removeLast()


return Permutations

// To make it look better
Permutations(ItemList) 
    return getPermutations(ItemList, {})

我没有测试它，但应该工作。也许它不是最聪明的方法，但它是一种简单的方法。如果有什么问题请告诉我！

于 2010-01-26T20:36:05.460 回答
0

尝试使用固定数量的可能元素递归地构建组合集。所有可能组合的集合将是 1 个元素、2 个元素……最多 N 个元素的组合集合的并集。

然后你可以单独攻击每个固定大小的组合。

于 2010-01-26T22:00:49.967 回答