Генерация комбинаций в с ++
Я искал исходный код для генерации комбинации с использованием C++. Я нашел несколько расширенных кодов для этого, но это хорошо только для определенного числа предварительно определенных данных. Может кто-нибудь дать мне несколько советов, или, может быть, какую-то идею для создания комбинации. В качестве примера предположим, что множество S = { 1, 2, 3, ...., n}, и мы выбираем из него r= 2. Вход будет n а также r. В этом случае программа будет генерировать массивы длины два, например, 5 2 выходных данных 1 2, 1 3 и т. Д. У меня были трудности при построении алгоритма. Мне потребовался месяц, чтобы подумать об этом.
18 ответов
Простой способ использования std::next_permutation:
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
int n, r;
std::cin >> n;
std::cin >> r;
std::vector<bool> v(n);
std::fill(v.end() - r, v.end(), true);
do {
for (int i = 0; i < n; ++i) {
if (v[i]) {
std::cout << (i + 1) << " ";
}
}
std::cout << "\n";
} while (std::next_permutation(v.begin(), v.end()));
return 0;
}
или небольшое изменение, которое выводит результаты в более легком для следования порядке:
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
int n, r;
std::cin >> n;
std::cin >> r;
std::vector<bool> v(n);
std::fill(v.begin(), v.begin() + r, true);
do {
for (int i = 0; i < n; ++i) {
if (v[i]) {
std::cout << (i + 1) << " ";
}
}
std::cout << "\n";
} while (std::prev_permutation(v.begin(), v.end()));
return 0;
}
Немного объяснения:
Это работает путем создания "массива выбора" (v), где мы размещаем r селекторы, затем мы создаем все перестановки этих селекторов и печатаем соответствующий элемент набора, если он выбран в текущей перестановке v, Надеюсь это поможет.
Вы можете реализовать это, если заметите, что для каждого уровня r вы выбираете число от 1 до n.
В C++ нам нужно "вручную" сохранять состояние между вызовами, которые дают результаты (комбинацию): поэтому мы создаем класс, который по конструкции инициализирует состояние и имеет член, который при каждом вызове возвращает комбинацию, пока существуют решения: например
#include <iostream>
#include <iterator>
#include <vector>
#include <cstdlib>
using namespace std;
struct combinations
{
typedef vector<int> combination_t;
// initialize status
combinations(int N, int R) :
completed(N < 1 || R > N),
generated(0),
N(N), R(R)
{
for (int c = 1; c <= R; ++c)
curr.push_back(c);
}
// true while there are more solutions
bool completed;
// count how many generated
int generated;
// get current and compute next combination
combination_t next()
{
combination_t ret = curr;
// find what to increment
completed = true;
for (int i = R - 1; i >= 0; --i)
if (curr[i] < N - R + i + 1)
{
int j = curr[i] + 1;
while (i <= R-1)
curr[i++] = j++;
completed = false;
++generated;
break;
}
return ret;
}
private:
int N, R;
combination_t curr;
};
int main(int argc, char **argv)
{
int N = argc >= 2 ? atoi(argv[1]) : 5;
int R = argc >= 3 ? atoi(argv[2]) : 2;
combinations cs(N, R);
while (!cs.completed)
{
combinations::combination_t c = cs.next();
copy(c.begin(), c.end(), ostream_iterator<int>(cout, ","));
cout << endl;
}
return cs.generated;
}
тестовый вывод:
1,2,
1,3,
1,4,
1,5,
2,3,
2,4,
2,5,
3,4,
3,5,
4,5,
Мое простое и эффективное решение, основанное на алгоритмах от профессора Натана Водарца:
// n choose r combination
#include <vector>
#include <iostream>
#include <algorithm>
struct c_unique {
int current;
c_unique() {current=0;}
int operator()() {return ++current;}
} UniqueNumber;
void myfunction (int i) {
std::cout << i << ' ';
}
int main()
{
int n=5;
int r=3;
std::vector<int> myints(r);
std::vector<int>::iterator first = myints.begin(), last = myints.end();
std::generate(first, last, UniqueNumber);
std::for_each(first, last, myfunction);
std::cout << std::endl;
while((*first) != n-r+1){
std::vector<int>::iterator mt = last;
while (*(--mt) == n-(last-mt)+1);
(*mt)++;
while (++mt != last) *mt = *(mt-1)+1;
std::for_each(first, last, myfunction);
std::cout << std::endl;
}
}
тогда вывод:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
#include<iostream>
using namespace std;
for(int i=1;i<=5;i++)
for (int j=2;j<=5;j++)
if (i!=j)
cout<<i<<","<<j<<","<<endl;
//or instead of cout... you can put them in a matrix n x 2 and use the solution
Это рекурсивный метод, который вы можете использовать для любого типа. Вы можете перебирать экземпляр класса Combination (например, вектор get или) со всеми комбинациями, каждая комбинация является вектором объектов. Это написано на C++11.
//combinations.hpp
#include <vector>
template<typename T> class Combinations {
// Combinations(std::vector<T> s, int m) iterate all Combinations without repetition
// from set s of size m s = {0,1,2,3,4,5} all permuations are: {0, 1, 2}, {0, 1,3},
// {0, 1, 4}, {0, 1, 5}, {0, 2, 3}, {0, 2, 4}, {0, 2, 5}, {0, 3, 4}, {0, 3, 5},
// {0, 4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5},
// {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}
public:
Combinations(std::vector<T> s, int m) : M(m), set(s), partial(std::vector<T>(M))
{
N = s.size(); // unsigned long can't be casted to int in initialization
out = std::vector<std::vector<T>>(comb(N,M), std::vector<T>(M)); // allocate space
generate(0, N-1, M-1);
};
typedef typename std::vector<std::vector<T>>::const_iterator const_iterator;
typedef typename std::vector<std::vector<T>>::iterator iterator;
iterator begin() { return out.begin(); }
iterator end() { return out.end(); }
std::vector<std::vector<T>> get() { return out; }
private:
void generate(int i, int j, int m);
unsigned long long comb(unsigned long long n, unsigned long long k); // C(n, k) = n! / (n-k)!
int N;
int M;
std::vector<T> set;
std::vector<T> partial;
std::vector<std::vector<T>> out;
int count (0);
};
template<typename T>
void Combinations<T>::generate(int i, int j, int m) {
// combination of size m (number of slots) out of set[i..j]
if (m > 0) {
for (int z=i; z<j-m+1; z++) {
partial[M-m-1]=set[z]; // add element to permutation
generate(z+1, j, m-1);
}
} else {
// last position
for (int z=i; z<j-m+1; z++) {
partial[M-m-1] = set[z];
out[count++] = std::vector<T>(partial); // add to output vector
}
}
}
template<typename T>
unsigned long long
Combinations<T>::comb(unsigned long long n, unsigned long long k) {
// this is from Knuth vol 3
if (k > n) {
return 0;
}
unsigned long long r = 1;
for (unsigned long long d = 1; d <= k; ++d) {
r *= n--;
r /= d;
}
return r;
}
Тестовый файл:
// test.cpp
// compile with: gcc -O3 -Wall -std=c++11 -lstdc++ -o test test.cpp
#include <iostream>
#include "combinations.hpp"
struct Bla{
float x, y, z;
};
int main() {
std::vector<int> s{0,1,2,3,4,5};
std::vector<Bla> ss{{1, .4, 5.0},{2, .7, 5.0},{3, .1, 2.0},{4, .66, 99.0}};
Combinations<int> c(s,3);
// iterate over all combinations
for (auto x : c) { for (auto ii : x) std::cout << ii << ", "; std::cout << "\n"; }
// or get a vector back
std::vector<std::vector<int>> z = c.get();
std::cout << "\n\n";
Combinations<Bla> cc(ss, 2);
// combinations of arbitrary objects
for (auto x : cc) { for (auto b : x) std::cout << "(" << b.x << ", " << b.y << ", " << b.z << "), "; std::cout << "\n"; }
}
вывод:
0, 1, 2, 0, 1, 3, 0, 1, 4, 0, 1, 5, 0, 2, 3, 0, 2, 4, 0, 2, 5, 0, 3, 4, 0, 3, 5, 0, 4, 5, 1, 2, 3, 1, 2, 4, 1, 2, 5, 1, 3, 4, 1, 3, 5, 1, 4, 5, 2, 3, 4, 2, 3, 5, 2, 4, 5, 3, 4, 5,
(1, 0,4, 5), (2, 0,7, 5), (1, 0,4, 5), (3, 0,1, 2), (1, 0,4, 5), (4, 0,66, 99), (2, 0,7, 5), (3, 0,1, 2), (2, 0,7, 5), (4, 0,66, 99), (3, 0,1, 2), (4, 0,66, 99),
Код похож на генерацию двоичных цифр. Сохраните дополнительную структуру данных, массив perm[], значение которого по индексу я скажу, включен ли i-й элемент массива или нет. А также держите переменную count. Всякий раз, когда считается == длина комбинации, выведите элементы на основе perm[].
#include<stdio.h>
// a[] : given array of chars
// perm[] : perm[i] is 1 if a[i] is considered, else 0
// index : subscript of perm which is to be 0ed and 1ed
// n : length of the given input array
// k : length of the permuted string
void combinate(char a[], int perm[],int index, int n, int k)
{
static int count = 0;
if( count == k )
{
for(int i=0; i<n; i++)
if( perm[i]==1)
printf("%c",a[i]);
printf("\n");
} else if( (n-index)>= (k-count) ){
perm[index]=1;
count++;
combinate(a,perm,index+1,n,k);
perm[index]=0;
count--;
combinate(a,perm,index+1,n,k);
}
}
int main()
{
char a[] ={'a','b','c','d'};
int perm[4] = {0};
combinate(a,perm,0,4,3);
return 0;
}
Ниже приведен итеративный алгоритм на C++, который не использует ни STL, ни рекурсию, ни условные вложенные циклы. Так он быстрее, не выполняет никаких обменов элементами и не нагружает стек рекурсией, а также может быть легко перенесен на ANSI C, заменив
mallloc(),
free()а также
printf()за
new,
deleteа также
std::cout, соответственно.
Если вы хотите, чтобы отображаемые элементы начинались с 1, измените
OutputArray()функция.
А именно:
cout << ka[i]+1...вместо
cout << ka[i]....
Обратите внимание, что я использую
Kвместо
r.
void OutputArray(unsigned int* ka, size_t n) {
for (int i = 0; i < n; i++)
std::cout << ka[i] << ",";
std::cout << endl;
}
void GenCombinations(const unsigned int N, const unsigned int K) {
unsigned int *ka = new unsigned int [K]; //dynamically allocate an array of UINTs
unsigned int ki = K-1; //Point ki to the last elemet of the array
ka[ki] = N-1; //Prime the last elemet of the array.
while (true) {
unsigned int tmp = ka[ki]; //Optimization to prevent reading ka[ki] repeatedly
while (ki) //Fill to the left with consecutive descending values (blue squares)
ka[--ki] = --tmp;
OutputArray(ka, K);
while (--ka[ki] == ki) { //Decrement and check if the resulting value equals the index (bright green squares)
OutputArray(ka, K);
if (++ki == K) { //Exit condition (all of the values in the array are flush to the left)
delete[] ka;
return;
}
}
}
}
int main(int argc, char *argv[])
{
GenCombinations(7, 4);
return 0;
}
Комбинации: Из «7 выберите 4». 
Вы можете использовать рекурсию, чтобы выбрать N+1 комбинацию, которую вы выбираете N комбинаций, а затем добавить 1 к ней. 1, который вы добавляете, всегда должен быть после последнего из ваших N, поэтому, если ваш N включает в себя последний элемент, с ним не будет связано ни одной комбинации N+1.
Возможно, не самое эффективное решение, но оно должно работать.
Базовый случай будет выбирать 0 или 1. Вы можете выбрать 0 и получить пустой набор. Из пустого набора можно предположить, что итераторы работают между элементами, а не над ними.
Я бы посоветовал выяснить, как бы вы это сделали на бумаге, и сделать из этого псевдокод. После этого вам нужно только выбрать способ кодирования и хранения манипулируемых данных.
Например:
For each result item in result array // 0, 1, ... r
For each item possible // 0, 1, 2, ... n
if current item does not exist in the result array
place item in result array
exit the inner for
end if
end for
end for
Можно напрямую вычислить индексы всех комбинаций в лексикографическом порядке, как я сделал в следующем коде.
Эти индексы можно использовать для прямого вывода или в качестве указателей на любые комбинированные элементы, например
"abcde"строка во втором примере функции main(), см. пример вывода после кода.
#include <vector>
#include <iostream>
template <typename F>
void Combinations(size_t n, size_t k, F && out) {
if (k > n)
return;
std::vector<size_t> a(k);
for (size_t i = 0; i < k; ++i)
a[i] = i;
while (true) {
out(a);
int i = int(k) - 1;
while (i >= 0 && a[i] >= n - 1 - (k - 1 - i))
--i;
if (i < 0)
break;
for (size_t j = a[i] + 1; i < k; ++j, ++i)
a[i] = j;
}
}
int main() {
Combinations(5, 3, [](auto const & a){
for (auto i: a)
std::cout << i << " ";
std::cout << std::endl;
});
std::string s = "abcde";
Combinations(5, 3, [&](auto const & a){
for (auto i: a)
std::cout << s[i] << " ";
std::cout << std::endl;
});
}
Выход:
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
a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e
Вот моя попытка:
Функция (готовая к копированию / вставке) без каких-либо зависимостей
template<class _Tnumber, class _Titerator >
bool next_combination
(
_Titerator const& _First
, _Titerator const& _Last
, _Tnumber const& _Max //!< Upper bound. Not reachable
)
{
_Titerator _Current = _First;
if( _Current == _Last )
{
return false;
}
*_Current += 1;
if( *_Current < _Max )
{
return true;
}
_Titerator _Next = _Current + 1;
if( _Next == _Last )
{
return false;
}
if( false == next_combination( _Next, _Last, _Max - 1 ) )
{
return false;
}
*_Current = *_Next + 1;
return *_Current < _Max;
}
Контрольная работа:
vector<int> vec({3,2,1}); // In descending order and different
do
{
copy( vec.begin(), vec.end(), ostream_iterator<int>(cout, ", " ) ); cout << endl;
}while( ::math::algorithm::next_combination( vec.begin(), vec.end(), 6 ) );
И вывод:
3, 2, 1,
4, 2, 1,
5, 2, 1,
4, 3, 1,
5, 3, 1,
5, 4, 1,
4, 3, 2,
5, 3, 2,
5, 4, 2,
5, 4, 3,
void print(int *a, int* s, int ls)
{
for(int i = 0; i < ls; i++)
{
cout << a[s[i]] << " ";
}
cout << endl;
}
void PrintCombinations(int *a, int l, int k, int *s, int ls, int sp)
{
if(k == 0)
{
print(a,s,ls);
return;
}
for(int i = sp; i < l; i++)
{
s[k-1] = i;
PrintCombinations(a,l,k-1,s,ls,i+1);
s[k-1] = -1;
}
}
int main()
{
int e[] = {1,2,3,4,5,6,7,8,9};
int s[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
PrintCombinations(e,9,6,s,6,0);
}
Для частного случая (n выберите r), где r - фиксированная константа, мы можем написать вложенные циклы, чтобы прийти к ситуации. Иногда, когда r не является фиксированным, у нас может быть другой особый случай (n выберите nr), где r снова является фиксированной константой. Идея состоит в том, что каждая такая комбинация является обратной к комбинациям (n выбирают r). Таким образом, мы можем снова использовать вложенные циклы, но инвертировать решение:
// example 1: choose each 2 from given vector and apply 'doSomething'
void doOnCombinationsOfTwo(const std::vector<T> vector) {
for (int i1 = 0; i1 < vector.size() - 1; i1++) {
for (int i2 = i1 + 1; i2 < vector.size(); i2++) {
doSomething( { vector[i1], vector[i2] });
}
}
}
// example 2: choose each n-2 from given vector and apply 'doSomethingElse'
void doOnCombinationsOfNMinusTwo(const std::vector<T> vector) {
std::vector<T> combination(vector.size() - 2); // let's reuse our combination vector
for (int i1 = 0; i1 < vector.size() - 1; i1++) {
for (int i2 = i1 + 1; i2 < vector.size(); i2++) {
auto combinationEntry = combination.begin(); // use iterator to fill combination
for (int i = 0; i < vector.size(); i++) {
if (i != i1 && i != i2) {
*combinationEntry++ = i;
}
}
doSomethingElse(combinationVector);
}
}
}
Это кажется читаемым, а также работает для
std::vector,
std::list,
std::deque или даже статический объявлен
int intArray[]
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <list>
#include <set>
#include <iterator>
template<typename InputIt, typename T>
bool nextCombination(InputIt begin,
InputIt end,
T toElement) {
/*
Given sequence: 1 2 3 4 5
Final sequence: 6 7 8 9 10
-- Formally --
Given sequence: 1 2 ... k-1 k
Final sequence: (n-k+1) (n-k+2) ... (n-1) n
lengthOfSubsequence = positionOf(5) - positionOf(1) = 5
We look for an element that satisfies:
seqeunce[pos] < n - k + pos
*/
const auto lengthOfSubsequence = std::distance(begin, end);
auto viewed_element_it = std::make_reverse_iterator(end);
auto reversed_begin = std::make_reverse_iterator(begin);
/*Looking for this element here*/
while ((viewed_element_it != reversed_begin) &&
(*viewed_element_it >= toElement -
lengthOfSubsequence +
std::distance(viewed_element_it, reversed_begin))) {
//std::distance shows position of element in subsequence here
viewed_element_it++;
}
if (viewed_element_it == reversed_begin)
return false;
auto it = std::prev(viewed_element_it.base());
/*
Increment the found element.
The rest following elements we set as seqeunce[pos] = seqeunce[pos-1] + 1
*/
std::iota(it, end, *it + 1);
return true;
}
int main()
{
std::list<int> vec = { 1, 2, 3 };
do {
std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
} while (nextCombination(vec.begin(), vec.end(), 10));
}
vector<list<int>> generate(int N, int K, int& count) {
vector<list<int>> output;
if(K == 1) {
count = N;
for(int i = 1; i <= N; i++) {
list<int> l = {i};
output.push_back(l);
}
} else {
count = 0;
int n;
vector<list<int>> l = generate(N, K - 1, n);
for(auto iter = l.begin(); iter != l.end(); iter++) {
int last = iter->back();
for (int i = last + 1; i <= N; ++i) {
list<int> value = *iter;
value.push_back(i);
output.push_back(value);
count++;
}
}
}
return output;
}
Вы можете просто использовать для циклов, если r мало, здесь r = 2, поэтому два для циклов:
unsigned int i, j, max=0;
for(i=1; i<=n; i++){
for(j=i+1; j<=n; j++){
int ans = (i & j);
cout << i << " " << j << endl;
}
}
#include <bits/stdc++.h>
using namespace std;
int next_combination(int sub) {
int x = sub &(-sub), y = sub + x;
return (((sub & ~y)/ x) >> 1) | y;
}
int main() {
int n = 5; // {0, 1, 2, 3, 4}
int k = 3; // k >0
int bit = (1<<k) -1;
for(;bit < (1<<n); bit=next_combination(bit)) {
vector<int> s;
for(int i=0;i<n;i++) {
if(bit &(1<<i)) s.push_back(i);
}
cout <<bit << " " << "{" << " ";
for(int ele : s) {
cout << ele << " ";
}
cout << "}" << endl;
}
return 0;
}
выход:
7 { 0 1 2 }
11 { 0 1 3 }
13 { 0 2 3 }
14 { 1 2 3 }
19 { 0 1 4 }
21 { 0 2 4 }
22 { 1 2 4 }
25 { 0 3 4 }
26 { 1 3 4 }
28 { 2 3 4 }
public static class CombinationGenerator {
int n;
int k;
Integer[] input;
List<List<Integer>> output;
public CombinationGenerator(int n, int k) {
this.n = n;
this.k = k;
input = new Integer[n];
for (int i = 1; i <= n; i++) {
input[i-1] = i;
}
}
public List<List<Integer>> generate(){
if(k>n){
throw new RuntimeErrorException(null, "K should be less than N");
}
output = generate(0, k);
printOutput();
return output;
}
private List<List<Integer>> generate(int cur, int k) {
List<List<Integer>> output = new ArrayList<List<Integer>>();
int length = input.length - cur;
if(length == k){
List<Integer> result = new ArrayList<Integer>();
for (int i = cur; i < input.length; i++) {
result.add(input[i]);
}
output.add(result);
}
else if( k == 1){
for (int i = cur; i < input.length; i++) {
List<Integer> result = new ArrayList<Integer>();
result.add(input[i]);
output.add(result);
}
}
else{
for (int i = cur; i < input.length; i++) {
List<List<Integer>> partialResult = generate(i+1, k-1);
for (Iterator<List<Integer>> iterator = partialResult.iterator(); iterator
.hasNext();) {
List<Integer> list = (List<Integer>) iterator.next();
list.add(input[i]);
}
output.addAll(partialResult);
}
}
return output;
}
private void printOutput(){
for (Iterator<List<Integer>> iterator = output.iterator(); iterator
.hasNext();) {
printList((List<Integer>) iterator.next());
}
}
private void printList(List<Integer> next) {
for (Iterator<Integer> iterator = next.iterator(); iterator.hasNext();) {
Integer integer = (Integer) iterator.next();
System.out.print(integer.intValue());
}
System.out.print("\n");
}
}