5

N 個のアイテムのリストがあり、リストをループしてすべての組み合わせを取得する方法を考えています。double がないので、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

可能な要素の数を固定して、組み合わせのセットを再帰的に構築してみてください。すべての可能な組み合わせのセットは、1 つの要素、2 つの要素、... 最大 N 個の要素の組み合わせのセットの和集合になります。

次に、各固定サイズの組み合わせを個別に攻撃できます。

于 2010-01-26T22:00:49.967 に答える
0

Simple algorithm using Recursion:

PSEUDOCODE

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, {})

I didnt test it, but should work. Maybe its not the smartest way to do it, but its an easy way. If something is wrong please let me know!

于 2010-01-26T20:36:05.460 に答える