*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

воскресенье, 13 июня 2010 г.

Перебор всех разбиений множества на два подмножества

Допустим, есть массив (вектор) v, и надо перебрать все возможные варианты разделения его компонент на два непересекающихся подмножества.

Если элементов множества немного, а именно - их количество умещается в разрядную сетку вашего компьютера, например, не более 32-х или 64-х, то есть элегантный способ организовать перебор следующим образом:

vector<int> v(20); // Исходное множество

// Всего вариантов будет: 2^(v.size())-1.
for (int i = 1; i < (1 << v.size()); ++i) {
  vector<int> left, right;
  for (int j = 0; j < v.size(); ++j) {
    if ((i >> j) & 1)
      left.push_back(v[j]);
    else
      right.push_back(v[j]);
  }

  // Текущий вариант множеств left и right готов для обработки.
  ...
}

3 комментария:

  1. Побитовые сдвиги типа для ускорения и тут же рядом лежит вызов size() - это ужасно ))

    ОтветитьУдалить
  2. добрый вечер.

    вы не подскажете, если необходимо разбиение на k непустых подмножеств, то как это оптимально организовать?

    ОтветитьУдалить