7

Python で記述されたスニペットを C++ に移植する必要がありますが、そのスニペットは Python の itertools の組み合わせを使用しています。

私が C++ に移植することに本当に興味を持っているのは、次の行です。

for k in combinations(range(n-i),2*i):

range(n-i)Pythonでは、からリストを生成します0 to (n-i) - 1

n = 16、i = 5 とする

print range(n-i)

出力:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

および python の組み合わせは、そのリスト内のすべての可能な組み合わせを生成します。

例えば

print list(combinations(range(n-i),2*i))

出力:

[(0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
(0, 1, 2, 3, 4, 5, 6, 7, 8, 10),
(0, 1, 2, 3, 4, 5, 6, 7, 9, 10),
(0, 1, 2, 3, 4, 5, 6, 8, 9, 10),
(0, 1, 2, 3, 4, 5, 7, 8, 9, 10),
(0, 1, 2, 3, 4, 6, 7, 8, 9, 10),
(0, 1, 2, 3, 5, 6, 7, 8, 9, 10),
(0, 1, 2, 4, 5, 6, 7, 8, 9, 10),
(0, 1, 3, 4, 5, 6, 7, 8, 9, 10),
(0, 2, 3, 4, 5, 6, 7, 8, 9, 10),
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)]

std::vectorC++ を使用して、およびC++ から同様の出力を生成したいのですnext_permutationが、それでも間違った結果が得られます。これは私の現在のアプローチです：

for(int j = 0; j < n-i; j++) {
        temp_vector.push_back(j); 
}

range(n-i)そのスニペットはPythonと同等です。

しかし、次のスニペット:

do {
     myvector.push_back(temp_vector);
} while(next_permutation(temp_vector.begin(),temp_vector.begin()+2*i));
cout<<myvector.size()<<endl;

は Python と同等ではありませんcombinations(range(n-i),2*i))。さまざまなバリエーションを試しましたが、期待どおりの結果が得られませんでした。

例えば：

n = 16 i = 5 とする

パイソン

>>> print len(list(combinations(range(n-i),2*i)))

11

C++

#include <vector>
#include <iostream>

using namespace std;
int main() {
    vector<int> temp_vector;
    vector< vector<int> > myvector;
    int n = 16, i = 5;
    for(int j = 0; j < n - i; j++) {
            temp_vector.push_back(j);
    }
    do {
            myvector.push_back(temp_vector);
    } while(next_permutation(temp_vector.begin(), temp_vector.begin()+2*i));
    cout<<myvector.size()<<endl;
    return 0;
}

g++ combinations.cpp

./a.out

3628800

どんなガイダンスも大歓迎です！どうもありがとう！

4

1 に答える 1

4

組み合わせと順列は同じものではありません。

組み合わせは、別のセットのアイテムのサブセットの順序付けられていないリストです。順列は、リスト内のアイテムの一意の順序です。

11 個のもののリストから 10 個のもののすべての組み合わせを生成しているので、11 個の結果が得られ、それぞれが元の 11 個のアイテムの異なる 1 個を欠いています。

すべての順列を生成すると、元の 11 項目の一意の順序がすべて生成されます。この場合の項目はすべて一意であるため、結果は 11 になります。それぞれが 11 項目すべてを含むリスト。ただし、順列は最初の 10 個のアイテムからしか生成していないため、10 個を取得しています! 11 番目の項目を含むリストはありません。

順列ではなく組み合わせを生成するアルゴリズムを見つける必要があります。

組み合わせ用の組み込みアルゴリズムはありません。std::next_permutation は、組み合わせを生成するアルゴリズムの一部として使用できます: C++ での組み合わせの生成 を参照してください。

これは、コードを含む、組み合わせのアルゴリズムの古い草案です。

于 2012-11-16T19:57:08.740 に答える