Как сгенерировать набор мощности заданного набора?

Power set of a set A is the set of all of the subsets of A.

Не самое дружелюбное определение в мире, но пример поможет:

Например. для {1, 2} подмножества: {}, {1}, {2}, {1, 2}

Таким образом, набор мощности равен {{}, {1}, {2}, {1, 2}}

Пусть это решение будет обозначено битом (1/0).

Таким образом, чтобы сгенерировать {1}, вы возьмете 1 и бросите 2 (10).

В аналогичных строках вы можете написать битовый вектор для всех подмножеств:

• {} -> 00
  {1} -> 10
  {2} -> 01
  {1,2} -> 11

Повторюсь: подмножество, если оно сформировано путем включения некоторых или всех элементов исходного множества. Таким образом, чтобы создать подмножество, вы переходите к каждому элементу, а затем решаете, сохранить его или отбросить. Это означает, что для каждого элемента у вас есть 2 решения. Таким образом, для набора вы можете получить 2^N различных решений, соответствующих 2^N различным подмножествам.

Посмотрим, сможешь ли ты забрать его отсюда.

Создайте набор мощности: {"A", "B", "C"}.

Псевдокод:

val set = {"A", "B", "C"}

val sets = {}

for item in set:
  for set in sets:
    sets.add(set + item)
  sets.add({item})
sets.add({})

Объяснение алгоритма:

1) Инициализировать sets пустым набором: {}.

2) Перебрать каждый элемент в {"A", "B", "C"}

3) Переберите каждый set в вашем sets.

3.1) Создайте новый набор, который является копией set.

3.2) Добавьте item к new set.

3.3) Добавьте new set к sets.

4) Добавьте item к вашему sets.

4) Итерация завершена. Добавьте пустой набор в свой resultSets.

Пошаговое руководство:

Давайте посмотрим на содержимое sets после каждой итерации:

Итерация 1, элемент = "А":

sets = {{"A"}}

Итерация 2, элемент = "B":

sets = {{"A"}, {"A", "B"}, {"B"}}

Итерация 3, элемент = "C":

sets = {{"A"}, {"A", "B"}, {"B"}, {"A", "C"}, {"A", "B", "C"}, {"B", "C"}, {"C"}}

Итерация завершена, добавьте пустой набор:

sets = {{"A"}, {"A", "B"}, {"B"}, {"A", "C"}, {"A", "B", "C"}, {"B", "C"}, {"C"}, {}}

Размер наборов 2^|set| = 2 ^ 3 = 8, что правильно.

Пример реализации на Java:

public static <T> List<List<T>> powerSet(List<T> input) {
  List<List<T>> sets = new ArrayList<>();
  for (T element : input) {
    for (ListIterator<List<T>> setsIterator = sets.listIterator(); setsIterator.hasNext(); ) {
      List<T> newSet = new ArrayList<>(setsIterator.next());
      newSet.add(element);
      setsIterator.add(newSet);
    }
    sets.add(new ArrayList<>(Arrays.asList(element)));
  }
  sets.add(new ArrayList<>());
  return sets;
}

Ввод: [A, B, C]

Выход: [[A], [A, C], [A, B], [A, B, C], [B], [B, C], [C], []]

Набор мощности - это просто набор всех подмножеств для данного набора. Он включает все подмножества (с пустым множеством). Известно, что в этом наборе 2^N элементов, где N — количество элементов в исходном наборе.

Для построения силового набора можно использовать следующее:

• Создайте цикл, который перебирает все целые числа от 0 до 2^N-1
• Перейти к двоичному представлению для каждого целого числа
• Каждое двоичное представление представляет собой набор из N битов (для меньших чисел добавьте ведущие нули). Каждый бит соответствует включению определенного члена множества в текущее подмножество.

Пример, 3 числа: a, b, c

number binary  subset
0      000      {}
1      001      {c}
2      010      {b}
3      011      {b,c}
4      100      {a}
5      101      {a,c}
6      110      {a,b}
7      111      {a,b,c}

Ну, вам нужно сгенерировать все подмножества. Для набора размера n существует 2ⁿ подмножеств.

Один из способов — перебрать числа от 0 до 2ⁿ - 1 и преобразовать каждое в список двоичных цифр, где 0 означает исключить этот элемент, а 1 означает включить его.

Другой способ - с рекурсией, разделяй и властвуй.

Генерация всех комбинаций набора (с включением или без элемента). поясню на примере: 3 предмета в наборе (или списке). Возможным подмножеством будет:

000   
100   
010   
001
110
101
011
111   

Результат равен 2^(количество элементов в наборе).

Таким образом, мы можем сгенерировать все комбинации из N элементов (с помощью python) следующим образом:

def powerSet(items):

    N = len(items)

    for i in range(2**N):

        comb=[]
        for j in range(N):
            if (i >> j) % 2 == 1:
                comb.append(items[j])
        yield comb

for x in powerSet([1,2,3]):
    print (x)

Вы получите что-то подобное, реализовав ответ с самым высоким рейтингом.

def printPowerSet(set,set_size):

    # set_size of power set of a set
    # with set_size n is (2**n -1)
    pow_set_size = (int) (math.pow(2, set_size));
    counter = 0;
    j = 0;

    # Run from counter 000..0 to 111..1
    for counter in range(0, pow_set_size):
        for j in range(0, set_size):

            # Check if jth bit in the 
            # counter is set If set then 
            # pront jth element from set 
            if((counter & (1 << j)) > 0):
                print(set[j], end = "");
        print("");

Решение C#

Временная сложность и пространственная сложность: O (n * 2 ^ n)

 public class Powerset
    {


        /*
         P[1,2,3] = [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
             */
        public  List<List<int>> PowersetSoln(List<int> array)
        {

            /*
                We will start with an empty subset
                loop through the number in the array
                         loop through subset generated till and add the number to each subsets

              */

            var subsets = new List<List<int>>();
            subsets.Add(new List<int>());

            for (int i = 0; i < array.Count; i++)
            {
                int subsetLen = subsets.Count; 
                for (int innerSubset = 0; innerSubset < subsetLen; innerSubset++)
                {
                    var newSubset = new List<int>(subsets[innerSubset]);
                    newSubset.Add(array[i]);
                    subsets.Add(newSubset);
                }

            }

            return subsets;
        }
    }

Пример кода Java:

void printPowerSetHelper(String s, String r) {
    if (s.length() > 0) {
        printPowerSetHelper(s.substring(1), r + s.charAt(0));
        printPowerSetHelper(s.substring(1), r);
    } 
    if (r.length() > 0) System.out.println(r);
}

void printPowerSet(String s) {
    printPowerSetHelper(s,"");
}