Алгоритм для: Все возможные способы разбить набор элементов на два набора?

У меня есть n элементов в наборе U (предположим, что он представлен массивом размера n). Я хочу найти все возможные способы разбиения множества U на два множества A и B, где |A| + |Б| = н.

Так, например, если U = {a,b,c,d}, комбинации будут такими:

  1. A = {a} -- B = {b,c,d}
  2. A = {b} -- B = {a,c,d}
  3. A = {c} -- B = {a,b,d}
  4. A = {d} -- B = {a,b,c}
  5. A = {a,b} -- B = {c,d}
  6. A = {a,c} -- B = {b,d}
  7. A = {a,d} -- B = {b,c}

Обратите внимание, что следующие два случая считаются равными, и следует вычислять только один:

Случай 1: A = {a,b} -- B = {c,d}

Случай 2: А = {с, d} -- В = {а, Ь}

Также обратите внимание, что ни одно из множеств A или B не может быть пустым.

Я думаю о том, как реализовать это, просто отслеживая индексы в массиве и перемещая их шаг за шагом. Количество индексов будет равно количеству элементов в множестве A, а множество B будет содержать все оставшиеся неиндексированные элементы.

Мне было интересно, знает ли кто-нибудь о лучшей реализации. Я ищу более высокую эффективность, потому что этот код будет выполняться на довольно большом наборе данных.

Спасибо!


set algorithm combinations
person alguru    schedule 09.08.2011    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Возьмите все целые числа от 1 до 2^(n-1), не включительно. Итак, если n = 4, целые числа от 1 до 7.

Каждое из этих чисел, записанное в двоичном формате, представляет элементы, присутствующие в наборе A. Набор B состоит из оставшихся элементов. Обратите внимание, что поскольку мы идем только к 2 ^ (n-1), а не к 2 ^ n, старший бит всегда устанавливается для набора B; мы всегда помещаем первый элемент в набор B, так как вы хотите, чтобы порядок не имел значения.

person dfan    schedule 09.08.2011
comment
Спасибо за быстрый ответ! Мне нравится этот метод, и я пробовал его в нескольких случаях, и, похоже, он работает хорошо! Мне было интересно, есть ли у вас идеи, где я могу найти (более или менее) формальное доказательство того, почему это работает. - person alguru; 09.08.2011
comment
Каждый элемент x либо находится в наборе A, либо нет, что соответствует тому, равен ли номер бита x 1 или 0. Таким образом, все возможные 2^N подмножеств вашего набора из N значений могут быть представлены N-битным двоичным числом, и мы просто перебирая все N-битные двоичные числа. - person dfan; 09.08.2011