Сегодня мой профессор CPSC назначил викторину в python, тема была рекурсией.
Весь класс застрял на вопросе номер два, который ниже. Никто не смог даже приблизиться к решению.
def sub_set(A):
if A == []: return A
X = sub_set(A[1:])
result = []
for L in X:
result += _____
return _____
Пример кода:
print(sub_set([1, 2])) # [[], [1], [2], [1, 2]]
print(sub_set([1, 2, 3])) # [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Вам разрешено изменять символы подчеркивания, например, мой пример ниже.
Мое решение было настолько далеким от закрытия, что его даже не следует рассматривать:
def sub_set(A):
if A == []: return A
X = sub_set(A[1:])
result = []
for L in X:
result += _____
return result + [A[:1]] + [A] + [A[::2]]
#sub_set([1, 2, 3]) -> [[3], [3], [3], [2], [2, 3], [2], [1], [1, 2, 3], [1, 3]]
Кто-нибудь знает, как это можно решить? Это кажется довольно сложной проблемой, когда у нас есть только 15 минут, чтобы решить эту проблему.
Просто для справки, он сказал, что бросит вопрос, не рассматривая никого в классе - продвинутый класс comp sci примерно из 10 тщательно отобранных студентов - мог бы его решить.
Я думаю, что есть ошибка в вопросе. Базовый регистр для рекурсии неверен.
Множество всех подмножеств пустого множества - это не пустое множество, а множество, содержащее пустое множество.
def sub_set(A):
if A == []: return A
должен быть
def sub_set(A):
if A == []: return [A]
Добавлено: С этим патчем, здесь решение:
def sub_set(A):
if A == []: return [A]
X = sub_set(A[1:])
result = []
for L in X:
result += [L, A[0:1] + L]
return result
Я не считаю, что это разрешимо без какого-либо серьезного хакера, потому что базовый случай ошибочен. Для [] должно быть одно подмножество: []. Но return A не возвращает никаких подмножеств.
Итак, вместо того, чтобы просто делать A[:1] + L, вам нужно сделать [A[:1] + L]. И вместо A[:1] + X + result вам нужно сделать [A[:1]] + X + result. Итак:
def sub_set(A):
if A == []: return A
X = sub_set(A[1:])
result = []
for L in X:
result += [A[:1] + L]
return [A[:1]] + X + result
Это все равно оставляет пустой список из подмножеств. И единственный способ исправить это - что-то глупое:
return ([] if [] in X + result else [[]]) + [A[:1]] + X + result
Это, по крайней мере, вернет правильные значения... но в неправильном порядке и с дубликатами всех одноэлементных подмножеств. Вы можете расширить хакерство, если хотите; Я не думаю, что это того стоит.
def sub_set(A):
if A == []: return A
X = sub_set(A[1:])
result = []
for L in X:
result += [L, [A[0]]+L]
return [[A[0]]] + result
print sub_set([1, 2])
>> [[1], [2], [1, 2]]
print sub_set([1, 2, 3])
>> [[1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
def sub_set(A):
if A == []: return A
X = sub_set(A[1:])
result = []
for L in X:
result += [L, A[0:1] + L]
return result if X != [] else [[], A[0:1]]
Это по существу то же самое, что и noa, минус изменение части кода, который вы не должны редактировать.
X - это набор всех подмножеств, которые НЕ включают A[0]. Это означает, что они также находятся в subset(A). Отсутствие всех подмножеств, содержащих DO A[0], которые вы можете получить, добавив A[0] к каждому из элементов в X.
Итак, ваш первый пробел будет A[0] + L
И ваш второй будет result + X
Не решение, которое вы ищете, но здесь работает решение с использованием yield:)
def powerset(A):
if A:
for L in powerset(A[1:]):
yield L
yield A[:1] + L
else:
yield []
это возможное решение. он возвращает правильные значения, но не обязательно в том же порядке:
def sub_set(A):
if A == []: return A
X = sub_set(A[1:])
result = []
for L in X:
result += [ A[:1] +L ]
return [[]] + X[1:] + (result or [A[:1]])
Эффективно, что это делает, для каждого слоя мы разбиваем исходный список на две части: начальный элемент и остальную часть списка. Мы получаем все подмножества остальной части списка, добавляем первый элемент к каждой части, добавляем [] и возвращаем его.
Пример потока:
[1,2,3] -> A0 = [1], A1X =[2,3] ->
[2,3] -> A0 = [2], A1X = [3] ->
[3] -> A0 = [3], A1X = [] ->
[] -> return []
[3] * [] = []. return [ [], [3] ]
[2] * [[], [3]] = [[2], [2,3]]. return [ [] + [[3]] + [[2], [2,3]] ]
[1] * [ [], [3], [2], [2,3] ] = [[1], [1,3], [1,2], [1, 2, 3] ]
return [ [] + [[], [3], [2], [2,3]] + [[1], [1,3], [1,2], [1,2,3]]
Общий поток [] + A0 * [подмножество] + [подмножество]. Вопросы, которые нужно посмотреть, это то, что подмножество всегда начинается с [] - поэтому вы получите его дважды, если вы его не удалите, и убедитесь, что вы не дублируете A0, когда он уже существует (в качестве [A0] + [] == [A0], и у вас всегда есть [A0] в списке), но на самой первой итерации (после возвращения []) вам нужно специально включить его.