Я искал исходный код для генерации комбинации с использованием С++. Я нашел несколько продвинутых кодов для этого, но это полезно только для предопределенных данных определенного числа. Может ли кто-нибудь дать мне какие-то намеки или, может быть, какую-то идею создать комбинацию. В качестве примера предположим, что множество S = {1, 2, 3,...., n} и выберем r = 2 из него. Вход будет n и r. В этом случае программа будет генерировать массивы длины два, например, 5 2 выхода 1 2, 1 3 и т.д. Мне было трудно построить алгоритм. Мне понадобился месяц, думая об этом.
Создание комбинаций в С++
Ответ 1
Простой способ использования 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, затем создаем все перестановки этих селекторов и печатаем соответствующий член набора, если он выбран в текущей перестановке of v. Надеюсь, это поможет.
Ответ 2
Вы можете реализовать его, если заметите, что для каждого уровня r вы выбираете число от 1 до n.
В С++ нам нужно "вручную" сохранять состояние между вызовами, которые дают результаты (комбинация): поэтому мы строим класс, который при инициализации конструкции инициализирует состояние, и имеет член, который на каждом вызове возвращает комбинацию while существуют решения: например,
#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,
Ответ 3
#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
Ответ 4
мое простое и эффективное решение, основанное на алгоритмах от профессора Натана Водарца:
// 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
Ответ 5
Я бы посоветовал выяснить, как вы будете делать это на бумаге самостоятельно и вывести псевдокод из этого. После этого вам нужно только решить, как кодировать и хранить управляемые данные.
Для ex:
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
Ответ 6
Вы можете использовать рекурсию, в которой для выбора комбинаций N + 1 вы выбираете N комбинаций, затем добавляете 1 к ней. Добавляемый вами 1 должен всегда быть после последнего из ваших N, поэтому, если ваш N включает последний элемент, нет связанных с ним комбинаций N + 1.
Возможно, это не самое эффективное решение, но оно должно работать.
Базовый блок будет выбирать 0 или 1. Вы можете выбрать 0 и получить пустой набор. Из пустого множества вы можете предположить, что итераторы работают между элементами, а не с ними.
Ответ 7
Код похож на создание двоичных цифр. Сохраните дополнительную структуру данных, массив perm [], значение которой в индексе я укажет, включен ли элемент i-го массива или нет. А также сохранить переменную count. Всякий раз, когда count == length of combination, печатайте элементы на основе 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;
}
Ответ 8
это рекурсивный метод, который можно использовать для любого типа. вы можете перебирать экземпляр класса Combinations (например, или get() со всеми комбинациями, каждая комбинация представляет собой вектор объектов. Это написано на С++ 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),
Ответ 9
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);
}
Ответ 10
Для частного случая (n выберите r), где r - фиксированная константа, мы можем записать r вложенных циклов, чтобы прийти к ситуации. Иногда, когда r не фиксировано, мы можем иметь еще один частный случай (n выбрать n-r), где r снова является фиксированной константой. Идея состоит в том, что каждая такая комбинация является обратной комбинациям (n выбирает r). Поэтому мы можем снова использовать 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 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);
}
}
}
Ответ 11
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;
}
Ответ 12
Вот моя попытка:
Функция (готова для копирования/вставки) без каких-либо зависимостей
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,
Ответ 13
Вы можете просто использовать для циклов, если 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;
}
}
Ответ 14
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");
}
}