あのぞんブログ

組み合わせ・順列プログラミングそれぞれまとめ nPr nCr nHr nΠr

2021-07-29

順列を扱うための情報をまとめました。

4 パターン表

名前英語記号A,B から 2 つ
順列PermutationnPrAB BA
重複順列Peramutation with replacementnΠrAA AB BA BB
組合わせCombinationnCrAB
重複組合わせCombination with replacementnHrAA 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

© 2021 あのぞんびより All Rights Reserved