挑战：在元组的每个位置创建具有不同值 'options' 的不同组合的元组列表。

Question

挑战来了。如果你能解决它，你就是一个比我更好的人。假设 a can = 1 或 0，b can = 1 或 0，c can = 0,1 或 2，d can = 0,1,2 或 4，e 仅 0，f = 0 或 1.

创建一个元组列表，其中包含总和为特定数字（小于 5）的所有组合，用于选择字母。

例如 a,b,c,d 和数字 4 会给出（无特定顺序）

[(1,1,1,1),(1,1,2,0),(1,1,0,2),(0,0,2,2),(0,0,0,4)]

或 f,f,e,d,c 和 3 会给出

[(1,1,0,1,0),(1,1,0,0,1)(1,0,0,1,1),(1,0,0,2,0),(1,0,0,0,2),(0,1,0,2,0),(0,1,0,0,2)]

创建所有的组合，然后删除那些加起来不等于数字的组合是作弊，而且效率太低。

我试过使用

list(itertools.product(*a))

但是就像我说的那样创建所有组合所以使用它可以减少它是作弊。

Answer 1

你可以使用 a list comprehension with short-circuiting conditionals:

[(a,b,c,d) 
 for a in range(2)
 for b in range(2)
 if a+b <= 4
 for c in range(3)
 if a+b+c <= 4
 for d in [0,1,2,4]
 if a+b+c+d == 4]

产量

[(0, 0, 0, 4),
 (0, 0, 2, 2),
 (0, 1, 1, 2),
 (0, 1, 2, 1),
 (1, 0, 1, 2),
 (1, 0, 2, 1),
 (1, 1, 0, 2),
 (1, 1, 1, 1),
 (1, 1, 2, 0)]

这会找到所有解，而无需枚举整组笛卡尔产品。一旦部分和大于目标金额。

将其概括为可以接受任意集合的函数从中形成笛卡尔积的迭代器，我们可以使用

def constrained_product(target, *args):
    pools = map(tuple, args)
    if len(pools) == 1:
        for y in pools[0]:
            if y == target:
                yield (y,)
    else:
        for y in pools[-1]:
            for x in constrained_product(target-y, *pools[:-1]):
                yield x + (y,)

这是此纯Python实现的轻微修改版本 itertools.product:

def iterproduct(*args):
    """
    list(iterproduct('ABCD', 'xy')) --> Ax Ay Bx By Cx Cy Dx Dy
    """
    pools = map(tuple, args)
    if len(pools) == 1:
        for y in pools[0]:
            yield (y,)
    else:
        for x in iterproduct(*pools[:-1]):
            for y in pools[-1]:
                yield x + (y,)

主要区别在于它使用条件 if y == target 将产生的项目限制为总和等于 target.

的项目

它类似于this pure-Python implementation shown in the docs，只是它在生成项目之前不生成所有产品。

例如，constrained_product可以这样使用：

A = range(2)
B = range(2)
C = range(3)
D = [0,1,2,4]
E = [0]
F = range(2)

def constrained_product(target, *args):
    pools = map(tuple, args)
    if len(pools) == 1:
        for y in pools[0]:
            if y == target:
                yield (y,)
    else:
        for y in pools[-1]:
            for x in constrained_product(target-y, *pools[:-1]):
                yield x + (y,)

for item in constrained_product(4, A, B, C, D):
    print(item)
    # (1, 1, 2, 0)
    # (1, 1, 1, 1)
    # (1, 0, 2, 1)
    # (0, 1, 2, 1)
    # (1, 1, 0, 2)
    # (1, 0, 1, 2)
    # (0, 1, 1, 2)
    # (0, 0, 2, 2)
    # (0, 0, 0, 4)

for item in constrained_product(3, F, F, E, D, C):
    print(item)
    # (1, 1, 0, 1, 0)
    # (1, 0, 0, 2, 0)
    # (0, 1, 0, 2, 0)
    # (1, 1, 0, 0, 1)
    # (1, 0, 0, 1, 1)
    # (0, 1, 0, 1, 1)
    # (0, 0, 0, 2, 1)
    # (1, 0, 0, 0, 2)
    # (0, 1, 0, 0, 2)
    # (0, 0, 0, 1, 2)

如果我们可以还假设 args 中的值都是非负然后我们可以通过添加 if-statement:

来加速代码

    for y in pools[-1]:
        if target-y >= 0:
            for x in constrained_product(target-y, *pools[:-1]):
                yield x + (y,)

如果 target-y < 0 那么调用 constrained_product(target-y, *pools[:-1]) 是没有意义的，因为根据假设 pools[:-1] 中的所有值都是非负数。我们知道没有可以求和为负数的元组，所以我们可以通过删除此分支来节省时间。

使用 constrained_product、

的修改版本

def constrained_product_nonneg(target, *args):
    pools = map(tuple, args)
    if len(pools) == 1:
        for y in pools[0]:
            if y == target:
                yield (y,)
    else:
        for y in pools[-1]:
            if target-y >= 0:
                for x in constrained_product_nonneg(target-y, *pools[:-1]):
                    yield x + (y,)

现在

list(constrained_product_nonneg(0, *[A]*53))

快速找到解决方案：

In [35]: %timeit list(constrained_product_nonneg(0, *[A]*53))
10000 loops, best of 3: 170 µs per loop

Answer 2

这是一个基于树的解决方案。它为系统做出每一个有效答案（这可能是作弊）但它不必进行重复计算。

class tree_node:
     def __init__(self, v, s, p):
          self.value = v
          self.sum = s
          self.parent = p
          self.branchList = []

if __name__ == "__main__":

    # Initialize the tree. The sums will be in the leaves once it's built
    root = tree_node(None, 0, None)
    leaf_list = [root]

    # Define the rules of the problem
    a = [0, 1]
    b = [0, 1]
    c = [0, 1, 2]
    d = [0, 1, 4]
    e = [0]
    f = [0, 1]
    rules = [a, b, c, d, e, f]

    # Build the tree, one layer of nodes at a time
    for rule in rules:
       new_leaves = []
       for leaf in leaf_list:
           for r in rule:
                tn = tree_node(r, r + leaf.sum, leaf)
                new_leaves.append(tn)
       leaf_list = new_leaves


    # Traverse the tree starting from each matching leaf
    target = 4
    for n in leaf_list:
        if n.sum == target:
            sequence = [n.value]
            parent = n.parent
            while parent.value != None:
                sequence = sequence + [parent.value]
                parent = parent.parent
            sequence.reverse()
            print sequence

挑战：在元组的每个位置创建具有不同值 'options' 的不同组合的元组列表。

Challenge: Creating a list of tuples of different combinations with different value 'options' in each location of the tuple.

combinations

python-2.7