展示一个列表的所有可能分组，仅给定子列表的数量（长度可变）

Question

问题

第一步：给定一个数字列表，生成所有可能的分组（按顺序），只考虑所需最终组数。

例如，如果我的数字列表是 1 到 4，我想要最终分为 2 组，则可能性如下：

[1], [2,3,4]

[1,2], [3,4]

[1,2,3], [4]

步骤 2：对这些组进行算术运算。

例如，如果我们选择加法，则最终结果将为：

1 + 234 = 235
12 + 34 = 46
123 + 4 = 127

先前的研究和类似问题

我在 Stack Overflow 和其他地方看到了许多涉及不同数量组的变量的问题的例子，这些问题使用范围和 for 循环，例如：

print [num_list[i:i+groups] for i in range(0,len(num_list),groups)]

但这与我想要的相反 - 在那种情况下，除了最后一个组以外，各个组的长度都是固定的，而组数则会震荡。

这不是作业，只是我遇到的一个有趣的问题。理想情况下，我需要能够迭代这些单独的子列表以执行数学运算，因此它们也需要被捕获。

我有一种感觉解决方案将涉及到itertools，但我似乎无法弄清楚关于分组方面的组合数。

步骤2的编辑/扩展

如果我想对每个分区执行不同的操作，我还可以用同样的方法吗？而不仅仅是指定int.add，我是否可以以某种方式执行所有主要的4个运算的另一种组合？例如：

symbol_list = ['+','-','*','/']
for op in symbol_list:
   #something

我最终会得到以下可能性：

1 + 2 * 34
1 * 2 - 34
1 / 2 + 34
etc.

操作顺序可以忽略。

最终解决方案

#!/usr/bin/env python

import sys
from itertools import combinations, chain, product

# fixed vars
num_list = range(_,_) # the initial list
groups = _ # number of groups
target = _ # any target desired
op_dict = {'+': int.__add__, '-': int.__sub__,
           '*': int.__mul__, '/': int.__div__}

def op_iter_reduce(ops, values):
    op_iter = lambda a, (i, b): op_dict[ops[i]](a, b)
    return reduce(op_iter, enumerate(values[1:]), values[0])

def split_list(data, n):
    for splits in combinations(range(1, len(data)), n-1):
        result = []
        prev = None
        for split in chain(splits, [None]):
            result.append(data[prev:split])
            prev = split
        yield result

def list_to_int(data):
    result = 0
    for h, v in enumerate(reversed(data)):
        result += 10**h * v
    return result

def group_and_map(data, num_groups):
    template = ['']*(num_groups*2 - 1) + ['=', '']
    for groups in split_list(data, num_groups):
        ints = map(list_to_int, groups)
        template[:-2:2] = map(str, ints)
        for ops in product('+-*/', repeat=num_groups-1):
            template[1:-2:2] = ops
            template[-1] = str(op_iter_reduce(ops, ints))
            if op_iter_reduce(ops, ints) == target:
                print ' '.join(template)

group_and_map(num_list, groups)

- Brett Woodward

Answer 1

步骤1：我发现将列表拆分成类似这样的组的最简单方法是尝试获得拆分位置的组合。以下是一种实现方法：

def split_list(data, n):
    from itertools import combinations, chain
    for splits in combinations(range(1, len(data)), n-1):
        result = []
        prev = None
        for split in chain(splits, [None]):
            result.append(data[prev:split])
            prev = split
        yield result

>>> list(split_list([1, 2, 3, 4], 2))
[[[1], [2, 3, 4]], [[1, 2], [3, 4]], [[1, 2, 3], [4]]]
>>> list(split_list([1, 2, 3, 4], 3))
[[[1], [2], [3, 4]], [[1], [2, 3], [4]], [[1, 2], [3], [4]]]

步骤2: 首先需要将类似于[[1], [2, 3, 4]]的列表转换成[1, 234]格式的列表。您可以使用以下函数完成此操作：

def list_to_int(data):
    result = 0
    for i, v in enumerate(reversed(data)):
        result += 10**i * v
    return result

>>> map(list_to_int, [[1], [2, 3], [4, 5, 6]])
[1, 23, 456]

现在你可以使用reduce()函数对结果列表进行操作：

>>> import operator
>>> reduce(operator.add, [1, 23, 456])  # or int.__add__ instead of operator.add
480

完整解决方案：根据不同运营商的编辑参考需求：

def op_iter_reduce(ops, values):
    op_dict = {'+': int.__add__, '-': int.__sub__,
               '*': int.__mul__, '/': int.__div__}
    op_iter = lambda a, (i, b): op_dict[ops[i]](a, b)
    return reduce(op_iter, enumerate(values[1:]), values[0])

def group_and_map(data, num_groups):
    from itertools import combinations_with_replacement
    op_dict = {'+': int.__add__, '-': int.__sub__,
               '*': int.__mul__, '/': int.__div__}
    template = ['']*(num_groups*2 - 1) + ['=', '']
    op_iter = lambda a, (i, b): op_dict[ops[i]](a, b)
    for groups in split_list(data, num_groups):
        ints = map(list_to_int, groups)
        template[:-2:2] = map(str, ints)
        for ops in combinations_with_replacement('+-*/', num_groups-1):
            template[1:-2:2] = ops
            template[-1] = str(op_iter_reduce(ops, ints))
            print ' '.join(template)

>>> group_and_map([1, 2, 3, 4], 2)
1 + 234 = 235
1 - 234 = -233
1 * 234 = 234
1 / 234 = 0
12 + 34 = 46
12 - 34 = -22
12 * 34 = 408
12 / 34 = 0
123 + 4 = 127
123 - 4 = 119
123 * 4 = 492
123 / 4 = 30

