Генерация комбинаций в с ++

Question

Я искал исходный код для генерации комбинации с использованием c ++. Я нашел несколько расширенных кодов для этого, но это хорошо только для определенного числа предварительно определенных данных. Может кто-нибудь дать мне несколько советов, или, может быть, какую-то идею для создания комбинации. В качестве примера предположим, что множество S = {1, 2, 3, ...., n}, и мы выбираем r = 2 из него. Входные данные будут n и r. В этом случае программа сгенерирует массивы длины два, например 5 2 выходных данных 1 2, 1 3 и т. Д. У меня возникли трудности при построении алгоритма. Мне потребовался месяц, чтобы подумать об этом.

Answer 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, затем мы создаем все перестановки этих селекторов и печатаем соответствующий элемент набора, если он выбран втекущая перестановка v.Надеюсь, это поможет.

Answer 2

Вы можете реализовать это, если заметите, что для каждого уровня 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,

Answer 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

Answer 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

Answer 5

это рекурсивный метод, который вы можете использовать для любого типа.Вы можете перебирать экземпляр класса 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),

Answer 6

Код аналогичен генерации двоичных цифр.Сохраните дополнительную структуру данных, массив 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;
}

Answer 7

Вы можете использовать рекурсию, чтобы выбрать N + 1 комбинацию, которую вы выбираете N комбинаций, а затем добавить 1 к ней.1, который вы добавляете, должен всегда быть после последнего из ваших N, поэтому, если ваш N включает в себя последний элемент, с ним не связано ни одной комбинации N + 1.

Возможно, не самое эффективное решение, но оно должно работать.

Базовый случай будет выбирать 0 или 1. Вы можете выбрать 0 и получить пустой набор.Из пустого набора можно предположить, что итераторы работают между элементами, а не на них.

Answer 8

Я бы посоветовал выяснить, как бы вы это сделали на бумаге, и сделать из этого псевдокод.После этого вам нужно только выбрать способ кодирования и хранения манипулируемых данных.

Например:

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

Answer 9

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

Answer 10

Вы можете просто использовать для циклов, если 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;     
     }
}