python - 1 つの重複を含むすべてのリストを反復処理する

Question

n値が からの整数である長さのすべてのリストを考慮してくださいrange 0 to n-1。重複が 1 つだけある可能性のあるすべてのリストをできるだけ早く反復したいと思います。その場合n = 2、可能なリストは次のとおりです。

00
11

n = 3それらが次の場合:

001
002
110
112
220
221
100
200
011
211
022
122
010
020
101
121
202
212

そのようなリストの総数は であるn! * (n choose 2)ため、可能であればすべてをメモリに格納することは避けたいと思います。

リストごとに、リストの関数を計算する関数を呼び出したいと思います。
これを行う良い方法は何ですか？

ベンチマーク私のコンピューターでは、次のベンチマーク結果が得られます

timeit all(one_duplicate(6))
100 loops, best of 3: 6.87 ms per loops
timeit all(one_duplicate(7))
10 loops, best of 3: 59 ms per loop
timeit all(one_duplicate(8))
1 loops, best of 3: 690 ms per loop
timeit all(one_duplicate(9))
1 loops, best of 3: 7.58 s per loop

と

timeit all(duplicates(range(6)))
10 loops, best of 3: 22.8 ms per loop
timeit all(duplicates(range(7)))
1 loops, best of 3: 416 ms per loop    
timeit all(duplicates(range(8)))
1 loops, best of 3: 9.78 s per loop

と

timeit all(all_doublet_tuples(6))
100 loops, best of 3: 6.36 ms per loop
timeit all(all_doublet_tuples(7))
10 loops, best of 3: 60 ms per loop
timeit all(all_doublet_tuples(8))
1 loops, best of 3: 542 ms per loop
timeit all(all_doublet_tuples(9))
1 loops, best of 3: 7.27 s per loop

現時点では と が最初に等しいこと を宣言all_doublet_tuplesします (テストでのノイズを考慮して)。one_duplicate

Answer 1

必要な出力タプルを次のように考えてみてください。これは、最初の (たとえば左から) doublet elem を複製し、それを 2 番目の doublet の位置に挿入することによって導出されました。

したがって、私の解決策は基本的に次の 2 段階のプロセスです。

1. のすべてのn-1順列を生成するrange(n)
2. 1. からの各タプル:
   各単一要素を取得し、最後を含めて (重複を避けるために)前の各位置に挿入します。

---

import itertools as it

# add_doublet accomplishes step 2
def add_doublet(t):
    for i in range(len(t)):
        for j in range(i+1, len(t)+1):
            yield t[:j] + (t[i],) + t[j:]


def all_doublet_tuples(n):
    for unique_tuple in it.permutations(range(n), n-1):
        for doublet_tuple in add_doublet(unique_tuple):
            yield doublet_tuple



from pprint import pprint

n = 3
pprint(list(all_doublet_tuples(n)))

ここでは出力を出力しません。長すぎるためです ... n=3 の場合は退屈です。

Answer 2

import itertools

def one_duplicate(n):
    nrange = list(range(n))
    for x in nrange:
        without_x = nrange[:x] + nrange[x+1:]
        for i, j in itertools.combinations(nrange, 2):
            for others in map(list, itertools.permutations(without_x, n-2)):
                others.insert(i, x)
                others.insert(j, x)
                yield others

