алгоритм — Создание всех возможных k комбинаций из n предметов в переполнении стека

От Розетта код

#include <algorithm>
#include <iostream>
#include <string>

void comb(int N, int K)
{
std::string bitmask(K, 1); // K leading 1's
bitmask.resize(N, 0); // N-K trailing 0's

// print integers and permute bitmask
do {
for (int i = 0; i < N; ++i) // [0..N-1] integers
{
if (bitmask[i]) std::cout << " " << i;
}
std::cout << std::endl;
} while (std::prev_permutation(bitmask.begin(), bitmask.end()));
}

int main()
{
comb(5, 3);
}

выход

 0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

Анализ и идея

Все дело в том, чтобы играть с двоичным представлением чисел
например число 7 в двоичном есть 0111

Так что это двоичное представление также можно рассматривать как список назначений в качестве таких:

За каждый бит я если бит установлен (т.е. 1) означает яЭтот пункт назначен иначе.

Затем простым вычислением списка последовательных двоичных чисел и использованием двоичного представления (которое может быть очень быстрым) дает алгоритм для вычисления всех комбинаций N над К.

сортировка в конце (некоторых реализаций) не нужно. Это просто способ детерминистически нормализовать результат, т. Е. Для одинаковых чисел (N, K) и одного и того же алгоритма. порядок комбинаций возвращается

Для дальнейшего чтения о представлениях чисел и их связи с комбинациями, перестановками, наборами мощности (и другими интересными вещами), посмотрите на Комбинаторная система счисления , Факториальная система счисления

В Python это реализовано как itertools.combination

https://docs.python.org/2/library/itertools.html#itertools.combinations

В C ++ такая комбинированная функция может быть реализована на основе функции перестановки.

Основная идея состоит в том, чтобы использовать вектор размером n и устанавливать только 1 элемент k внутри, тогда все комбинации nchoosek могут быть получены путем сбора k элементов в каждой перестановке.
Хотя это может быть не самый эффективный способ, требующий большого пространства, так как комбинация обычно очень велика. Лучше быть реализованным в виде генератора или помещать рабочие коды в do_sth ().

Пример кода:

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

int main(void) {

int n=5, k=3;

// vector<vector<int> > combinations;
vector<int> selected;
vector<int> selector(n);
fill(selector.begin(), selector.begin() + k, 1);
do {
for (int i = 0; i < n; i++) {
if (selector[i]) {
selected.push_back(i);
}
}
//     combinations.push_back(selected);
do_sth(selected);
copy(selected.begin(), selected.end(), ostream_iterator<int>(cout, " "));
cout << endl;
selected.clear();
}
while (prev_permutation(selector.begin(), selector.end()));

return 0;
}

и вывод

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

Это решение на самом деле является дубликатом с
Генерация комбинаций в с ++

Если номер набора будет в пределах 32, 64 или размера собственного примитива машины, то вы можете сделать это с помощью простой битовой манипуляции.

template<typename T>
void combo(const T& c, int k)
{
int n = c.size();
int combo = (1 << k) - 1;       // k bit sets
while (combo < 1<<n) {

pretty_print(c, combo);

int x = combo & -combo;
int y = combo + x;
int z = (combo & ~y);
combo = z / x;
combo >>= 1;
combo |= y;
}
}

этот пример вызывает функцию pretty_print () по порядку словаря.

Например. Вы хотите иметь 6C3 и предполагать, что текущая «комбинация» — 010110.
Очевидно, следующая комбо ДОЛЖНА быть 011001.
011001 это:
010000 | 001000 | 000001

010000: непрерывно удаляются 1 с стороны LSB.
001000: установите 1 на следующем из непрерывных 1 с стороны LSB.
000001: непрерывно сдвигать 1с младшего бита вправо и удалять бит бита.

int x = combo & -combo;

это получает самый низкий 1.

int y = combo + x;

это устраняет непрерывно 1 сек стороны LSB и устанавливает 1 на следующую из них (в вышеупомянутом случае, 010000 | 001000)

int z = (combo & ~y)

это дает вам непрерывные 1с стороны LSB (000110).

combo = z / x;
combo >> =1;

это для «непрерывного сдвига 1 с младшего бита вправо и удаления бита младшего бита».

Таким образом, последняя задача — ИЛИ у выше.

combo |= y;

Несколько простых конкретных примеров:

#include <bits/stdc++.h>

using namespace std;

template<typename T>
void pretty_print(const T& c, int combo)
{
int n = c.size();
for (int i = 0; i < n; ++i) {
if ((combo >> i) & 1)
cout << c[i] << ' ';
}
cout << endl;
}

template<typename T>
void combo(const T& c, int k)
{
int n = c.size();
int combo = (1 << k) - 1;       // k bit sets
while (combo < 1<<n) {

pretty_print(c, combo);

int x = combo & -combo;
int y = combo + x;
int z = (combo & ~y);
combo = z / x;
combo >>= 1;
combo |= y;
}
}

