нерекурсивный подход к проблеме генерации комбинаций ошибок

Я хотел нерекурсивный подход к проблеме генерации комбинации определенного набора символов или чисел.

Итак, учитывая подмножество k чисел n, сгенерируйте все возможные комбинации n!/k!(n-k)!

Рекурсивный метод даст комбинацию, учитывая предыдущую комбинацию.

Нерекурсивный метод будет генерировать комбинацию заданного значения индекса цикла i.

Я подошел к проблеме с этим кодом:

Протестировано с n = 4 и k = 3, и это работает, но если я изменяю k на число> 3, это не работает.

Неужели из-за того, что (н-к)! в случае n = 4 и k = 3 равно 1. а если k > 3 будет больше 1?

Спасибо.

int facto(int x);

int len,fact,rem=0,pos=0;
int str[7];
int avail[7];


   str[0] = 1;
   str[1] = 2;
   str[2] = 3;
   str[3] = 4;
   str[4] = 5;
   str[5] = 6; 
   str[6] = 7;




  int tot=facto(n) / facto(n-k) / facto(k);




for (int i=0;i<tot;i++)
{


       avail[0]=1;
       avail[1]=2;
       avail[2]=3;
       avail[3]=4;
       avail[4]=5; 
       avail[5]=6;
avail[6]=7;



    rem = facto(i+1)-1;
    cout<<rem+1<<". ";
    for(int j=len;j>0;j--)
    {
        int div = facto(j); 
        pos = rem / div; 
        rem = rem % div; 
        cout<<avail[pos]<<" "; 
        avail[pos]=avail[j];

    }
    cout<<endl;
}

int facto(int x)
{
    int fact=1;
    while(x>0) fact*=x--;
    return fact;
}

c c++ combinatorics non-recursive
person Mark    schedule 01.05.2010    source источник
comment
Это домашнее задание? Пожалуйста, отметьте это как таковое.   -  person Marcelo Cantos    schedule 01.05.2010
comment
Что значит по вине? И вы искали предыдущие вопросы?   -  person Potatoswatter    schedule 01.05.2010
comment
возможный дубликат stackoverflow.com/questions/2211915/ stackoverflow.com/questions/2685501/ stackoverflow.com/questions/127704/   -  person Potatoswatter    schedule 01.05.2010

Ответы (3)


arrow_upward
2
arrow_downward

Эээ... почему бы не использовать std::next_permutation? Он делает именно то, что вы ищете, и не требует, чтобы вы писали (и отлаживали и поддерживали) свои собственные.

person Billy ONeal    schedule 01.05.2010
comment
ну, это не перестановка, которую я ищу, это комбинация, которую я ищу, например, в 1 2 3 4 3 из 4 будет 1 2 3 1 2 4 1 3 4 2 3 4 - person Mark; 01.05.2010
comment
@mark: вы можете использовать двоичные перестановки длины n в качестве фильтра. - person tiftik; 01.05.2010
comment
@Vicente Botet Escriba: я неправильно понял значение словосочетаний true, но пример вывода, который он показывает, — это то, что он должен отредактировать, — это вопрос. - person Billy ONeal; 01.05.2010

arrow_upward
2
arrow_downward

Это настолько быстро, насколько это можно вычислить — фактическая функция комбинации выполняется с использованием двух строк кода. Однако интуитивно понять это не так просто!
Работа выполняется путем реализации последовательности кода Грея.

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <stdint.h>
using namespace std;

//'Combinations' over a set of n objects with k bins, eg n=3,k=2 = 3

//The combination function.
//It takes a combination and returns the next combination.
//It uses GCC's '__builtin_ctzll' which returns the number of
//trailing 0-bits in v, starting at the least significant bit position.
uint64_t combination(uint64_t v) {
    uint64_t t = v | (v - 1ULL); // t gets v's least significant 0 bits set to 1
    return (t + 1ULL) | (((~t & -~t) - 1ULL) >> (__builtin_ctzll(v) + 1ULL));
}

//arg 1 is number of bins (n) arg 2 is number of samples (k/r)
int main (int argc, char *argv[]) {
    uint64_t n = min(64ULL,argc > 1ULL ? atoi(argv[1]) : 3ULL); //max bins = 63
    uint64_t k = min( n,argc > 2 ? atoi(argv[2]) : 2ULL);       //max samples = bins.
    uint64_t v = (1ULL << k) - 1;       //start value;
    uint64_t m = n == 64 ? UINT64_MAX: (1ULL << n) - 1ULL;  //size of n is used as a mask.
    string index = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz+*";
    cout << index.substr(0,n) << endl;
    do {
        cout << bitset<64>(v & m).to_string().substr(64ULL-n) << endl;
        v=combination(v);
    } while (v < m);
    return 0;
}
person Konchog    schedule 03.10.2016

arrow_upward
0
arrow_downward

Учтите, что ваш итератор представляет собой число из k цифр в базе n. В C/C++ вы можете представить его как массив ints размера k, где каждый элемент находится в диапазоне от 0 до n-1).

Затем, чтобы перейти от одной позиции к другой, вам нужно всего лишь увеличить число.

Это даст вам все перестановки. Для получения комбинаций необходимо наложить дополнительное условие — цифры должны быть в порядке возрастания.

Например с k = 3, n = 3: 000 001 002 011 012 022 111 112 122 222

Реализация этого ограничения в C также довольно проста, в операции приращения, используемой для итерации, вместо того, чтобы устанавливать крайние правые цифры в ноль при переносе, вы должны установить их в то же значение, что и самая левая цифра изменилась.

обновление: немного кода:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXK 100

int
main(int argc, char *argv[]) {
    int digits[MAXK];

    int k = atol(argv[1]);
    int n = atol(argv[2]);
    int i, left;

    memset(digits, 0, sizeof(digits));

    while(1) {
        for (i = k; i--; ) {
            printf("%d", digits[i]);
            printf((i ? "-" : "\n"));
        }

        for (i = k; i--; ) {
            left = ++digits[i];
            if (left < n) {
                while (++i < k) digits[i] = left;
                break;
            }
        }
        if (i < 0) break;
    }
}
person salva    schedule 18.01.2011