Ich habe einen Quellcode zum Generieren von Kombinationen mit C++ gesucht. Ich habe einige erweiterte Codes dafür gefunden, aber das ist nur für bestimmte vordefinierte Zahlen gut. Kann mir jemand ein paar Tipps geben oder vielleicht eine Idee, um eine Kombination zu generieren? Nehmen wir als Beispiel an, die Menge S = { 1, 2, 3, …., n} und wir wählen r = 2 daraus. Die Eingabe wäre n
und r
.In diesem Fall erzeugt das Programm Arrays der Länge zwei, wie 5 2 Ausgänge 1 2, 1 3 usw. Ich hatte Schwierigkeiten, den Algorithmus zu konstruieren. Ich habe einen Monat gebraucht, um darüber nachzudenken.
Generieren von Kombinationen in c++
Keneth Adrian
mitchnull
Eine einfache Art zu verwenden 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;
}
oder eine leichte Variation, die die Ergebnisse in einer leichter verständlichen Reihenfolge ausgibt:
#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;
}
Eine kleine Erklärung:
Es funktioniert durch Erstellen eines “Auswahlarrays” (v
), wo wir platzieren r
Selektoren, dann erstellen wir alle Permutationen dieser Selektoren und drucken das entsprechende Set-Mitglied, wenn es in der aktuellen Permutation von ausgewählt ist v
. Hoffe das hilft.
-
Es werden Permutationen und keine Kombinationen ausgegeben, wie in der Frage angegeben. Vielleicht finden Sie diesen Link hilfreich
– Igor Chornos
24. Februar 2012 um 12:52 Uhr
-
Hm. entweder ich vermisse etwas oder du vermisst etwas. sieh dir das an: ideone.com/tfAGp
– mitchnull
24. Februar 2012 um 13:10 Uhr
-
@kids_fox Dieser Code ist korrekt und erzeugt Kombinationen. Der Grund, warum es funktioniert, ist, dass es alle druckt sortiert Permutationen.
– sam hocevar
24. Februar 2012 um 13:37 Uhr
-
Ich habe diesen Code in einer generischen Form umgeschrieben: coliru.stacked-crooked.com/…
– Muhende Ente
1. August 2013 um 17:42 Uhr
-
Sie können diese “leichter zu befolgende Reihenfolge” ohne Umkehrung erhalten
if(v[i])
überprüfen Sie, ob Sie füllenv
vonv.begin()
zuv.end()-n+r
anstattv.begin()+n-r
zuv.end()
.– Ruslan
1. Dezember 2015 um 15:07 Uhr
CapelliC
Sie können es implementieren, wenn Sie dies für jede Ebene beachten R Sie wählen eine Zahl von 1 bis n.
In C++ müssen wir den Zustand „manuell“ zwischen Aufrufen beibehalten, die Ergebnisse erzeugen (eine Kombination): Also bauen wir eine Klasse, die bei der Konstruktion den Zustand initialisiert und ein Mitglied hat, das bei jedem Aufruf die Kombination zurückgibt, solange es Lösungen gibt : zum Beispiel
#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;
}
Testausgabe:
1,2,
1,3,
1,4,
1,5,
2,3,
2,4,
2,5,
3,4,
3,5,
4,5,
meine einfache und effiziente Lösung basierend auf Algorithmen von Prof. Nathan Wodarz:
// 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;
}
}
dann ist die Ausgabe:
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
-
Dies ist der schnellste, einfachste und sauberste nicht-rekursive Algorithmus. Rekursion bringt hier keine Klarheit und ist wahrscheinlich langsamer.
– rwst
4. Mai 2018 um 16:22 Uhr
-
Es ist nur sauber, weil es hartcodiert ist, um mit Werten von 1 bis N zu arbeiten. Ansonsten genau dasselbe wie das allgemeinere von CapelliC.
– rostig
19. Oktober 2018 um 21:10 Uhr
#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
Code ähnelt dem Generieren von Binärziffern. Behalten Sie eine zusätzliche Datenstruktur bei, ein Array Perm[], dessen Wert am Index i angibt, ob das Array-Element enthalten ist oder nicht. Und halten Sie auch eine Zählvariable. Immer wenn Anzahl == Länge der Kombination, Elemente basierend auf zul. drucken[].
#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;
}
TommasoF
Dies ist eine rekursive Methode, die Sie für jeden Typ verwenden können. Sie können eine Instanz der Klasse Combinations durchlaufen (z. B. oder get() Vektor mit allen Kombinationen, jede Kombination ist ein Vektor von Objekten. Dies ist in C++11 geschrieben.
//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;
}
Testdatei:
// 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"; }
}
Ausgabe ist:
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),
Unten ist ein iterativer Algorithmus in C++, der verwendet nicht die STL noch Rekursion noch bedingte verschachtelte Schleifen. Es ist damit schneller, führt keine Elementtausche durch, belastet den Stack nicht mit Rekursionen und lässt sich durch Substitution auch leicht nach ANSI C portieren mallloc()
, free()
und printf()
zum new
, delete
und std::cout
bzw.
Wenn Sie möchten, dass die angezeigten Elemente bei 1 beginnen, ändern Sie die OutputArray()
Funktion.
Nämlich: cout << ka[i]+1...
anstatt cout << ka[i]...
.
Beachten Sie, dass ich verwende K
anstatt 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;
}
-
Das Zuweisen von Speicher vom Heap ist ein zeitaufwändiger Vorgang. Mit Vorlagen können Sie es auf Stapel machen.
– DejanM
6. Januar 2021 um 11:03 Uhr
-
@DejanM: Der Stack-Speicher ist knapper als der Heap-Speicher. Beachten Sie jedoch, dass die Speicherzuweisung nur einmal erfolgt.
– Georg Robinson
17. März 2021 um 19:14 Uhr
Ich verstehe nicht wirklich, was du willst. Angesichts des Satzes
S
und geben Sie 2 ein, möchten Sie alle Kombinationen von 2 und jedes Element vonS
in einem Array der Arraylänge 2?– Derwall
24. Februar 2012 um 12:16 Uhr
Sie müssen genauer angeben, welche Art von Kombinationen Sie möchten. Wollen Sie zum Beispiel mit S = {1, 2} und r=2 {1,2} und {2,1} oder auch {1,1} und {2,2} oder sogar nur {1 ,2}?
– Joachim Isaksson
24. Februar 2012 um 12:17 Uhr
Ich glaube er will das: en.wikipedia.org/wiki/Combination. {1,2} {2,1} sind identisch, und {1,1} und {2,2} sind nicht möglich.
– jrok
24. Februar 2012 um 12:19 Uhr
Für lesbare Algorithmen können Sie in der Python-Dokumentation nachsehen: docs.python.org/library/itertools.html
– orlp
24. Februar 2012 um 12:22 Uhr
Die Antworten ist eine Google-Suche entfernt
– Alexander
24. Februar 2012 um 12:22 Uhr