Python は、シーケンスの順列と組み合わせを見つけるための直接的な方法を提供します。これらのメソッドは itertools パッケージに存在します。
順列
まず itertools パッケージをインポートして、Python で順列メソッドを実装します。このメソッドは入力としてリストを受け取り、すべての順列をリスト形式で含むタプルのオブジェクト リストを返します。
Python3
Java例外処理をスローする
# A Python program to print all> # permutations using library function> from> itertools>import> permutations> # Get all permutations of [1, 2, 3]> perm>=> permutations([>1>,>2>,>3>])> # Print the obtained permutations> for> i>in> list>(perm):> >print> (i)> |
>
>
出力：
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)>
時間計算量: O(n!)。n は入力リストの長さです。 nがあるからです！ n 個の要素の順列があり、プログラムはそれらすべてを生成して出力します。
補助スペース: O(n!)、プログラムはすべての n! を保存する必要があるためです。並べ替えを印刷する前にメモリ内に保存します。具体的には、permutations([1, 2, 3]) を呼び出して作成された perm 変数には、すべての n! が格納されます。メモリ内の順列をリストとして保存します。
それはnを生成します！入力シーケンスの長さが n の場合の順列。
長さ L の順列を取得したい場合は、この方法で実装します。
Python3
# A Python program to print all> # permutations of given length> from> itertools>import> permutations> # Get all permutations of length 2> # and length 2> perm>=> permutations([>1>,>2>,>3>],>2>)> # Print the obtained permutations> for> i>in> list>(perm):> >print> (i)> |
>
>
出力：
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)>
このプログラムの時間計算量は O(n^r) です。ここで、n は入力配列の長さ、r は生成される順列の長さです。
すべての順列は印刷前にメモリに保存されるため、空間複雑性も O(n^r) になります。
nCr * r を生成します!入力シーケンスの長さが n で、入力パラメーターが r の場合の順列。
組み合わせ
このメソッドは、リストと入力 r を入力として受け取り、長さ r の可能なすべての組み合わせをリスト形式で含むタプルのオブジェクト リストを返します。
Python3
# A Python program to print all> # combinations of given length> from> itertools>import> combinations> # Get all combinations of [1, 2, 3]> # and length 2> comb>=> combinations([>1>,>2>,>3>],>2>)> # Print the obtained combinations> for> i>in> list>(comb):> >print> (i)> |
>
>
出力：
(1, 2) (1, 3) (2, 3)>
1. 組み合わせは、入力の辞書編集順に出力されます。したがって、入力リストがソートされている場合、組み合わせタプルはソートされた順序で生成されます。
Python3
Javaの配列リストメソッド
# A Python program to print all> # combinations of a given length> from> itertools>import> combinations> # Get all combinations of [1, 2, 3]> # and length 2> comb>=> combinations([>1>,>2>,>3>],>2>)> # Print the obtained combinations> for> i>in> list>(comb):> >print> (i)> |
>
>
出力：
(1, 2) (1, 3) (2, 3)>
2. 要素は、値ではなく位置に基づいて一意であるものとして扱われます。したがって、入力要素が一意である場合、各組み合わせに繰り返し値は存在しません。
Python3
# A Python program to print all combinations> # of given length with unsorted input.> from> itertools>import> combinations> # Get all combinations of [2, 1, 3]> # and length 2> comb>=> combinations([>2>,>1>,>3>],>2>)> # Print the obtained combinations> for> i>in> list>(comb):> >print> (i)> |
bash if 条件
>
>
出力：
(2, 1) (2, 3) (1, 3)>
3. 同じ要素を同じ要素に組み合わせたい場合は、combinations_with_replacement を使用します。
Python3
# A Python program to print all combinations> # with an element-to-itself combination is> # also included> from> itertools>import> combinations_with_replacement> # Get all combinations of [1, 2, 3] and length 2> comb>=> combinations_with_replacement([>1>,>2>,>3>],>2>)> # Print the obtained combinations> for> i>in> list>(comb):> >print> (i)> |
>
>
出力：
(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)>