Какой лучший способ генерировать выбор из данного набора чисел?

Question

, например, если дано сделать выбор от 1 до 5, и ответ выглядит следующим образом.

1,2,3,4,5,  
1-2,1-3,1-4,1-5,2-3,2-4,2-5,3-4,3-5,4-5,  
1-2-3,1-2-4,1-2-5,1-3-4,
.....,
1-2-3-4-5.

Может кто-нибудь предложить быстрый алгоритм?

Answer 1

Просто сгенерируйте все целые числа от одного (или нуля, если вы хотите включить пустой набор) до 2 ^ N - 1 . Ваши наборы обозначены битами набора в номере. Например, если у вас есть 5 элементов {A, B, C, D, E}, число 6 = 00110 будет представлять подмножество {C, D}.

Answer 2

Самый быстрый способ - использовать шаблон метапрограммирования , который будет обменивать время компиляции и размер кода на время выполнения.Но это будет полезно только для небольшого числа комбинаций, и вы должны знать их заранее.Но вы сказали «быстро»:)

#include <iostream>
using namespace std;

typedef unsigned int my_uint;

template <my_uint M>
struct ComboPart {
    ComboPart<M-1> rest;

    void print() {
        rest.print();
        for(my_uint i = 0; i < sizeof(my_uint) * 8; i++)
            if(M & (1<<i)) cout << (i + 1) << " ";
        cout << endl;
    }
};

template <>
struct ComboPart<0> {
    void print() {};
};

template <my_uint N>
struct TwoPow {
    enum {value = 2 * TwoPow<N-1>::value};
};

template <>
struct TwoPow<0> {
    enum {value = 1};
};

template <my_uint N>
struct Combos {
    ComboPart<TwoPow<N>::value - 1> part;
    void print() {
        part.print();
    }
};

int main(int argc, char *argv[]) {
    Combos<5> c5 = Combos<5>();
    c5.print();

    return 0;
}

Этот конструирует все комбинации во время компиляции.

Answer 3

Вы хотите найти блок питания

In mathematics, given a set S, the power set (or powerset) of S, written , 
P(S), , is the set of all subsets of S

Существует алгоритм поиска блока питания по этой ссылке .

You basically take first element say 1 and find a all subsets {{},{1}}. Call this 
power set
Take next element 2 and add to powerset and get {{2},{1,2}} and take union
 with powerset.
{{},{1}} U {{2},{1,2}} = {{},{1},{2},{1,2}}

Но это простой способсделать это описано в ответах выше. Здесь - ссылка, которая объясняет это подробно.

Answer 4

Вам нужны комбинации, а не перестановки (т. Е. {1,2} совпадает с {2,1})

C (n, k) = n! / (K! (Nk)!)

Ответ = сумма (k = 1 до n) C (n, k)

      ( i.e. C(n,1)+C(n,2)...+C(n,n) )

Answer 5

Кто-нибудь может предложить быстрый алгоритм?

Алгоритмы могут быть выражены на многих языках, вот мощность, установленная в Haskell:

power [] = [[]]

power (x:xs) = rest ++ map (x:) rest
  where rest = power xs

Answer 6

То, что вы хотите, в комбинаторике называется choose. Это и это должно помочь вам начать.