генерация подмножеств заданной размерности в множестве

[carlos0n]

Здравствуйте.
Необходимо написать метод, получающий на вход размерность подмножеств, а на выходе выдающий эти подмножества.
т.е. есть массив длинны n и надо получить все подмножества длинны к примеру n/2. (1,2) и (2,1) - являются одинаковыми подмножествами и нужно получить только одно, т.е. порядок элементов в подмножестве не учитывается. Желательно бы алгоритм без повторяющихся, иначе при больших n становится очень много мусора.
Помогите плз с алгоритмом.

[carlos0n]

Я видимо не совсем в тот раздел форума написал.
Админы, перенесите в "Реализация, исходники, языки", если сочтёте нужным.

ну можно к примеру тупо рекурсией. полно таких алгоритмов. только не подмножествами это называют, а комбинациями.
подробное иллюстрированное руководство: Кнут, Art of Computer Programming, Volume 4 Fascicle 3, Generating All Combinations and Partitions (2005)

или сочетаниями

[carlos0n]

вы не подскажите, где можно бесплатно скачать эту книгу?
я понимаю, что алгоритмы есть, но вот я пока не одного, нормально объяснённого не встретил.
тупо рекурсией, это в чём она будет заключаться? если это так тупо и алгоритмов полно, то скажите хотя бы один))
по данной ссылке есть несколько кодов, но я не понимаю их синтаксис.
перепишите на что нибудь си-подобное плз, буду оч признателен.
http://www.linux.org.ru/forum/development/3361427

[carlos0n]

в общем то можно перебирать индексы таким образом (при учёте, что в массиве нет повторяющихся эл-тов)

0 1 2 3 4 5 6 7 - индексы массива

печатаем все подмножества размерности 5
тогда надо распечатывать эл-ты с индексами вида:

0 1 2 3 4
0 1 2 3 5
0 1 2 3 6
0 1 2 3 7
0 1 2 4 5
0 1 2 4 6
............
3 4 5 6 7

думаю алгоритм понятен по примеру.
но я не могу чего то сообразить как это закодить))

ну вот к примеру все сочетания из 6 по 3:

yoda@tatooine:~$ cat p.cc
#include <cstdio>

const int N = 6, K = 3;
int a[K];

void rec(int i)
{
    if (i == K) {
        for (int j = 0; j < K; j++)
            printf("%d ", a[j]);
        printf("\n");
    } else {
        for (a[i] = (i > 0 ? a[i-1] + 1 : 1); a[i] < N; a[i]++)
            rec(i + 1);
    }
}

int main()
{
    int a[N];
    rec(0);
}
yoda@tatooine:~$ ./p
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

Поправка:

        for (a[i] = (i > 0 ? a[i-1] + 1 : 1); a[i] <= N; a[i]++)

1 2 3 
1 2 4 
1 2 5 
1 2 6 
1 3 4 
1 3 5 
1 3 6 
1 4 5 
1 4 6 
1 5 6 
2 3 4 
2 3 5 
2 3 6 
2 4 5 
2 4 6 
2 5 6 
3 4 5 
3 4 6 
3 5 6 
4 5 6

[carlos0n]

спасибо большое! очень мне помогли!