返回从不同箱中取出的 n 个对象的所有可能组合的算法

Question

为了使其更具体，我需要一个算法（无论是否递归），给定一个整数 n 和一个矩阵作为输入，该算法将返回所有具有以下组合的组合： 1) 每行至少 1 个对象 2）总共有n个对象

我觉得如果我尝试所有组合并使用每行有n个对象和1个对象的组合，我觉得我可以更容易地解决这个问题，但我相信该算法可以比这更有效。 我还成功地编写了一种算法，该算法将返回每行 1 个对象的所有组合，但无法将其扩展为更多。我一直用 Python 编码，但任何语言都可以。需要额外考虑的是，python 按引用传递对象。 =)

假设矩阵是平方的。如果有人想知道为什么，这是我试图解决的更复杂的图形算法的一部分。

谢谢大家！

Answer 1

假设矩阵m是一个列表的列表；这是一个 Racket 函数：

(define (combinations m n)
  (cond
    ((and (zero? n) (null? m)) '(()))
    ((zero? n) '())
    ((null? m) '())
    ((null? (car m)) '())
    (else
      (append (combinations (cons (cdar m) (cdr m)) n)
              (map (lambda (ls) (cons (caar m) ls))
                   (append
                     (combinations (cons (cdar m) (cdr m)) (sub1 n))
                     (combinations (cdr m) (sub1 n))))))))

Answer 2

感谢所有的答案，它们很接近我正在寻找的东西。我设法在Python下完成它（所以我没有检查这里发布的结果），我的问题实际上是Python在函数调用中传递引用与复制。我认为浅拷贝就足够了，但显然我需要一个深拷贝（没有想过为什么浅拷贝还不够）。

我就是这样做的：
PS1：这里的图表是列表的字典。 n_edges 是要从图中选取的边数
PS2：这里的大小计算效率很低，还没有花时间修复它。
PS3：为了在字典上有序迭代，我创建了两个列表：图形的列表列表表示（lol）和与其匹配的索引数组（lolindex）。
PS4：适应我发布的问题，我使用的真实方法有更多问题特定的代码。还没有按照我在这里放置的方式测试代码。

def pickEdges(n_edges, newgraph):
    size = sum(len(v) for v in newgraph.itervalues())
    if (size == n_edges):
        print newgraph
        return

    for i in range(len(lol)):
        for j in range(len(lol[i])):
                tmpgraph = copy.deepcopy(newgraph)
                if (lol[i][j] not in tmpgraph[lolindex[i]]):
                       tmpgraph[lolindex[i]].append(lol[i][j])
                       pickEdges(n_edges, tmpgraph)

Answer 3

您很可能想修改任务并列出简单列表的所有组合？
下面是一个 Javascript 函数，可以为您完成此操作：

function getWayStr(curr) {
  var nextAbove = -1;
  for (var i = curr + 1; i < waypoints.length; ++i) {
    if (nextAbove == -1) {
      nextAbove = i;
    } else {
      wayStr.push(waypoints[i]);
      wayStr.push(waypoints[curr]);
    }
  }
  if (nextAbove != -1) {
    wayStr.push(waypoints[nextAbove]);
    getWayStr(nextAbove);
    wayStr.push(waypoints[curr]);
  }
 } 

Answer 4

多么好的问题啊！为了与术语保持一致，我将矩阵中的行称为“输入 bags” 和输入袋中的物品作为“对象”。包（或多集）是一个容器，允许成员多次出现，但其成员没有固有的顺序（与列表不同）。

我们正在寻找具有以下签名的函数：

set of valid combinations =
generate_combinations(list of input bags, number of objects in valid combination)

由于有效组合集可能超出 Python 可用的内存，因此 generate_combinations 应返回一个生成器而不是显式列表。

有效结果必须满足以下要求：

1. 每个输入袋中至少
2. 有 1 个对象 总共有 n 个对象

我假设以下内容：

1. 结果中对象的顺序并不重要
2. 一个输入袋可以包含重复的对象
3. 两个输入袋可以包含重复的对象（在退化情况下，两个输入袋可以相同）
4. 有效结果无需替换即可提取对象

要求 #1 和假设 #4 意味着输入袋的数量 n <= 中的对象总数所有包

数据结构

• 由于输入包允许包含重复值（根据假设#2），我们不能使用 set/frozenset 来存储这些值。 Python 列表适合此任务。替代容器可以是 collections.Counter，它具有常量 -对具有许多重复项的列表进行时间隶属度测试和更好的空间效率。
• 每个有效组合也是一个包
• 对于输入包的列表，顺序并不重要，因此可以将其概括为输入包的包。为了理智起见，我将保持原样。

我将使用 Python 的内置 itertools 模块来生成组合，该模块是在 v2.6 中引入的。如果您运行的是旧版本的 Python，请使用配方。对于这些代码示例，为了清楚起见，我已将生成器隐式转换为列表。

>>> import itertools, collections
>>> input_bags = [Bag([1,2,2,3,5]), Bag([1,4,5,9]), Bag([12])]
>>> output_bag_size = 5
>>> combos = generate_combinations(input_bags, output_bag_size)
>>> combos.next() #an arbitrary example
Bag([1,1,2,4,12])

意识到上述问题可以简化为可以通过 Python 内置的 itertools 模块立即解决的问题，该模块生成序列的组合。我们需要做的唯一修改是消除要求#1。为了解决减少的问题，请将袋子的成员组合成一个袋子。

>>> all_objects = itertools.chain.from_iterable(input_bags)
>>> all_objects
generator that returns [1, 2, 2, 3, 5, 1, 4, 5, 9, 12]
>>> combos = itertools.combinations(all_objects, output_bag_size)
>>> combos
generator that returns [(1,2,2,3,5), (1,2,2,3,1), (1,2,2,3,4), ...]

为了恢复要求#1，每个有效组合（输出包）需要包含来自每个输入包的 1 个元素以及来自任何包的附加元素，直到输出包大小达到用户指定的值。如果忽略[每个输入袋中的 1 个元素]和[任何袋中的附加元素]之间的重叠，则解决方案只是第一个可能的组合和第二个可能的组合的笛卡尔积。

要处理重叠，请从 [来自任何包的附加元素] 中删除 [每个输入包中的 1 个元素] 中的元素，然后进行 for 循环。

>>> combos_with_one_element_from_each_bag = itertools.product(*input_bags)
>>> for base_combo in combos_with_one_element_from_each_bag:
>>>     all_objects = list(itertools.chain.from_iterable(input_bags))
>>>     for seen in base_combo:
>>>         all_objects.remove(seen)
>>>     all_objects_minus_base_combo = all_objects
>>>     for remaining_combo in itertools.combinations(all_objects_minus_base_combo, output_bag_size-len(base_combo)):
>>>         yield itertools.chain(base_combo, remaining_combo)

列表支持删除操作，但生成器不支持删除操作。为了避免将 all_objects 作为列表存储在内存中，请创建一个跳过 base_combo 中的元素的函数。

>>> def remove_elements(iterable, elements_to_remove):
>>>     elements_to_remove_copy = Bag(elements_to_remove) #create a soft copy
>>>     for item in iterable:
>>>         if item not in elements_to_remove_copy:
>>>             yield item
>>>         else:
>>>             elements_to_remove_copy.remove(item)

Bag 类的实现可能如下所示：

>>> class Bag(collections.Counter):
>>>     def __iter__(self):
>>>         return self.elements()
>>>     def remove(self, item):
>>>         self[item] -= 1
>>>         if self[item] <= 0:
>>>             del self[item]

完整代码

import itertools, collections

class Bag(collections.Counter):
    def __iter__(self):
        return self.elements()
    def remove(self, item):
        self[item] -= 1
        if self[item] <= 0:
            del self[item]
    def __repr__(self):
        return 'Bag(%s)' % sorted(self.elements())


def remove_elements(iterable, elements_to_remove):
    elements_to_remove_copy = Bag(elements_to_remove) #create a soft copy
    for item in iterable:
        if item not in elements_to_remove_copy:
            yield item
        else:
            elements_to_remove_copy.remove(item)

def generate_combinations(input_bags, output_bag_size):
    combos_with_one_element_from_each_bag = itertools.product(*input_bags)
    for base_combo in combos_with_one_element_from_each_bag:
        all_objects_minus_base_combo = remove_elements(itertools.chain.from_iterable(input_bags), base_combo)
        for remaining_combo in itertools.combinations(all_objects_minus_base_combo, output_bag_size-len(base_combo)):
            yield Bag(itertools.chain(base_combo, remaining_combo))

input_bags = [Bag([1,2,2,3,5]), Bag([1,4,5,9]), Bag([12])]
output_bag_size = 5
combos = generate_combinations(input_bags, output_bag_size)
list(combos)

通过添加错误检查代码（例如 output_bag_size >= len(input_bags)）来完成此操作。

这种方法的好处是：
1. 需要维护的代码更少（即itertools）
2.无递归。 Python 性能随着调用堆栈高度的增加而降低，因此最小化递归是有益的。
3. 最小的内存消耗。该算法需要超出输入包列表消耗的恒定空间内存。