5

2つのリストを取り込んで、リストの長さが同じであるとは限らず、2つのリスト間のすべてのインターリーブを返す関数を作成したいと思います。

入力：サイズが同じである必要のない2つのリスト。

出力：元のリストの順序を保持する、2つのリスト間のすべての可能なインターリーブ。

例： AllInter（[1,2]、[3,4]）-> [[1,2,3,4]、[1,3,2,4]、[1,3,4,2]、[ 3,1,2,4]、[3,1,4,2]、[3,4,1,2]]

私は解決策を望んでいません。ヒントが欲しい。

4

4 に答える 4

5

Itertools は、この問題を処理するのに十分な能力がなく、ペグと穴の問題を少し理解する必要があります。

リストの例を検討してください

A = [1, 2] B = [3, 4]

len(A) + len(B)要素 (ペグ) を配置できる4 つの穴 ( ) があります。

|   ||   ||   ||   |
|___||___||___||___|

Python では、空のスロットを次のリストとして表すことができます。None

slots = [None]*(len(A) + len(B))

2 番目のリストの要素 (ペグ) をペグに配置できる方法の数は、単純に、穴からスロットを選択できる方法の数です。

len(A) + len(B)ハlen(B)

= 4C2

=itertools.combinations(range(0, len(len(A) + len(B)))

次のように表すことができます

|   ||   ||   ||   |  Slots
|___||___||___||___|  Selected

  3    4              (0,1)
  3         4         (0,2)
  3              4    (0,3) 
       3    4         (1,2) 
       3         4    (1,3)
            3    4    (2,3)

これらのスロット位置のそれぞれについて、2 番目のリストの要素 (ペグ) を入力します。

for splice in combinations(range(0,len(slots)),len(B)):
    it_B = iter(B)
    for s in splice:
        slots[s] = next(it_B)

完了したら、最初のリストの要素 (ペグ) で残りの空のスロットを埋める必要があります。

    it_A = iter(A)
    slots = [e if e else next(it_A) for e in slots]

別のスロット位置で次の反復を開始する前に、穴をフラッシュします

    slots = [None]*(len(slots))

上記のアプローチの Python 実装

def slot_combinations(A,B):
    slots = [None]*(len(A) + len(B))
    for splice in combinations(range(0,len(slots)),len(B)):
        it_B = iter(B)
        for s in splice:
            slots[s] = next(it_B)
        it_A = iter(A)
        slots = [e if e else next(it_A) for e in slots]
        yield slots
        slots = [None]*(len(slots))

そして、上記の実装からの O/P

list(slot_combinations(A,B))
[[3, 4, 1, 2], [3, 1, 4, 2], [3, 1, 2, 4], [1, 3, 4, 2], [1, 3, 2, 4], [1, 2, 3, 4]]
于 2013-03-09T06:11:00.550 に答える
2

ヒント: 各リストに同じ要素が含まれているとします (ただし、リストごとに異なります)。つまり、1 つのリストは完全に赤 (r とします) で、もう 1 つは青 (b とします) でした。

出力の各要素には r+b またはそれらが含まれ、そのうちの r は赤色です。

あなたが解決策を求めていないにもかかわらず、他の人があなたのためにそれを台無しにしてしまったようです (しかし、彼らは非常に良い説明をしています)

というわけで早速書いたコードです。

import itertools

def interleave(lst1, lst2):
    r,b = len(lst1), len(lst2)
    for s in itertools.combinations(xrange(0,r+b), r):
        lst = [0]*(r+b)
        tuple_idx,idx1,idx2 = 0,0,0
        for i in xrange(0, r+b):
            if tuple_idx < r and i == s[tuple_idx]:
                lst[i] = lst1[idx1]
                idx1 += 1
                tuple_idx += 1
            else: 
                lst[i] = lst2[idx2]
                idx2 += 1
        yield lst


def main():
    for s in interleave([1,2,3], ['a','b']):
        print s

if __name__ == "__main__":
    main()

基本的な考え方は、出力を (r+b) r の組み合わせを選択するようにマッピングすることです。

于 2013-03-09T06:03:01.183 に答える
1

@airza が示唆するように、itertoolsモジュールはあなたの友達です。

カプセル化された魔法の良さを使用したくない場合は、再帰を使用することをお勧めします。

リストを生成するプロセスを頭の中で再生し始め、同じことを繰り返していることに気付いたら、パターンを見つけてみてください。例えば：

  1. 最初のリストから最初の要素を取得します
  2. 他のリストから 2 番目または最初のいずれかを取得します
  3. 3 番目を取るか、そうでない場合は 2 番目を取るか、他のリストから別のものを取る
  4. ...

わかりました、それは私たちが使用していないより大きなロジックがあるように見え始めています. 数を増やしているだけです。確かに、より高い要素に名前を付けるのではなく、「最初の要素を変更しながら機能する基本ケースを見つけることができますか?

それで遊びます。:)

于 2013-03-09T01:56:03.280 に答える
0

少し金属に近く、よりエレガントな (私の意見では) さまざまな可能なスライスを反復することを試すことができます。基本的には、標準のスライス操作に対する 3 つの引数すべてをステップ実行して反復処理し、最終的なリストに追加されたものをすべて削除します。興味があれば、コード スニペットを投稿できます。

于 2013-03-09T06:08:44.007 に答える