Есть N элементов, N - заранее не известно, нужно перебрать элементы след. образом:
по одному, по два и т.д.
Алгоритм д.б. простой, но что никак не сообразить

Всех таких комбинаций, как легко увидеть - 2^N - в наборе элемент либо есть, либо его нет, так что можно просто сделать цикл от 0 (или от 1, если пустой набор не нужен) до 2^N-1.
Единичный бит на k-ом месте в счетчике цикла означает присутствие элемента.
Требование к порядку - сначала по одному, потом по два - маленько усложняет логику, но не настолько, чтобы не догадаться. Возможны как рекурсивные решения (проще, но при больших числах не очень эффективно), так и нерекурсивные.

спасибо

Была у меня такая задачка на одной из контрольных. Написал рекурсией, но легко переделать и без её использования
По научному задача состоит в том, что нужно перебрать в лексеграфическом порядке все подмножества данного множества из n элементов(у меня в проге считается, что все элементы-натуральные числа в диапозоне 1..n)

Код

#include <stdio.h> int n; // количество элементов bool* s; // типа говорит, участвует i-ый елемент в данном подмножестве или нет void step(int k = -1) { // выводим очередное подмножество   for (int i = 0; i < n; i++) {     if (s[i]) printf("%i", i + 1);   } // каждое подмножество на одной строке ))   if (k != -1)     printf("\n"); // генерируем следущеее подмножество   for (i = k + 1; i < n; i++) {     s[i] = true;     step(i);     s[i] = false;   } } int main() {   freopen("subset.in", "r", stdin);   freopen("subset.out", "w", stdout);   scanf("%i", &n);   s = new bool[n]; // выводим пустое подмножество(если не надо удали)   printf("\n");   int l = -1;   step();   delete[] s;   fclose(stdin);   fclose(stdout);   return 0; }

Если чтобы работало быстрее, то не выводи очередное подмножество, а сливай его в буфер, а потом одним разом выводи буфер и избавься от рекурсии

Это сообщение отредактировал(а) yaja - 10.4.2005, 11:10

А комп не загнется все варианты перебирать? Возьми строку из 20 элементов. Количество вариантов - 20! (факториал). Число далеко не маленькое.

Цитата

Возьми строку из 20 элементов

Если верить словам моего препода по физике, то для вычисления каких-то величин из квантовой механики необходимо перебрать все перестановки для нескольких тысяч элементов...