>>> list(one_duplicate(2))
[[0, 0], [1, 1]]
>>> list(one_duplicate(3))
[[0, 0, 1], [0, 0, 2], [0, 1, 0], [0, 2, 0], [1, 0, 0], [2, 0, 0], [1, 1, 0], [1, 1, 2], [1, 0, 1], [1, 2, 1], [0, 1, 1], [2, 1, 1], [2, 2, 0], [2, 2, 1], [2, 0, 2], [2, 1, 2], [0, 2, 2], [1, 2, 2]]
>>> list(one_duplicate(4))
[[0, 0, 1, 2], [0, 0, 1, 3], [0, 0, 2, 1], [0, 0, 2, 3], [0, 0, 3, 1], [0, 0, 3, 2], [0, 1, 0, 2], [0, 1, 0, 3], [0, 2, 0, 1], [0, 2, 0, 3], [0, 3, 0, 1], [0, 3, 0, 2], [0, 1, 2, 0], [0, 1, 3, 0], [0, 2, 1, 0], [0, 2, 3, 0], [0, 3, 1, 0], [0, 3, 2, 0], [1, 0, 0, 2], [1, 0, 0, 3], [2, 0, 0, 1], [2, 0, 0, 3], [3, 0, 0, 1], [3, 0, 0, 2], [1, 0, 2, 0], [1, 0, 3, 0], [2, 0, 1, 0], [2, 0, 3, 0], [3, 0, 1, 0], [3, 0, 2, 0], [1, 2, 0, 0], [1, 3, 0, 0], [2, 1, 0, 0], [2, 3, 0, 0], [3, 1, 0, 0], [3, 2, 0, 0], [1, 1, 0, 2], [1, 1, 0, 3], [1, 1, 2, 0], [1, 1, 2, 3], [1, 1, 3, 0], [1, 1, 3, 2], [1, 0, 1, 2], [1, 0, 1, 3], [1, 2, 1, 0], [1, 2, 1, 3], [1, 3, 1, 0], [1, 3, 1, 2], [1, 0, 2, 1], [1, 0, 3, 1], [1, 2, 0, 1], [1, 2, 3, 1], [1, 3, 0, 1], [1, 3, 2, 1], [0, 1, 1, 2], [0, 1, 1, 3], [2, 1, 1, 0], [2, 1, 1, 3], [3, 1, 1, 0], [3, 1, 1, 2], [0, 1, 2, 1], [0, 1, 3, 1], [2, 1, 0, 1], [2, 1, 3, 1], [3, 1, 0, 1], [3, 1, 2, 1], [0, 2, 1, 1], [0, 3, 1, 1], [2, 0, 1, 1], [2, 3, 1, 1], [3, 0, 1, 1], [3, 2, 1, 1], [2, 2, 0, 1], [2, 2, 0, 3], [2, 2, 1, 0], [2, 2, 1, 3], [2, 2, 3, 0], [2, 2, 3, 1], [2, 0, 2, 1], [2, 0, 2, 3], [2, 1, 2, 0], [2, 1, 2, 3], [2, 3, 2, 0], [2, 3, 2, 1], [2, 0, 1, 2], [2, 0, 3, 2], [2, 1, 0, 2], [2, 1, 3, 2], [2, 3, 0, 2], [2, 3, 1, 2], [0, 2, 2, 1], [0, 2, 2, 3], [1, 2, 2, 0], [1, 2, 2, 3], [3, 2, 2, 0], [3, 2, 2, 1], [0, 2, 1, 2], [0, 2, 3, 2], [1, 2, 0, 2], [1, 2, 3, 2], [3, 2, 0, 2], [3, 2, 1, 2], [0, 1, 2, 2], [0, 3, 2, 2], [1, 0, 2, 2], [1, 3, 2, 2], [3, 0, 2, 2], [3, 1, 2, 2], [3, 3, 0, 1], [3, 3, 0, 2], [3, 3, 1, 0], [3, 3, 1, 2], [3, 3, 2, 0], [3, 3, 2, 1], [3, 0, 3, 1], [3, 0, 3, 2], [3, 1, 3, 0], [3, 1, 3, 2], [3, 2, 3, 0], [3, 2, 3, 1], [3, 0, 1, 3], [3, 0, 2, 3], [3, 1, 0, 3], [3, 1, 2, 3], [3, 2, 0, 3], [3, 2, 1, 3], [0, 3, 3, 1], [0, 3, 3, 2], [1, 3, 3, 0], [1, 3, 3, 2], [2, 3, 3, 0], [2, 3, 3, 1], [0, 3, 1, 3], [0, 3, 2, 3], [1, 3, 0, 3], [1, 3, 2, 3], [2, 3, 0, 3], [2, 3, 1, 3], [0, 1, 3, 3], [0, 2, 3, 3], [1, 0, 3, 3], [1, 2, 3, 3], [2, 0, 3, 3], [2, 1, 3, 3]]

アルゴリズムの説明は次のとおりです。

• を使用してすべてのインデックス ペアを検索します。itertools.combinations(nrange, 2)
• 範囲内の各数値について、範囲全体xの長さのすべての順列を取得します。n-2x
• これらの順列のxそれぞれで、最初のステップで見つかったインデックスのそれぞれに挿入し、結果を生成します。

私の答えとPeter Stahl'sのタイミング比較：

# Just showing they both get the same result
In [23]: set(peter(range(6))) == set(tuple(x) for x in fj(6))
Out[23]: True

In [24]: %timeit list(peter(range(6)))
10 loops, best of 3: 27.3 ms per loop

In [25]: %timeit list(fj(6))
100 loops, best of 3: 8.32 ms per loop

In [26]: %timeit list(peter(range(7)))
1 loops, best of 3: 506 ms per loop

In [27]: %timeit list(fj(7))
10 loops, best of 3: 81 ms per loop

Answer 3

import itertools
n=3
for i in range(n-1):
    for j in range(n-i-1):
        for perm in map(list, itertools.permutations(range(n), n-1)):
            perm.insert(i, perm[i+j])
            print perm

ここでの重要な概念は、N の長さのセットからすべての N-1 の長さの順列を生成し、それをすべての繰り返しの組み合わせ (i および i+j) に対して実行することです。

N=3 の場合、順列は次のとおりです。

(0, 1) (0, 2) (1, 0) (1, 2) (2, 0) (2, 1)

繰り返される要素は、X でマークされた位置にあります。

XX_、X_X、_XX

結果は、これらのセットの「乗算」です。

        XX_  X_X  _XX
