3

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

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

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

谢谢大家！

4

4 回答 4

2

假设矩阵m是一个列表列表；这是它的球拍功能：

(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))))))))
于 2011-03-14T04:51:00.147 回答
1

感谢所有的答案，他们接近我正在寻找的东西。我设法在 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)
于 2011-03-22T05:04:31.370 回答
0

您很可能想修改任务并列出简单列表的所有组合？下面是一个 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]);
  }
 }
于 2011-03-14T08:59:19.583 回答
0

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

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

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

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

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

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

我假设以下内容：

  1. 结果中对象的顺序无关紧要
  2. 一个输入包可以包含重复的对象
  3. 两个输入包可以包含重复的对象（在退化的情况下，两个输入包可以相同）
  4. 有效的结果拉取对象而不进行替换

要求 #1 和假设 #4 暗示number of input bags <= n <= total number of objects in all bags

数据结构

  • 由于输入包允许包含重复值（根据假设 #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.最小的内存消耗。该算法需要超出输入包列表所消耗的恒定空间内存。

于 2013-11-20T07:15:50.930 回答