2021-07-29
順列を扱うための情報をまとめました。
4 パターン表
| 名前 | 英語 | 記号 | A,B から 2 つ |
|---|---|---|---|
| 順列 | Permutation | nPr | AB BA |
| 重複順列 | Peramutation with replacement | nΠr | AA AB BA BB |
| 組合わせ | Combination | nCr | AB |
| 重複組合わせ | Combination with replacement | nHr | AA AB BB |
もう少しだけ複雑な例
順列
4P2(4 個の中から 2 個選んで並べる)
AB AC AD BA BC BD CA CB CD DA DB DC
[0, 1][0, 2][0, 3][1, 0][1, 2][1, 3][2, 0][2, 1][2, 3][3, 0][3, 1][3, 2]重複順列
類語: sequence with repetition、 直積、全列挙。
2([0,1])Πn で n 桁の bit 全探索になる。 4Π2(重複ありで 4 個の中から 2 個選んで並べる)
AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
[0, 0][0, 1][0, 2][0, 3][1, 0][1, 1][1, 2][1, 3][2, 0][2, 1][2, 2][2, 3][3, 0][3, 1][3, 2][3, 3]組合わせ
4C2(4 個の中から 2 個選ぶ)
AB AC AD BC BD CD
[0, 1][0, 2][0, 3][1, 2][1, 3][2, 3]重複組合わせ
4H2(重複ありで 4 個の中から 2 個選ぶ)
AA AB AC AD BB BC BD CC CD DD
[0, 0][0, 1][0, 2][0, 3][1, 1][1, 2][1, 3][2, 2][2, 3][3, 3]コード例
Rust
use itertools::{iproduct, Itertools};
// permutation
(0..3).permutations(2)
// [0, 1][0, 2][1, 0][1, 2][2, 0][2, 1]
// permutation with replacement
iproduct!(0..3, 0..3)
// (0, 0)(0, 1)(0, 2)(1, 0)(1, 1)(1, 2)(2, 0)(2, 1)(2, 2)
// combination
(0..3).combinations(2)
// [0, 1][0, 2][1, 2]
// combination with replacement
(0..3).combinations_with_replacement(2)
// [0, 0][0, 1][0, 2][1, 1][1, 2][2, 2]重複順列だけ Rust の経験が浅くてわからないです。 擬似言語で言うこんな書き方ができれば実現できそうです。
// 引数 r 個分同じ長さの配列を Rest parameters(残余構文)で渡す
iproduct!(...(0..3).repeat(2))Python
import itertools
itertools.permutations('ABCD', 2)
# AB AC BA BC CA CB
itertools.product('ABCD', repeat=2)
# AA AB AC BA BB BC CA CB CC
itertools.combinations('ABCD', 2)
# AB AC BC
itertools.combinations_with_replacement('ABCD', 2)
# AA AB AC BB BC CCこの記事を共有する