Question

我很难把系数组合起来。基本上我有一个项目清单,想为它们获得所有独特的系数组合,比如:

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

我不确定这样做的最佳方式(动力编程、循环、brute force、etc.),

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个项目.我是否最好使用动态编程)?

Answer 1

您的错误就是这条线:

coeff_temp = coeff

这不会生成 coeff 的副本: 它会引用同一个对象。当您在下一行修改它时 :

coeff_temp[k] = data

你重新修改你目前插入的每一份 - 他们都是相同的名单!

要实际复制列表, 请使用 :

coeff_temp = list(coeff)

或

coeff_temp = coeff[:]

这是解决你问题的最好办法:

imp或t itertools
data = {
    "dog": xrange(1, 5),
    "cat": xrange(1, 5)
    #add m或e here...
}
combinations = (dict(zip(data.keys(), c)) f或 c in itertools.product(*data.values()))

f或 c in combinations:
    print c

Answer 2

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

也就是您之后的编号。记住组合的数量将是 < code> (len(data))****** appto ,随着数据的增加和不断增长,这些组合会爆炸性地增加。

" 强力 " 编辑:如前所述,实现这一点的另一种途径是:

from itertools import product

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

Answer 3

在我看来,你所要的是一个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数字,等等。

Answer 4

尝试查看 libertools lib http://docs.python.org/library/itertools.html 在哪里能找到组合函数,它必须帮助您。

Answer 5

如果您想要组合,那么循环几乎是所有时间的正确答案。

您的代码存在问题 : 在 < code> recursion 函数中, 当您说 < code> coeff_temp = coeff 时, 您正在复制 < em> reference 到 < code > coeff , 所以您每次都在附加相同的列表。这就是为什么。否则, 方法对我来说似乎很好。

更改线条

coeff_temp = coeff

至

coeff_temp = list(coeff)

至copy the list, and keep going on from there.

Itertools 模块是组合的精细解决方案。

友情链接