Het genereren van combinaties in c++

Ik op zoek geweest naar een bron code voor het genereren combinatie met c++. Ik vond een aantal geavanceerde codes voor deze, maar dat is goed voor slechts bepaald aantal vooraf gedefinieerde gegevens. Kan iemand mij wat tips, of misschien een idee voor het genereren combinatie. Als voorbeeld, stel dat de verzameling S = { 1, 2, 3, …., n} en halen we r= 2 uit. De ingang zou worden n en r.In dit geval zal het programma het genereren van arrays van lengte twee, zoals 5 2 uitgangen 1 2, 1 3, enz.. ik had moeite met het construeren van het algoritme. Het kostte me een maand na te denken over dit.

  • Ik begrijp niet echt wat je wilt. Gegeven de set S en ingang 2 wilt u alle combinaties van 2 en elk item van S in een matrix matrix lengte 2?
  • Je moet meer specifiek wat voor soort combinaties die u wilt. Bijvoorbeeld, met S = {1, 2} en r=2, wilt u {1,2} en {2,1}, of {1,1} en {2,2} of {1,2}?
  • Ik denk dat hij wil is dit: en.wikipedia.org/wiki/Combination. {1,2} {2,1} is hetzelfde, {1,1} en {2,2} is niet mogelijk.
  • Voor leesbare algoritmen, kunt u zoeken in de Python documentatie: docs.python.org/library/itertools.html
  • De beantwoorden is een google-zoekopdracht afstand
  • er is een uitgebreid antwoord op uw vraag hier stackoverflow.com/questions/127704/…
  • Als ik het goed begrijp, bent u op zoek naar een soort algemene algoritme, toch? Met r=2, u hoeft slechts twee geneste loops, maar met r=3, dan zou je drie, dus dat zou in principe een ander algoritme, en u op zoek bent naar een enkel algoritme dat behandelt alle gevallen tot r=count. Rechts? Is dat uw vraag?
  • Ja, @MrLister. Ik ben op zoek naar een enkel algoritme in C++ waar de uitgang als we n het aantal elementen in de verzameling en r de lengte van de array.
  • Ik ben niet bezorgd over de permutatie, hoe, dit is wat ik wilde weten: als we n= 5; dat is 1,2 ,3 ,4 5. en r = 1 kregen we de uitgang 1,2,3,4,5. maar als r=5, dan hebben we 1 2 3 4 5. het veranderen van de ingangen n= 5 r= 2, we hebben : 1 2 , 1 3, 1 4, 1 5 , 2 3 , enz… waar kunnen we controleren met behulp van de formule voor combinatie..
  • Ik denk niet dat het geaccepteerd antwoord is een keuze.

 

