Permutation

順列はn個からk個を選ぶ順序付きの数え方であり、P(n,k)=n!/(n-k)! で計算する。全順列の個数はn!である。

目的

順序付きの選択を数え上げる、組合せ論の基礎である。

メカニズム

P(n,k) = n!/(n-k)! = n×(n-1)×…×(n-k+1)。全順列はP(n,n)=n!。重複ありの順列はP(n,k)=n^k。円順列はP(n,k)=(n-1)!。全順列の生成にはバックトラッキングまたはHeapのアルゴリズムを使う。

ユースケース

順列の生成と列挙（enumeration）
パスワード強度の計算
スケジューリングと順序問題
確率の計算（プロバビリティ）

例

入力
```
P(5,3)=5!/(5-3)!=60
```
Output
```
60
```
Ordered arrangements of 3 out of 5

よくあるエラー

Confusing permutations with combinations (ordered vs unordered): Permutations are ordered (P), combinations unordered (C)

関連用語

組み合わせとは、n 個から順序を考慮せずに k 個を選ぶ選び方の数 C(n,k)=n!/(k!(n-k)!)、すなわち二項係数である。

階乗 n! = n×(n-1)×...×1 は順列と組合せの基礎である。極めて速く増大し、20! はすでに 64 ビット整数の範囲を超える。

関連ツール

高精度計算ツール

High-precision arithmetic calculator. No floating-point errors。無料、プライベート、100%クライアントサイド。

References