我对如何解决这个问题有点困惑。我知道我想做什么，但我无法思考如何合理地解决这个问题。
假设我有一个清单：
numlist = [10,4]
我在另一个列表中有以下值：
datalist = [10,5,4,2,1]
如何仅使用
numlist中的数字来分解datalist中的数字？答案的一个例子是：
10, 4 10, 2,2 10, 2,1,1 10, 1,1,1,1 5,5, 4 5,5, 2,2
...and so on.
I understand how to do this vaguely. make a for loop, for each entry in the list and compare if it can be divided by the datalist, and if so print the result. I think I need recursions which is where I'm having trouble understanding.
here's my code so far (I have some print statements for troubleshooting):
def variableRecursion(self, solutionList):
#solution list contrains ['red', 2, 'green', 1] which means 2 reds(value 4) and 1 green(value 2)
#adding fake lookup list for now, in real code, I can use real data because I am reversing the order
list = [('red', 4), ('green', 2), ('blue', 1) ]
for x1, x2 in zip(solutionList[::2], solutionList[1::2]):
for x in list:
for y1, y2 in zip(x[::2], x[1::2]):
#print x1, x2
keyName = x1
keyShares = x2
keyValue = lookup.get_value(x1)
if ((keyValue%y2) == 0) and (keyValue != y2):
tempList = []
#print 'You can break ', keyName, keyValue, ' with ', y1, y2, ' exactly ', keyValue/x2, ' times.'
#newKeyShares = keyShares - 1
for a1, a2 in zip(solutionList[::2], solutionList[1::2]):
#print a1, a2
print 'You can break ', keyName, keyValue, ' with ', y1, y2, ' exactly ', keyValue/y2, ' times.'
newKeyShares = keyShares - 1
print 'there is a match', a1, a2, ' but we will change the shares to ', newKeyShares
print a1
if (a1 == keyName):
print 'a'
tempList.append([(keyName), (newKeyShares)])
elif (a1 == y1):
print 'b'
tempList.append([(y1), (a2+keyValue/y2)])
else:
print 'c'
try:
tempList.append([(y1), (a2+keyValue/y2)])
except e:
tempList.append([(a1), (a2)])
print tempList
appendList.appendList(tempList)
tempList = []
#exit()
#print solutionList
最佳答案
这个问题与euler项目的Problem 31非常相似：“使用任何数量的硬币，可以用多少种不同的方法来制作2英镑？”。仅在您的示例中，您要求枚举所有可以将数字相加得到10和4的方法。
解决这个问题的最好方法是首先尝试只分解一个数字。让我们用数字[5,4,2,1]来看看五个人可能的分手：
[5]
[4,1]
[2,2,1]
[2,1,1,1]
[1,1,1,1,1]
下面的python代码将为您提供这些组合的列表：
def possibleSplits(value,validIncrements):
ret = []
for increment in validIncrements:
if increment > value:
continue
if increment == value:
ret.append([increment])
continue
if increment < value:
remainder = value - increment
toAdd = possibleSplits(remainder, validIncrements)
for a in toAdd:
ret.append([increment] + a)
return ret
这段代码假设相同答案的不同顺序应该被视为不同的。例如，拆分5时，[4,1]和[1,4]都将显示为解决方案。如果愿意，可以将其限制为只包含按数字顺序排列的答案（因此会出现[1,4]，但不会出现[4,1]）
def orderedPossibleSplits(value, validIncrements):
ret = []
splits = possibleSplits(value, validIncrements)
for value in splits:
value.sort()
if value not in ret:
ret.append(value)
return ret
现在，您可以使用它来查找10的可能拆分和4的可能拆分，并组合它们：
increments = [10, 5, 4, 2, 1]
tenSplits = orderedPossibleSplits(10, increments)
fourSplits = orderedPossibleSplits(4, increments)
results = []
for tenSplit in tenSplits:
for fourSplit in fourSplits:
results.append(tenSplit + fourSplit)
编辑：如评论中所述，调用值为100的possiblesplits非常慢-超过10分钟并计数。之所以出现这种情况，是因为possiblesplits（100）将递归地调用possiblesplits（99）、possiblesplits（98）和possiblesplits（96），每个possiblesplits都调用三个自己的possiblesplits，以此类推。我们可以用DATALIS[1，2，4]和大N AS逼近可能的PLS（n）的处理时间。
处理时间（n）=c+处理时间（n-1）+处理时间（n-2）+处理时间（n-4）
一段恒定的时间。
所以可能存在的相对时间是
N 1 | 2 | 3 | 4 | 5 ... 20 ... 98 | 99 | 100
Time 1 | 1 | 1 | 4 | 7 ... 69748 ... 30633138046209681029984497 | 56343125079040471808818753 | 103631163705253975385349220
假设可能性（5）需要7纳秒，可能性（100）需要3*10^9年。对于大多数实用程序来说，这可能是一段不合适的长时间然而，我们可以利用记忆来减少这一时间。如果我们保存先前计算的呼叫的结果，我们可以得到线性时间复杂度，减少可能性（100）到100纳秒。
评论还指出，orderedppossiblesplits（100）的预期值大约有700个元素因此，possiblesplits（100）的元素数量要大得多，因此即使使用memoization也不切实际。相反，我们将丢弃它并重写OrderedPossibleSplits以使用备忘录，而不依赖于PossibleSplits。
#sorts each element of seq and returns it
def orderedInnerLists(seq):
return map(sorted, seq)
#returns a copy of seq with duplicates removed
def removeDuplicates(seq):
ret = []
for value in seq:
if value not in ret:
ret.append(value)
return ret
memoizedResults = {}
def orderedPossibleSplits(value,validIncrements):
memoizeKey = (value, tuple(validIncrements))
if memoizeKey in memoizedResults:
return memoizedResults[memoizeKey]
ret = []
for increment in validIncrements:
if increment > value:
continue
if increment == value:
ret.append([increment])
continue
if increment < value:
remainder = value - increment
toAdd = orderedPossibleSplits(remainder, validIncrements)
for a in toAdd:
ret.append([increment] + a)
memoizeValue = removeDuplicates(orderedInnerLists(ret))
memoizedResults[memoizeKey] = memoizeValue
return memoizeValue
在我的机器上，OrderedPossibleSplits（100，[1,2,4]）大约需要10秒——比我们最初30亿年的运行时间有了很大的改进。
关于python - 如何从列表中分解一个数字？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7519259/