-1

我无法组合系数。基本上我有一个项目列表，并希望为它们获取所有独特的系数组合，如下所示：

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]

它只会更改我创建的主队列中的最后一个条目。我究竟做错了什么？

ps这是最好的方法吗（范围在1-5之间，列表中大约有20-30个项目..我最好使用动态编程）？

4

5 回答 5

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

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

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

from itertools import product

def all_combos(items, upto):
    return product(*(range(upto+1) for i in range(items)))
于 2012-05-22T16:42:55.990 回答
1

你的错误是这一行：

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-22T16:29:25.183 回答
1

在我看来，你想要的是一个 N 位的 base-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-22T16:42:57.310 回答
0

如果你想要组合，那么递归几乎总是正确的答案。

您的代码存在问题：在recursion函数内部，当您说coeff_temp = coeff要复制对 的引用时coeff，您只是每次都附加相同的列表。这就是为什么 。否则，该方法对我来说似乎很好。

换行

coeff_temp = coeff

至

coeff_temp = list(coeff)

复制列表，然后从那里继续。

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

于 2012-05-22T16:27:10.773 回答
0

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

于 2012-05-22T16:21:52.130 回答