Сумма подмножества Python
Я пытаюсь написать функцию, которая не только определяет, прибавляет ли сумма подмножества набора к желаемому целевому числу, но также печатает подмножество, которое является решением.
Вот мой код для определения наличия подмножества:
def subsetsum(array,num):
if num == 0 or num < 1:
return False
elif len(array) == 0:
return False
else:
if array[0] == num:
return True
else:
return subsetsum(array[1:],(num - array[0])) or subsetsum(array[1:],num)
Как я могу изменить это для записи самого подмножества, чтобы я мог его распечатать? Заранее спасибо!
7 ответов
Основываясь на вашем решении:
def subsetsum(array,num):
if num == 0 or num < 1:
return None
elif len(array) == 0:
return None
else:
if array[0] == num:
return [array[0]]
else:
with_v = subsetsum(array[1:],(num - array[0]))
if with_v:
return [array[0]] + with_v
else:
return subsetsum(array[1:],num)
Слегка измененная версия ответа Сэми для печати всех возможных комбинаций.
def subset(array, num):
result = []
def find(arr, num, path=()):
if not arr:
return
if arr[0] == num:
result.append(path + (arr[0],))
else:
find(arr[1:], num - arr[0], path + (arr[0],))
find(arr[1:], num, path)
find(array, num)
return result
Вы можете изменить свой подход, чтобы сделать это более легко, что-то вроде:
def subsetsum(array, num):
if sum(array) == num:
return array
if len(array) > 1:
for subset in (array[:-1], array[1:]):
result = subsetsum(subset, num)
if result is not None:
return result
Это вернет либо действительное подмножество, либо None,
Думаю, я добавлю другое решение в смесь.
Мы можем сопоставить каждый выбор подмножества списка двоичному номеру (с добавлением 0), где 0 означает, что элемент не занял соответствующую позицию в списке, а 1 означает, что он взят.
Так маскировка [1, 2, 3, 4] с 0101 создает подсписок [2, 4],
Таким образом, генерируя все 0-дополненные двоичные числа в диапазоне от 0 до 2^LENGTH_OF_LIST, мы можем выполнить итерацию всех выборок. Если мы используем эти выборки подсписка в качестве масок и суммируем выборку - мы можем знать ответ.
Вот как это делается:
#!/usr/bin/env python
# use a binary number (represented as string) as a mask
def mask(lst, m):
# pad number to create a valid selection mask
# according to definition in the solution laid out
m = m.zfill(len(lst))
return map(lambda x: x[0], filter(lambda x: x[1] != '0', zip(lst, m)))
def subset_sum(lst, target):
# there are 2^n binary numbers with length of the original list
for i in xrange(2**len(lst)):
# create the pick corresponsing to current number
pick = mask(lst, bin(i)[2:])
if sum(pick) == target:
return pick
return False
print subset_sum([1,2,3,4,5], 7)
Выход:
[3, 4]
Чтобы вернуть все возможности, мы можем использовать генератор (единственные изменения в subset_sum, с помощью yield вместо return и удаление return False охранник):
#!/usr/bin/env python
# use a binary number (represented as string) as a mask
def mask(lst, m):
# pad number to create a valid selection mask
# according to definition in the solution laid out
m = m.zfill(len(lst))
return map(lambda x: x[0], filter(lambda x: x[1] != '0', zip(lst, m)))
def subset_sum(lst, target):
# there are 2^n binary numbers with length of the original list
for i in xrange(2**len(lst)):
# create the pick corresponsing to current number
pick = mask(lst, bin(i)[2:])
if sum(pick) == target:
yield pick
# use 'list' to unpack the generator
print list(subset_sum([1,2,3,4,5], 7))
Выход:
[[3, 4], [2, 5], [1, 2, 4]]
Примечание. Хотя заполнение нулями маски может не сработать, так как она будет просто выбирать элементы исходного списка в обратном порядке - я не проверял и не использовал его.
Я не использовал его, так как для меня менее очевидно (что для меня), что происходит с такой подобной треной маской (1, 0 или ничего), и я, скорее, все четко определил.
Немного обновлен приведенный ниже код, чтобы вернуть все возможные комбинации для этой проблемы. Фрагмент в ветке выше не будет печатать все возможные комбинации, когда ввод задан как подмножество ([4,3,1],4)
def subset(array, num):
result = []
def find(arr, num, path=()):
if not arr:
return
if arr[0] == num:
result.append(path + (arr[0],))
else:
find(arr[1:], num - arr[0], path + (arr[0],))
find(arr[1:], num, path)
find(array, num)
return result
Вместо рекурсии вы можете использовать итеративный подход.
def desiredSum(array, sum):
numberOfItems = len(array)
storage = [[0 for x in range(sum + 1)] for x in range(numberOfItems + 1)]
for i in range(numberOfItems + 1):
for j in range(sum + 1):
value = array[i - 1]
if i is 0: storage[i][j] = 0
if j is 0: storage[i][j] = 1
if value <= j:
noTake = storage[i - 1][j]
take = storage[i - 1][j - value]
storage[i][j] = noTake + take
return storage[numberOfItems][sum]
Немного другой подход к печати всего подмножества через рекурсию.
def subsetSumToK(arr,k):
if len(arr)==0:
if k == 0:
return [[]]
else:
return []
output=[]
if arr[0]<=k:
temp2=subsetSumToK(arr[1:],k-arr[0]) #Including the current element
if len(temp2)>0:
for i in range(len(temp2)):
temp2[i].insert(0,arr[0])
output.append(temp2[i])
temp1=subsetSumToK(arr[1:],k) #Excluding the current element
if len(temp1)>0:
for i in range(len(temp1)):
output.append(temp1[i])
return output
arr=[int(i) for i in input().split()]
k=int(input())
sub=subsetSumToK(arr,k)
for i in sub:
for j in range(len(i)):
if j==len(i)-1:
print(i[j])
else:
print(i[j],end=" ")