(0, 1)  001  010  011
(0, 2)  002  020  022
(1, 0)  110  101  100
(1, 2)  112  121  122
(2, 0)  220  202  200
(2, 1)  221  212  211

すべてがオンザフライで計算されます。メモリ消費はO(N)だと思います。

Answer 4

from itertools import product    

def duplicates(r):
    r_len = len(r)
    dup_len = r_len - 1
    for tup in product(r, repeat=r_len):
        if len(set(tup)) == dup_len:
            yield tup

>>> list(duplicates(range(2)))
[(0, 0), (1, 1)]

>>> list(duplicates(range(3)))
[(0, 0, 1),
 (0, 0, 2),
 (0, 1, 0),
 (0, 1, 1),
 (0, 2, 0),
 (0, 2, 2),
 (1, 0, 0),
 (1, 0, 1),
 (1, 1, 0),
 (1, 1, 2),
 (1, 2, 1),
 (1, 2, 2),
 (2, 0, 0),
 (2, 0, 2),
 (2, 1, 1),
 (2, 1, 2),
 (2, 2, 0),
 (2, 2, 1)]

私のマシンのいくつかのベンチマーク：

%timeit all(duplicates(range(5)))
100 loops, best of 3: 2.5 ms per loop

%timeit all(duplicates(range(6)))
10 loops, best of 3: 38.6 ms per loop

%timeit all(duplicates(range(7)))
1 loops, best of 3: 766 ms per loop

%timeit all(duplicates(range(8)))
1 loops, best of 3: 18.8 s per loop

Answer 5

あなたの質問は、実際listのメモリ内を作成せずにそうする方法と、それぞれで関数を実行する方法に関するものです。そのため、最初にその部分を一般的に答え、次に特定の問題について答えます。

可能なリストの総数は n*(n-1) * (n choose 2) であるため、可能であればすべてをメモリに格納することは避けたいと思います。

各回答を a に追加してから返すyield通常の関数の代わりに、1 つずつ回答するジェネレーター関数を作成するだけで済みます。listlist

リストごとに、リストの関数を計算する関数を呼び出したいと思います。これを行う良い方法は何ですか？

ジェネレーター関数を呼び出して、結果を反復子として使用できます。例えば：

for element in my_generator_function(n):
    my_function(element)

各要素を呼び出した結果が必要な場合はmy_function、別のジェネレーター関数を作成できます。

def apply_to(my_function, my_iterator):
    for element in my_iterator):
        yield my_function(element)

ただし、mapPython 3 またはitertools.imapPython 2 で呼び出された、まさにそれを行う組み込み関数が既に存在します。

または、さらに簡単に、ジェネレーター式を使用できます。

results = (my_function(element) for element in my_generator_function(n))

詳細については、公式の Python チュートリアルのIterators、Generators、およびGenerator Expressionsセクションを参照してください。

これで、次のように問題を分解できます。

• 最初の n 個の数値のセット内の各数値について:
  • その数のすべての順列を 2 回、他の数の n-2 と共に

n=2 の場合、これは (0, 0) のすべての順列と (1) からの 0 の数、および (1, 1) のすべての順列と (0) の 0 の数を意味します。n=3 の場合、(0, 0) のすべての順列と 1 つの数字 (1, 2) があり、(1, 1) のすべての順列と 1 つの数字 (0, 2) があります。 (2, 2) のすべての順列と、1 つの数値 (0, 1) を組み合わせたもの。等々。

したがって、次の魔法を使用して、それを直接 Python に変換しますitertools。

def one_duplicate_element(n):
    for i in range(n):
        rest = (j for j in range(n) if j != i)
        for combination in itertools.combinations(rest, n-2):
            yield from itertools.permutations(combination + (i, i))

これはyield fromPython 3.3 のステートメントを使用しており、これは「この反復子からすべての要素を生成する」ことを意味します。3.2 以前を使用している場合は、ループを使用して明示的に行う必要があります。

def one_duplicate_element(n):
    for i in range(n):
        rest = (j for j in range(n) if j != i)
        for combination in itertools.combinations(rest, n-2):
            for permutation in itertools.permutations(combination + (i, i)):
                yield permutation

しかし、これはまさに要求どおりに機能しますが、サンプル出力と同じリストが生成されないことに気付くでしょう。順序を無視しても（あなたには関係ないと思います）、重複があります。なんで？

さて、セットの順列は何(0, 0)ですか？これはひっかけ問題です。(0, 0)重複があるため、セットにすることはできません。それで、何であれ(0, 0)、その順列は何ですか？さて、順序付けられたタプルの順列の通常の定義では、((0, 0), (0, 0)). そして、それはまさにあなたにitertools.permutations与えるものです。

どのように機能するかを見て関数を自分でpermutations書くか、ドキュメントのレシピセクションで関数を使用するか、結果を並べ替えて、または…を使用することができます。permutations_without_duplicatesunique_everseenunique_justseen

def one_duplicate_element_no_duplicates(n):
    yield from unique_everseen(one_duplicate_element(n))