int main()
{
vector<char> c0 = {'1', '2', '3', '4', '5'};
combo(c0, 3);

vector<char> c1 = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
combo(c1, 4);
return 0;
}

результат:

1 2 3
1 2 4
1 3 4
2 3 4
1 2 5
1 3 5
2 3 5
1 4 5
2 4 5
3 4 5
a b c d
a b c e
a b d e
a c d e
b c d e
a b c f
a b d f
a c d f
b c d f
a b e f
a c e f
b c e f
a d e f
b d e f
c d e f
a b c g
a b d g
a c d g
b c d g
a b e g
a c e g
b c e g
a d e g
b d e g
c d e g
a b f g
a c f g
b c f g
a d f g
b d f g
c d f g
a e f g
b e f g
c e f g
d e f g

Я написал класс на C # для обработки общих функций для работы с биномиальным коэффициентом, который является типом проблемы, к которой относится ваша проблема. Он выполняет следующие задачи:

1. Выводит все K-индексы в хорошем формате для любого N, выбирают K в файл. K-индексы могут быть заменены более описательными строками или буквами. Этот метод делает решение этого типа проблемы довольно тривиальным.

2. Преобразует K-индексы в соответствующий индекс записи в отсортированной таблице биномиальных коэффициентов. Этот метод намного быстрее, чем старые опубликованные методы, основанные на итерации. Это делается с помощью математического свойства, присущего треугольнику Паскаля. Моя газета говорит об этом. Я считаю, что я первый, кто открыл и опубликовал эту технику.

3. Преобразует индекс в отсортированной таблице биномиальных коэффициентов в соответствующие K-индексы. Я считаю, что это также быстрее, чем другие решения.

4. Пользы Марк Доминус метод для вычисления биномиального коэффициента, который с гораздо меньшей вероятностью переполнится и работает с большими числами.

5. Класс написан на .NET C # и предоставляет способ управления объектами, связанными с проблемой (если таковые имеются), используя общий список. Конструктор этого класса принимает значение bool, называемое InitTable, которое при значении true создаст общий список для хранения управляемых объектов. Если это значение равно false, таблица не будет создана. Таблицу не нужно создавать для выполнения 4 вышеуказанных методов. Методы доступа предоставляются для доступа к таблице.

6. Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был тщательно протестирован с 2 случаями, и никаких известных ошибок нет.

Чтобы прочитать об этом классе и скачать код, см. Таблицы биномиальных коэффициентов.

Должно быть довольно просто перенести класс на C ++.

Решение вашей проблемы включает генерацию K-индексов для каждого N выбор K. Например:

int NumPeople = 10;
int N = TotalColumns;
// Loop thru all the possible groups of combinations.
for (int K = N - 1; K < N; K++)
{
// Create the bin coeff object required to get all
// the combos for this N choose K combination.
BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
int[] KIndexes = new int[K];
BC.OutputKIndexes(FileName, DispChars, "", " ", 60, false);
// Loop thru all the combinations for this N choose K case.
for (int Combo = 0; Combo < NumCombos; Combo++)
{
// Get the k-indexes for this combination, which in this case
// are the indexes to each person in the problem set.
BC.GetKIndexes(Loop, KIndexes);
// Do whatever processing that needs to be done with the indicies in KIndexes.
...
}
}

Метод OutputKIndexes также можно использовать для вывода K-индексов в файл, но он будет использовать отдельный файл для каждого случая N выбора K.

Вот алгоритм, который я придумал для решения этой проблемы. Вы должны иметь возможность изменить его для работы с вашим кодом.

void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
unsigned int n = (startNum - bitVal) << 1;
n += bitVal ? 1 : 0;

for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
cout << (n >> (i - 1) & 1);
cout << endl;

if (!(n & testNum) && n != startNum)
r_nCr(n, bitVal, testNum);

if (bitVal && bitVal < testNum)
r_nCr(startNum, bitVal >> 1, testNum);
}

Вы можете увидеть объяснение того, как это работает Вот.

Ниже приведена ссылка на общий ответ C # на эту проблему: Как отформатировать все комбинации из списка объектов. Вы можете легко ограничить результаты только длиной k.

https://stackoverflow.com/a/40417765/2613458

Это также можно сделать с помощью обратного отслеживания, поддерживая посещенный массив.

void foo(vector<vector<int> > &s,vector<int> &data,int go,int k,vector<int> &vis,int tot)
{

vis[go]=1;
data.push_back(go);
if(data.size()==k)
{
s.push_back(data);
vis[go]=0;
data.pop_back();
return;
}

for(int i=go+1;i<=tot;++i)
{
if(!vis[i])
{
foo(s,data,i,k,vis,tot);
}
}
vis[go]=0;
data.pop_back();
}vector<vector<int> > Solution::combine(int n, int k) {
vector<int> data;
vector<int> vis(n+1,0);
vector<vector<int> > sol;
for(int i=1;i<=n;++i)
{
for(int i=1;i<=n;++i) vis[i]=0;
foo(sol,data,i,k,vis,n);
}
return sol;

}