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

Я учусь на собеседование, и я наткнулся на этот вопрос онлайн в разделе "Математика".

Сгенерировать набор мощности заданного набора:

int A[] = {1,2,3,4,5};  
int N = 5; 
int Total = 1 << N;
for ( int i = 0; i < Total; i++ ) { 
 for ( int j = 0; j < N; j++) {
  if ( (i >> j) & 1 ) 
      cout << A[j]; 
   } 
 cout <<endl;

 }

Пожалуйста, я не хочу явного ответа. Я просто хочу уточнения и подсказки о том, как подойти к этой проблеме.

Я проверил алгоритм установки мощности на google, и я до сих пор не понимаю, как решить эту проблему.

Кроме того, кто-то может повторить то, что задает вопрос.

Спасибо.

Ответ 1

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 различным подмножествам.

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

Ответ 2

Набор мощности - это всего лишь набор всех подмножеств для данного набора. Он включает все подмножества (с пустым множеством). Хорошо известно, что в этом наборе есть 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}

Ответ 3

Создайте блок питания: {"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, пункт = "A":

sets = {{"A"}}

Итерация 2, пункт = "B":

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

Итерация 3, item = "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], []]

Ответ 4

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

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

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

Ответ 5

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

Результат равен 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)

Ответ 6

Пример кода 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,"");
}