Попытка симулировать комбинации Python в C ++ с помощью next_permutation

Мне нужно портировать фрагмент, написанный на Python, на C ++
но этот фрагмент использует комбинации из itertools в python.

Строка, которую я действительно заинтересован в портировании на 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::vector а также next_permutation из C ++, но я все еще получаю ошибочные результаты. Это мой текущий подход:

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;

Не эквивалентно combinations(range(n-i),2*i)) в Python, и я пробовал много вариантов, и до сих пор не смог придумать результаты, которые я ожидаю.

Например:

Пусть n = 16
я = 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

Любое руководство будет с благодарностью! Большое спасибо!

3

Решение

комбинации и перестановки — это не одно и то же.

Комбинация — это неупорядоченный список подмножества элементов из другого набора. Перестановка — это уникальный порядок элементов в списке.

Вы генерируете все комбинации из 10 вещей из списка из 11 вещей, так что вы получите 11 результатов, в каждом из которых отсутствует один из исходных 11 предметов.

Генерация каждой перестановки будет генерировать каждый уникальный порядок оригинальных 11 предметов. Поскольку все элементы в этом случае уникальны, это значит, что результат будет 11! списки, где каждый содержит все 11 предметов. Однако вы генерируете перестановки только из первых 10 элементов, поэтому вы получаете 10! списки, ни один из которых не содержит 11-й пункт.

Вам нужно найти алгоритм генерации комбинаций вместо перестановок.


Там нет встроенного алгоритма для комбинаций. std :: next_permutation может использоваться как часть алгоритма для генерации комбинаций: см. Генерация комбинаций в с ++.

Вот старый проект предложения по алгоритмам для комбинаций, включая код.

4

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]