做一个范围的系数组合？

我在制作系数组合时遇到了麻烦。基本上我有一个项目清单，并希望得到系数的所有独特的组合，他们是这样的：做一个范围的系数组合？

dog:1 cat:1 
dog:2 cat:1 
dog:3 cat:1 
dog:1 cat:2 
dog:2 cat:2

我真的不知道这样做（动态规划的最佳方式，递归，蛮力，等等。），所以我试图做一个递归开始：

list = ["dog", "cat"] 

coeff = [1] * len(list) 
main_queue = [] 

def recursion(k, list): 
    for item in list[0:k-1]: 
     for data in range(5): 
      coeff_temp = coeff 
      coeff_temp[k] = data 
      main_queue.append(coeff_temp) 
      #print item, data 

    if k == (len(list)-1): 
     return 
    else: 
     recursion(k+1, list) 

recursion(0, list) 

print "*" * 30 

for x in main_queue: 
    print x

输出为：

****************************** 
[4, 1] 
[4, 1] 
[4, 1] 
[4, 1] 
[4, 1]

它只是改变了我提出的主要队列中的最后一项。我究竟做错了什么？

p.s.这是做到这一点的最佳方式（范围在1-5之间，列表中会有大约20-30个项目..我最好使用动态编程）？

来源

2012-05-22 Error_404

我不明白你的描述你想要完成什么。 – murgatroid99

请提供一个*完整的例子，以明确指定输入和预期输出。 – NPE

@ murgatroid99我有一个预期输出的例子。你有什么理解上的麻烦？ –

你的错误是这行：

coeff_temp = coeff

这并不使coeff副本：说对同一对象的引用。当您在下一行修改它时：

coeff_temp[k] = data

您正在修改您插入的每一个目前为止 - 它们都是相同的列表！

要真正复制列表中，使用：

coeff_temp = list(coeff)

或

coeff_temp = coeff[:]

这里是你的问题的最佳解决方案：

import itertools 
data = { 
    "dog": xrange(1, 5), 
    "cat": xrange(1, 5) 
    #add more here... 
} 
combinations = (dict(zip(data.keys(), c)) for c in itertools.product(*data.values())) 

for c in combinations: 
    print c

来源

2012-05-22 16:29:25 Eric

谢谢埃里克，我意识到我犯了另一个错误以及我用列表作为变量，所以我用你的例子，并改变了变量名，但现在我得到一个错误'TypeError：'类型'对象是不可迭代的第一个for循环在递归函数 –

@Error_404然后你仍然使用'list'作为变量。 – Eric

你的权利，有一个我错过的例子。现在看起来好像有些工作，但是有重复的结果。 –

试试看itertools lib http://docs.python.org/library/itertools.html在哪里可以找到组合（）函数，它必须帮助你。

来源

2012-05-22 16:21:52 Denis

如果你想要组合，那么递归在几乎所有的时候都是正确的答案。

没有您的代码有问题：里面的recursion功能，当你说coeff_temp = coeff要复制的参考到coeff，所以你的每一次只是追加相同的列表。这就是为什么。否则，该方法对我来说似乎很好。

行

coeff_temp = coeff

更改为

coeff_temp = list(coeff)

复制的清单，并保持从那里上。

itertools模块是一个很好的组合解决方案。

来源

2012-05-22 16:27:10

对不起，@Eric已经回答了同样的问题，因为我正在撰写我的答案，所以直到我发布时才看到它。信用应该是他的。 –

你刚刚在那里，而我正在打字 - 看看时间。然而，你的推理是错误的 - “coeff”是全球性的事实是无关紧要的。 – Eric

@Eric：当然，我的解释还不够清楚。我正在试着说完全一样的你，他使用了对同一个列表的引用。我现在看到它不是很清楚，我已经修复了它。感谢您的评论。 –

data = ["dog", "cat"] 
upto = 4 

def all_combos(items, upto): 
    if items < 1: 
     yield [] 
    else: 
     for r in range(upto+1): 
      for rest in all_combos(items-1, upto): 
       yield [r] + rest 

for coeffs in all_combos(len(data), upto): 
    print ", ".join("{}s: {}".format(n, coeff) for n,coeff in zip(data,coeffs))

dogs: 0, cats: 0 
dogs: 0, cats: 1 
dogs: 0, cats: 2 
dogs: 0, cats: 3 
dogs: 0, cats: 4 
dogs: 1, cats: 0 
dogs: 1, cats: 1 
dogs: 1, cats: 2 
dogs: 1, cats: 3 
dogs: 1, cats: 4 
dogs: 2, cats: 0 
dogs: 2, cats: 1 
dogs: 2, cats: 2 
dogs: 2, cats: 3 
dogs: 2, cats: 4 
dogs: 3, cats: 0 
dogs: 3, cats: 1 
dogs: 3, cats: 2 
dogs: 3, cats: 3 
dogs: 3, cats: 4 
dogs: 4, cats: 0 
dogs: 4, cats: 1 
dogs: 4, cats: 2 
dogs: 4, cats: 3 
dogs: 4, cats: 4

这就是你所追求的。 请记住组合的数量将为(len(data))**upto，随着数据的增加爆炸式增长。

编辑：如已经指出的那样，另一种方式来实现这一目标是

from itertools import product 

def all_combos(items, upto): 
    return product(*(range(upto+1) for i in range(items)))

来源

2012-05-22 16:42:55

'itertools.product'不会是一个更简单的方法来获得这个输出吗？（我对OP想要的内容普遍存在困惑;给出的例子与他后来的评论不符。） – DSM

谢谢Hugh这个作品，而且是我想要的。 –

@DSM：当然。看我的答案如何使用它。 – Eric

在我看来，你需要的是一个N位基-M数，其中N是多少的项目在列表中，M是每个可能值的数量。例如，如果列表中有3个项目，并且每个项目需要1到4的值，则可以使用3位数字的3位数字。由于您的第一个数字是1，因此您将其分配给每个数字，并将其分配给列表项目。

在此，第一列是实际数量为你计数，并且所述第二列被添加到每个数字用1相同的号码，然后分配给每个三只动物的值：

000 111  cat 1 dog 1 hamster 1 
001 112  cat 1 dog 1 hamster 2 
002 113  cat 1 dog 1 hamster 3 
010 121  cat 1 dog 2 hamster 1 
011 122  cat 1 dog 2 hamster 2 
012 123  cat 1 dog 2 hamster 3 
020 131  cat 1 dog 3 hamster 1 
021 132  cat 1 dog 3 hamster 2 
022 133  cat 1 dog 3 hamster 3 
100 211  cat 2 dog 1 hamster 1

其余3位数的基数为3的数字。

来源

2012-05-22 16:42:57

做一个范围的系数组合？

回答

相关问题