返回所有可能的n个物体组合的算法

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

我觉得如果我只是尝试了所有的组合，我可以解决这个问题更容易，使用具有n个对象和1的那些对象总每一行，但我相信算法可以比这更有效率。我也成功编写了一个算法，它将返回每行1个对象的所有组合，但无法将其扩展到更多。我一直在用Python编码，但任何语言都没问题。考虑到python传递每个引用的对象的额外点。 =）

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

谢谢大家！

来源

2011-03-14 Arthur

感谢，他们接近我一直在寻找。我设法在Python下执行它（所以我没有检查这里发布的结果），我的问题实际上是Python在函数调用中传递引用vs副本。我认为一个浅的副本就足够了，但显然我需要一个深层的副本（没有想到为什么浅层是不够的）。

这就是我做的：
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-22 05:04:31 Arthur

假设矩阵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-14 04:51:00

最有可能要修改的任务，并列出一个简单的列表的所有组合？下面是一个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-14 08:59:19 Bytemain

真是个好问题！为了与术语保持一致，我会将矩阵中的行称为“输入bags”，并将输入袋中的项目称为“对象”。袋（或multiset）是一个容器，允许成员出现不止一次，但其成员没有固有的顺序（与列表不同）。

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

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

因为它有可能是一组有效组合超过Python可以使用的内存，generate_combinations应该返回一个发电机，而不是一个明确的名单。

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

至少1个从各输入包
对象将具有N个对象的总

我假设以下几点：

结果中对象的顺序无关紧要
输入袋可以包含重复的对象
两个输入袋可以包含重复的对象（在退化情况下，两个输入袋可以是相同的）
有效结果拉动对象，而无需更换

要求＃ 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个元素]中的元素从[任何袋子中的其他元素]中移除，然后循环移除。

>>> 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)

remove操作在列表上受支持，但在生成器上不受支持。要避免将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)

袋类的实现可能是这样的：

>>> 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）。

The bene适合的方法是： 1.较少的代码维护（即itertools） 2.没有递归。 Python性能会随着调用堆栈高度而下降，因此最小化递归是有益的。 3.最小的内存消耗。该算法需要超出输入包列表消耗的恒定空间内存。

来源

2013-11-20 07:15:50 IceArdor

返回所有可能的n个物体组合的算法

回答

相关问题