13 Replies
  1. 110

    Een eenvoudige manier met behulp van 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;
    }

    of een lichte variatie die uitgangen van de resultaten in een makkelijker te volgen volgorde:

    #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;
    }

    Een beetje uitleg:

    Het werkt door het creëren van een “selectie array” (v), waar wij r selectors, daarna maken we alle permutaties van deze kiezers, en afdrukken van de bijbehorende set lid als deze geselecteerd is in de huidige permutatie van v. Hoop dat dit helpt.

    • Het zal de output permutaties en combinaties niet zoals werd vermeld in de vraag. U kan vinden op de deze link behulpzaam
    • Nee. het zal de output combinaties. probeer het misschien? 🙂
    • Ik probeerde het, het output geneste lus (reverse), iets zoals <code>for (int n = 5; n >= 1; –n) for (int m = n – 1; m >= 1; –m) cout << n << m< code>
    • Ik zie niet in deze produceert combinaties
    • hm. ofwel heb ik iets gemist of mist u iets. check this out: ideone.com/tfAGp
    • Deze code is correct en het levert combinaties. De reden waarom het werkt is omdat het hiermee drukt u alle sorteren permutaties.
    • Dank u, Sam. Ik miste dit
    • Dank je wel voor de code. Het is eigenlijk klopt en hij doet het genereren van combinaties. hoewel ik het niet volledig begrijpen van het algoritme; wat zou de looptijd van dit algoritme?
    • std::next_permutation presteert op de meeste n/2 swaps. De buitenste lus loopt Cr(n, r) keer, en we hebben ook een binnenste lus die O(n).
    • Ik herschreef deze code in een generieke vorm: coliru.stacked-crooked.com/…
    • combinatie kan betekenen selecteren k uit n . dus permutatie kan mislukken, maar als we naar de vorm combinaties met alle n tekens , dit is correct .
    • betekenen”? combinatie te selecteren k van n, en dit programma doet precies dat. Permutatie wordt alleen gebruikt voor het genereren van alle permutaties van de reeks.
    • excuses , ik zag alleen next_permutation in haast .
    • Kunt u dat “makkelijker te volgen om” zonder kerende if(v[i]) controleren of u vult v van v.begin() te v.end()-n+r in plaats van v.begin()+n-r te v.end().
    • bent u zeker? dat zou betekenen 1 1 1 0 0 (bijvoorbeeld ingangen n=5 r=3) voor het starten van set, en next_permutation zou zijn 0 0 1 1 1 (die zou worden lexicographically kleiner), dus zou de lus stopt na de eerste iteratie…
    • Ah, goed, je zou ook moeten gebruiken prev_permutation in dat geval.
    • Eh, inderdaad. Ik heb er niet aan gedacht van het gebruik van prev_permutation 😉 Zal het bijwerken van het antwoord, bedankt.

  2. 6

    U kunt uitvoeren als u er rekening mee dat voor elk niveau r selecteert u een nummer van 1 tot n.

    In C++, we moeten ‘handmatig’ houden van de staat tussen de gesprekken dat levert resultaten op (een combinatie van): we bouwen een klasse die op de bouw-initialiseren van de staat, en is een lid dat op elk gesprek geeft de combinatie terwijl er oplossingen: bijvoorbeeld

    #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;
    }

    test output:

    1,2,
    1,3,
    1,4,
    1,5,
    2,3,
    2,4,
    2,5,
    3,4,
    3,5,
    4,5,
  3. 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
    • dit omvat verschillende permutaties van dezelfde combinatie, probeer het wijzigen van de 2de lus for (int j=i+1;j<=5;j++)
  4. 3

    mijn eenvoudige en efficiënte oplossing, gebaseerd op algoritmen van 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;
        }
    }

    is de uitvoer:

    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

    • Dit is de snelste, eenvoudigste en zuiverste niet-recursief algoritme. Recursie niet toevoegen duidelijkheid hier en is waarschijnlijk langzamer.
    • Het is schoon, omdat het moeilijk is gecodeerd zijn om te werken met waarden van 1 tot en met N. Anders precies hetzelfde als de meer generieke één van CapelliC.
  5. 2

    Ik zou willen voorstellen het uitzoeken hoe je dat zou doen op papier jezelf en concluderen pseudocode van dat. Na dat, je hoeft alleen te beslissen over de manier van coderen en opslaan van de gegevens gemanipuleerd.

    Voor 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. 2

    Kunt u gebruik maken van recursie waarbij pick N+1 combinaties je pick-N combinaties voeg dan 1. De 1 die u toevoegt, moet altijd na de laatste van N, dus als je N omvat het laatste element is er geen N+1 combinaties gekoppeld.

    Misschien niet de meest efficiënte oplossing, maar het zou moeten werken.

    Base geval zou het plukken van 0 of 1. Je kon kiezen 0 en krijgen een lege verzameling. Van een lege set kunt u ervan uitgaan dat iterators werk tussen de elementen en niet bij hen.

  7. 2

    – Code is vergelijkbaar met het genereren van binaire cijfers. Houden met een extra data-structuur, een array perm[], waarvan de waarde bij index zal ik vertellen als i-de array-element wordt opgenomen of niet. En ook het houden van een aantal variabele. Wanneer count == lengte van de combinatie -, print-elementen op basis van 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;
    }
    • Gebruik geen turboc
    • voor de liefde van de almachtige god van de code
  8. 2

    dit is een recursieve methode die je kunt gebruiken op elk type. u kunt itereren op een exemplaar van Combinaties klasse (bijv. of get() vector met alle combinaties, iedere combinatie is een vector van objecten. Dit is geschreven in 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 bestand:

    //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"; }    
    
    }

    uitvoer is :

    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. 0
    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. 0

    Voor het speciale geval van (n-r), waar r is een vaste constante is, kunnen we schrijven r geneste lussen te komen op de situatie. Soms, als r niet is opgelost, we hebben misschien een ander speciaal geval (n) kies n-r), waar de r is weer een vaste constante. Het idee is dat elke dergelijke combinatie is de inverse van de combinaties van (n-r). Dus we kunnen weer gebruik maken van r geneste loops, maar omkeren van de oplossing:

    //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);
          }
       }
    }
  11. 0
    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. 0

    Hier mijn poging:

    Functie (gereed voor kopiëren/plakken) zonder enige afhankelijkheid

     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;
            }

    Test:

    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 ) );

    En output:

    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. 0

    Je kan gewoon gebruik maken van for-lussen als r is klein, hier r = 2, dus twee for-lussen:

    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;     
         }
    }
    • moet gebruik maken van recursie

Geef een reactie

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *