より具体的にするために、入力として整数 n と行列を指定すると、次のすべての組み合わせを返すアルゴリズム (再帰的かどうかに関係なく) が必要です: 1) 各行から少なくとも 1 つのオブジェクト 2) 意志合計n個のオブジェクトを持つ
すべての組み合わせを試して、各行から n 個のオブジェクトと 1 個のオブジェクトを持つものを使用すれば、これを簡単に解決できると思いますが、アルゴリズムはそれよりもはるかに効率的であると信じています。また、1 行に 1 つのオブジェクトのすべての組み合わせを返すアルゴリズムのコーディングにも成功しましたが、それ以上に拡張することはできませんでした。Pythonでコーディングしてきましたが、どの言語でも構いません。Python が参照ごとにオブジェクトを渡すという考慮事項の追加点。=)
行列が二乗であると仮定します。誰かが理由を知りたい場合、これは私が解決しようとしているより複雑なグラフ アルゴリズムの一部です。
皆さんありがとう！
行列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))))))))
すべての回答をありがとう、彼らは私が探していたものに近かった. 私はPythonでそれを行うことができました（したがって、ここに投稿された結果を確認しませんでした）、私の問題は実際には関数呼び出しで参照とコピーを渡すPythonでした。浅いコピーで十分だと思っていましたが、どうやら深いコピーが必要だったようです (なぜ浅いコピーでは不十分なのか考えていませんでした)。
PS1: ここのグラフはリストの辞書です。n_edges は、グラフ
PS2 から選択されるエッジの数です。ここでのサイズの計算はかなり非効率的です。まだ修正するのに時間はかかりません。
PS3: 辞書を順番に反復処理するために、グラフのリストのリスト表現 (lol) とそれに一致するインデックス配列 (lolindex) の 2 つのリストを作成しました。
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)
なんて素晴らしい質問でしょう！用語と一致させるために、マトリックス内の行を「入力バッグ」と呼び、入力バッグ内の項目を「オブジェクト」と呼びます。バッグ (またはマルチセット) は、メンバーが複数回出現することを許可するコンテナーですが、そのメンバーには固有の順序がありません (リストとは異なります)。
次のシグネチャを持つ関数を探しています。
set of valid combinations =
generate_combinations(list of input bags, number of objects in valid combination)
有効な組み合わせのセットが Python で使用できるメモリを超える可能性があるためgenerate_combinations、明示的なリストではなくジェネレータを返す必要があります。
有効な結果は、次の要件を満たす必要があります。
私は次のことを想定しています：
要件 1 と仮定 4 が意味することnumber of input bags <= n <= total number of objects in all bags
データ構造
itertoolsv2.6 で導入されたPython の組み込みモジュールを使用して組み合わせを生成します。古いバージョンの 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 を削除することだけです。削減された問題を解決するには、バッグのメンバーを 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 要素] と [いずれかのバッグからの追加要素] の間のオーバーラップが無視される場合、解は最初の可能な組み合わせと 2 番目の可能な組み合わせのデカルト積になります。
オーバーラップを処理するには、[各入力バッグの 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.最小のメモリ消費。このアルゴリズムは、入力バッグのリストによって消費されるものを超えて一定スペースのメモリを必要とします。
ほとんどの場合、タスクを変更して、単純なリストのすべての組み合わせをリストしたいですか? 以下は、これを行う 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]);
}
}