Есть n людей, пронумерованных от 1 до n. Я должен написать код, который производит и печатает все различные комбинации k людей из этих n. Пожалуйста, объясните используемый алгоритм.
Создавая все возможные k комбинаций n элементов в С++
Ответ 1
Я предполагаю, что вы спрашиваете о комбинациях в комбинаторном смысле (то есть порядок элементов не имеет значения, поэтому [1 2 3] совпадает с [2 1 3]). Идея довольно проста, если вы понимаете индукцию/рекурсию: чтобы получить все комбинации K -element, вы сначала выбираете исходный элемент комбинации из существующего набора людей, а затем вы "объединяете" этот начальный элемент со всеми возможные комбинации K-1 людей, созданных из элементов, которые преуспевают в исходном элементе.
В качестве примера предположим, что мы хотим взять все комбинации из 3 человек из набора из 5 человек. Тогда все возможные комбинации из 3 человек могут быть выражены в терминах всех возможных комбинаций из 2 человек:
comb({ 1 2 3 4 5 }, 3) =
{ 1, comb({ 2 3 4 5 }, 2) } and
{ 2, comb({ 3 4 5 }, 2) } and
{ 3, comb({ 4 5 }, 2) }
Здесь код С++, который реализует эту идею:
#include <iostream>
#include <vector>
using namespace std;
vector<int> people;
vector<int> combination;
void pretty_print(const vector<int>& v) {
static int count = 0;
cout << "combination no " << (++count) << ": [ ";
for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; }
cout << "] " << endl;
}
void go(int offset, int k) {
if (k == 0) {
pretty_print(combination);
return;
}
for (int i = offset; i <= people.size() - k; ++i) {
combination.push_back(people[i]);
go(i+1, k-1);
combination.pop_back();
}
}
int main() {
int n = 5, k = 3;
for (int i = 0; i < n; ++i) { people.push_back(i+1); }
go(0, k);
return 0;
}
И вот вывод для N = 5, K = 3:
combination no 1: [ 1 2 3 ]
combination no 2: [ 1 2 4 ]
combination no 3: [ 1 2 5 ]
combination no 4: [ 1 3 4 ]
combination no 5: [ 1 3 5 ]
combination no 6: [ 1 4 5 ]
combination no 7: [ 2 3 4 ]
combination no 8: [ 2 3 5 ]
combination no 9: [ 2 4 5 ]
combination no 10: [ 3 4 5 ]
Ответ 2
От код Rosetta
#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
Итак, это двоичное представление также можно рассматривать как список назначений как таковой:
Для каждого бита i, если бит установлен (т.е. 1), означает, что i -й элемент назначается иначе.
Затем, просто вычисляя список последовательных двоичных чисел и используя двоичное представление (которое может быть очень быстрым), дает алгоритм вычисления всех комбинаций N над k.
сортировка в конце (некоторых реализаций) не требуется. Это просто способ детерминированности нормализовать результат, т.е. Для тех же чисел (N, K) и того же алгоритма возвращается тот же порядок комбинаций
Для дальнейшего ознакомления с численными представлениями и их отношением к комбинациям, перестановкам, силовым наборам (и другим интересным материалам) взгляните на комбинаторную систему чисел, Система факториальных номеров
Ответ 3
В Python это реализовано как itertools.combinations
https://docs.python.org/2/library/itertools.html#itertools.combinations
В С++ такая комбинационная функция может быть реализована на основе функции перестановки.
Основная идея состоит в том, чтобы использовать вектор размера n и установить только k item to 1 внутри, тогда все комбинации 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
Это решение на самом деле является дубликатом с Создание комбинаций в С++
Ответ 4
Вот алгоритм, который я придумал для решения этой проблемы. Вы должны иметь возможность модифицировать его для работы с вашим кодом.
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);
}
Вы можете увидеть, как это работает здесь.
Ответ 5
Если номер набора будет находиться в пределах 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 с LSB вправо и удаляет бит LSB.
int x = combo & -combo;
это получает наименьшее значение 1.
int y = combo + x;
это исключает непрерывное 1s стороны LSB и устанавливает 1 на следующем (в приведенном выше случае, 010000 | 001000)
int z = (combo & ~y)
это дает вам непрерывную 1 сторону LSB (000110).
combo = z / x;
combo >> =1;
это для 'сдвинутого непрерывно 1s LSB вправо и удаления бит LSB'.
Таким образом, окончательное задание - это OR y для указанного выше.
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
Ответ 6
Я написал класс в С# для обработки общих функций для работы с биномиальным коэффициентом, который является типом проблемы, с которой сталкивается ваша проблема. Он выполняет следующие задачи:
-
Выводит все K-индексы в хорошем формате для любого N, выбирающего K в файл. K-индексы могут быть заменены более описательными строками или буквами. Этот метод позволяет решить этот тип проблемы довольно тривиально.
-
Преобразует K-индексы в соответствующий индекс записи в таблице отсортированных биномиальных коэффициентов. Этот метод намного быстрее, чем более старые опубликованные методы, основанные на итерации. Он делает это, используя математическое свойство, присущее Pascal Triangle. В моей статье говорится об этом. Я считаю, что я первый, кто открыл и опубликовал эту технику.
-
Преобразует индекс в отсортированную таблицу биномиальных коэффициентов в соответствующие K-индексы. Я считаю, что это также быстрее, чем другие решения.
-
Использует метод Mark Dominus для вычисления биномиального коэффициента, который гораздо реже переполняется и работает с большими числами.
-
Класс написан на .NET С# и предоставляет способ управления объектами, связанными с проблемой (если они есть), используя общий список. Конструктор этого класса принимает значение bool, называемое InitTable, которое, когда true, создаст общий список для хранения объектов, которые будут управляться. Если это значение ложно, то оно не создаст таблицу. Таблицу не нужно создавать, чтобы выполнить описанные выше методы. Для доступа к таблице предоставляются методы доступа.
-
Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был широко протестирован с 2 случаями и нет известных ошибок.
Чтобы прочитать об этом классе и загрузить код, см. Tablizing the Binomial Coeffieicent.
Для переноса класса на С++ должно быть довольно просто.
Решение вашей проблемы связано с генерированием 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.
Ответ 7
За ссылкой ниже приведен общий ответ С# на эту проблему: как отформатировать все комбинации из списка объектов. Вы можете легко ограничить результаты только длиной k.