Как вернуть список всех подмножеств из списка целых чисел, используя Python? - PullRequest
Новая
       29

Как вернуть список всех подмножеств из списка целых чисел, используя Python?

0 голосов
/ 20 марта 2020

Мне дали целочисленный массив A, мне нужно вернуть массив всех его подмножеств. Я пытался решить эту проблему с помощью Backtracking. 

def subset_helper(index, result, A, temp):
    result.append(temp)
    #print(temp)
    for i in range(index,len(A)):
        temp.append(A[i])
        subset_helper(i+1,result,A,temp)
        #backtracking
        temp.pop()
    return    
def subsets(A):
    result = []
    temp = []
    index = 0
    subset_helper(index, result, A, temp)
    return result

Это возвращает мне пустой список. Печать temp дает мне правильный ответ, но проблема просит меня вернуть массив. Я думаю, что временный массив из-за вызова по ссылке меняется на каждой итерации, и это, вероятно, причина, по которой он дает мне список пустого списка. 

Input : [12,13]
Expected Output : [[],[12],[12,13],[13]]
My Output : [[],[],[],[]]

Ответы [ 4 ]

3 голосов
/ 20 марта 2020

Вы можете использовать блок питания для получения нужного выхода. 

iterable=[12,13]
res=list(powerset(iterable))
1 голос
/ 20 марта 2020

Если это не проблема домашней работы, вы можете использовать превосходный модуль itertools для генерации подмножеств 

from itertools import combinations, chain

def get_subsets(integers):
    return list(chain.from_iterable([combinations(integers, i) for i in range(len(integers) + 1)]))

Input: get_subsets([1, 2, 3])
Output: [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
1 голос
/ 20 марта 2020

вы можете попытаться напечатать адрес в subset_helper, и вы можете обнаружить, что ваш temp - это тот же адрес объекта, поэтому ваш результат представляет собой список с таким же значением объекта: 

def subset_helper(index, result, A, temp):
    result.append(temp)
    print(id(temp))
    for i in range(index,len(A)):
        temp.append(A[i])
        subset_helper(i+1,result,A,temp)
        #backtracking
        temp.pop()
    return

output: 

1559293711304
1559293711304
1559293711304
1559293711304
[[], [], [], []]

теперь изменяется, чтобы добавить копию вашего объекта tmp: 

import copy
def subset_helper(index, result, A, temp):
    result.append(copy.copy(temp))
    for i in range(index,len(A)):
        temp.append(A[i])
        subset_helper(i+1,result,A,temp)
        #backtracking
        temp.pop()
    return

и теперь вы добавляете новый объект в список результатов, вы можете увидеть результат, как вы ожидали: 

[[], [12], [12, 13], [13]]
0 голосов
/ 20 марта 2020

Кроме того, с точки зрения алгоритма c вы можете go пройти через все возможные двоичные числа до 2 ** N (N - это длина вашего набора), и принять 1 как указание на то, что элемент должен принадлежат подмножеству: 

A = ["A", "B", "C"]

allSubsets = []
for i in range(2**len(A)):
  n = 1
  subset = []
  for j in range(len(A)):
    if i & n != 0:
      subset.append(A[j])
    n <<= 1
  allSubsets.append(subset)

print(allSubsets)

производит: 

[[], ['A'], ['B'], ['A', 'B'], ['C'], ['A', 'C'], ['B', 'C'], ['A', 'B', 'C']]
...