C ++에서 조합 생성

C ++에서 조합 생성

---

C ++를 사용하여 조합을 생성하기위한 소스 코드를 찾고 있습니다. 이에 대한 고급 코드를 찾았지만 특정 번호의 사전 정의 된 데이터에만 유용합니다. 누구든지 나에게 몇 가지 힌트를 주거나 조합을 생성하는 아이디어를 줄 수 있습니까? 예를 들어 S = {1, 2, 3, ...., n} 세트를 가정하고 r = 2를 선택합니다. 입력은 n및 r.이 경우 프로그램은 5 2 출력 1 2, 1 3 등과 같이 길이 2의 배열을 생성합니다. 알고리즘을 구성하는 데 어려움이있었습니다. 이것에 대해 생각하는 데 한 달이 걸렸습니다.

---

사용하는 간단한 방법 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,

---

          #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

---

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

출력은 다음과 같습니다.
12 3
12 4
1 2 5
1 3 4
1 3 5
1 4 5
2 34
2 3 5
2 4 5
3 4 5

---

나는 당신이 종이에 어떻게 할 것인지 알아 내고 그것으로부터 의사 코드를 추론하는 것이 좋습니다. 그 후에는 조작 된 데이터를 인코딩하고 저장하는 방법 만 결정하면됩니다.

예 :

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

---

재귀를 사용하여 N + 1 조합을 선택하고 N 조합을 선택한 다음 1을 더할 수 있습니다. 추가하는 1은 항상 N의 마지막 요소 뒤에 있어야하므로 N에 마지막 요소가 포함되어 있으면 N + 1 조합이 연결되지 않습니다.

아마도 가장 효율적인 솔루션은 아니지만 작동해야합니다.

기본 케이스는 0 또는 1을 선택합니다. 0을 선택하고 빈 세트를 얻을 수 있습니다. 빈 집합에서 반복기가 요소가 아닌 요소간에 작동한다고 가정 할 수 있습니다.

---

코드는 이진수 생성과 유사합니다. 추가 데이터 구조 인 배열 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;
}

---

이것은 모든 유형에서 사용할 수있는 재귀 적 방법입니다. Combinations 클래스의 인스턴스 (예 : 모든 조합이있는 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),

---

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

---

r이 고정 된 상수 인 (n choose r) 의 특수한 경우 , 상황에 도달하기 위해 r 개의 중첩 루프를 작성할 수 있습니다. 때로는 r이 고정되지 않은 경우 또 다른 특별한 경우가있을 수 있습니다 (n choose nr) , 여기서 r은 다시 고정 상수입니다. 아이디어는 이러한 모든 조합이 (n choose 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'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);
      }
   }
}

---

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

---

내 시도는 다음과 같습니다.

종속성없는 기능 (복사 / 붙여 넣기 준비)

 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,

---

r이 작 으면 for 루프를 사용할 수 있습니다. 여기서 r = 2이므로 두 개의 for 루프가 있습니다.

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

참조 URL : https://stackoverflow.com/questions/9430568/generating-combinations-in-c