返回所有可能的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個物體組合的算法

回答

相關問題