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

Question

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

Так, например, если 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: A = {c, d} - B = {a, b}

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

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

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

Спасибо!

Answer 1

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

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