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

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

52 голосов
/ 24 февраля 2012

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

Ответы [ 12 ]

0 голосов
/ 12 марта 2016

Для частного случая (n выберите r) , где r - фиксированная константа, мы можем написать вложенные циклы, чтобы прийти к ситуации.Иногда, когда r не является фиксированным, мы можем иметь другой особый случай (n выберите nr) , где r снова является фиксированной константой.Идея состоит в том, что каждая такая комбинация является обратной к комбинациям (n выбирают 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);
      }
   }
}
0 голосов
/ 11 декабря 2013 
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);
}
Страница:
...