如果您使用的是 Python 2.6 或更早版本，且不可用itertools.combinations_with_replacement()函数，则可以使用此处链接中提供的方法。

- Andrew Clark

---

谢谢，这个也很好用。枚举部分让我有点困惑 - 需要再看一下。根据编辑，我正在尝试弄清楚如何添加一个循环来执行所有四种主要算术运算。因此，我可以尝试a + b - c，a * b / c等所有排列组合。 - Brett Woodward

@BrettWoodward - 你想保持运算顺序还是总是从左到右计算（1 + 2 * 34 是否应该实际计算为 (1 + 2) * 34 而不是正常的 1 + (2 * 34)）。 - Andrew Clark

在这种情况下，可以忽略OoO。也就是说，始终从左到右。我想使用lambda来实现，但不确定如何迭代不同的运算符。 - Brett Woodward

@BrettWoodward - 好的，我最近的编辑现在通过迭代基本数学运算符来工作了。 - Andrew Clark

太棒了，谢谢。虽然我一直在努力解决一个问题，但过去的几个小时里似乎它并没有创造出我需要的所有排列组合。最终我将组合替换为积，这会生成所有可能的重复算术运算符。最终我让它工作了。感谢大家，真是太好了。 - Brett Woodward

Answer 2

Raymond Hettinger写了一篇文章，介绍如何将一个可迭代对象分成n组的所有情况：

import itertools
import operator

def partition_indices(length, groups, chain = itertools.chain):
    first, middle, last = [0], range(1, length), [length]    
    for div in itertools.combinations(middle, groups-1):
        yield tuple(itertools.izip(chain(first, div), chain(div, last)))

def partition_into_n_groups(iterable, groups, chain = itertools.chain):
    # http://code.activestate.com/recipes/576795/
    # author: Raymond Hettinger
    # In [1]: list(partition_into_n_groups('abcd',2))
    # Out[1]: [('a', 'bcd'), ('ab', 'cd'), ('abc', 'd')]
    s = iterable if hasattr(iterable, '__getitem__') else tuple(iterable)
    for indices in partition_indices(len(s), groups, chain):
        yield tuple(s[slice(*x)] for x in indices)

def equations(iterable, groups):
    operators = (operator.add, operator.sub, operator.mul, operator.truediv)
    strfop = dict(zip(operators,'+-*/'))
    for partition in partition_into_n_groups(iterable, groups):
        nums_list = [int(''.join(map(str,item))) for item in partition]
        op_groups = itertools.product(operators, repeat = groups-1)
        for op_group in op_groups:
            nums = iter(nums_list)
            result = next(nums)
            expr = [result]
            for op in op_group:
                num = next(nums)
                result = op(result, num)
                expr.extend((op, num))
            expr = ' '.join(strfop.get(item,str(item)) for item in expr)
            yield '{e} = {r}'.format(e = expr, r = result)

for eq in equations(range(1,5), groups = 2):
    print(eq)

产量

1 + 234 = 235
1 - 234 = -233
1 * 234 = 234
1 / 234 = 0.0042735042735
12 + 34 = 46
12 - 34 = -22
12 * 34 = 408
12 / 34 = 0.352941176471
123 + 4 = 127
123 - 4 = 119
123 * 4 = 492
123 / 4 = 30.75

- unutbu

---

谢谢，这也很好用。我正在尝试理解那里的语法。根据编辑，我正试图弄清如何对所有4个主要算术运算进行循环。因此，我可以尝试a + b - c，a * b / c等所有排列组合，而不是将它们全部加起来。 - Brett Woodward

Answer 3

步骤 1：

我对所有可能的索引组合进行了工作:

from itertools import combinations

def cut(lst, indexes):
    last = 0
    for i in indexes:
        yield lst[last:i]
        last = i
    yield lst[last:]


def generate(lst, n):
    for indexes in combinations(list(range(1,len(lst))), n - 1):
        yield list(cut(lst, indexes))

例子：

for g in generate([1, 2, 3, 4, 5], 3):
    print(g)
"""
[[1], [2], [3, 4, 5]]
[[1], [2, 3], [4, 5]]
[[1], [2, 3, 4], [5]]
[[1, 2], [3], [4, 5]]
[[1, 2], [3, 4], [5]]
[[1, 2, 3], [4], [5]]
"""

步骤二：

首先，我们需要将数字组转化为数字：

for g in generate(list(range(1,6)), 3):
    print([int(''.join(str(n) for n in n_lst)) for n_lst in g])
"""
[1, 2, 345]
[1, 23, 45]
[1, 234, 5]
[12, 3, 45]
[12, 34, 5]
[123, 4, 5]
"""

然后使用reduce和operator进行算术运算：
(尽管这最后一个子步骤与您的问题无关)

from functools import reduce
import operator
op = operator.mul

for g in generate(list(range(1,6)), 3):
    converted = [int(''.join(str(n) for n in n_lst)) for n_lst in g]
    print(reduce(op, converted))
"""
690
1035
1170
1620
2040
2460
"""

- Rik Poggi

---

谢谢，这个很好用。根据修改，我正在尝试找出如何在所有四种主要算术运算中添加一个循环。因此，我可以尝试a + b -c、a * b / c等所有排列组合，而不是将它们全部相加。 - Brett Woodward

@BrettWoodward：这真的取决于你想要做什么操作，无论如何，你都可以将它们放在列表或字典中，例如：{'+': operator.add, ...}，然后选择你想要的那个。我已经更新了我的答案，并附上了 operator 和 reduce 文档的链接。不管怎样，如果你继续扩展你的问题，你永远不会解决它！;) - Rik Poggi