Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > как перебрать все комбинации элементов?

Автор: D@mon 2.4.2005, 12:54

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

Автор: MBo 2.4.2005, 13:26

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

Автор: D@mon 3.4.2005, 11:15

спасибо

Автор: yaja 4.4.2005, 18:09

Была у меня такая задачка на одной из контрольных. Написал рекурсией, но легко переделать и без её использования smile

По научному задача состоит в том, что нужно перебрать в лексеграфическом порядке все подмножества данного множества из 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;
}

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

Автор: Kolia 16.5.2005, 17:08

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

Автор: yaja 17.5.2005, 21:25

Цитата

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

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