はじめに
仮に4つの数字があるとします。順列で、その総数を求めたいと考えています。順列の総数は、数字の個数の階乗で求める事が出来ます。
- 1, 2, 3, 4 ⇒ n! = 4! = 24
と、このように、4つの数字の順列の総数を、4の階乗で求める事が出来ました。では、4つの数字のパターンが次のようなケースだとどうなるでしょう？
- 1, 1, 1, 1 ⇒ n! = 4! = 24? え？1通りじゃん…24も無いよね？
と、こんな感じになるわけです。このようなケースは「同じものを含む順列」として扱い、単なる階乗では求められません。別の公式が必要になってくるわけです。
「同じものを含む順列」公式
「同じものを含む順列」公式
n = 使われている数字の総数
a, b ... = 各数字が使われている個数
\frac{n!}{a!・b!・...}
数学的には、このような公式が使われます。これを元に、各数字のパターンを考えると、
問：与えられた数字の順列の総数を求めよ
例題 1： 1, 2, 3, 4
n = 4 使われている数字の個数
a = 1 「1」が使われている個数
b = 1 「2」が使われている個数
c = 1 「3」が使われている個数
d = 1 「4」が使われている個数
\frac{4!}{1!・1!・1!・1!} = \frac{4\times3\times2\times1}{1\times1\times1\times1} = \frac{24}{1} = 24
例題 2：1, 1, 1, 2
n = 4 使われている数字の個数
a = 3 「1」が使われている個数
b = 1 「2」が使われている個数
\frac{4!}{3!・1!} = \frac{4\times3\times2\times1}{3\times2\times1\times1} = \frac{24}{6} = 4
- パターン的には…
- 1, 1, 1, 2
- 1, 1, 2, 1
- 1, 2, 1, 1
- 2, 1, 1, 1
うん、これで合ってるみたいですね。
やはり数学的でパターンが決まっているので、コードを作るのがやりやすいかもしれないですね。とりあえずの印象としては、
- 各数字は配列に収めて操作したらよさそう
- 階乗を出すのが頻出する
- 分子/各分母は、
.reduce()を使うのがよさそう
やりたいこと
- 「同じものを含む順列」その総数を求める
- 上記公式を元にコードを作る
- 分子に、nの階乗を置く
- 分母用に、数字の個数と重複数を求める
- 分子/各分母を、
.reduce()で行う
それではこれを元に、コードを作成していこうと思います。
nの階乗を求める（分子用）
まず始めに、nの階乗を求めていきます。
n は、与えられた数字の全体の個数となります。
尚、階乗の求め方はいろいな方法があるとは思いますが、今回は、.reduce() を使った方法で行っています。
const permutation = (...arr) => {
/*---n の階乗を求める ---*/
const fact = [...Array(arr.length).keys()]
.reduce((a, c) => {
return a *= c + 1;
}, 1);
console.log(`${arr.length}! = ${fact}`);
}
permutation(1, 2, 3, 4); // 4! = 24
permutation(1, 1, 1, 2, 3); // 5! = 120
- 引数はスプレッド構文により可変長で、配列に変換される
- 配列を直接引数に入れたい場合は、スプレッドだけ取ってやれば、関数の他をいじらなくても動く
- 乗算なので
.reduce()の初期値は「1」 -
.reduce()の部分をもっと簡潔に書きたい場合は、波カッコとreturnを省略する
.reduce((a, c) => {
return a *= c + 1;
}, 1);
.reduce((a, c) => a *= c + 1, 1);
数字の個数と重複数を求める（分母用）
分母でもそれぞれの数字の階乗を作りたいので、使われている数字の個数と重複を調べる必要があります。しかし、どのような方法で出来るのか、ぱっとすぐには浮かびません。適当にネットを漁っていたら、よさそうな方法があったので、それを使っていきたいと思います。
const permutation = (...arr) => {
/*---数字の個数と重複数を求める ---*/
const obj = {};
for (let e of arr) {
obj[e] = (obj[e] || 0) + 1;
}
console.log(obj);
}
permutation(1, 2, 3, 4);
// {
// 1: 1,
// 2: 1,
// 3: 1,
// 4: 1
// }
permutation(1, 1, 1, 2, 3);
// {
// 1: 3,
// 2: 1,
// 3: 1
// }
うまく重複のカウントが出来ているようですね。
参考元の記事では、.reduce()や、通常のfor文で回す方法や、三項演算子で計算する方法も紹介されていましたが、すっきり簡潔に書けそうなのは、.forEach()や for of文と理論演算子の組み合わせかなと思いました。
順列の総数を求める（分子/各分母）
必要な材料がそろってきましたので、順列の総数を求めていきたいと思います。手順としては、次のように進めたいと思います。
- 手順1: 変数objのvalue値を抜出す（分母用）
- 手順2: 手順1を元に各要素数の配列を作る
- 手順3: 手順2を元にそれぞれの階乗を出す
- 手順4:
.reduce()で「分子/各分母」を行う（初期値はn!）
const permutation = (...arr) => {
/*const fact = ...省略*/
/*const obj = ...省略*/
const total =
/*手順1*/ Object.values(obj)
/*手順2*/ .map(v => [...Array(v).keys()])
/*手順3*/ .map(e => e.reduce((a, c) => a *= c + 1, 1))
/*手順4*/ .reduce((a, c) => a /= c, fact);
console.log(total);
}
permutation(1, 2, 3, 4); // 24
permutation(1, 1, 1, 2, 3); //20
ついでと言っては何ですが、各手順がそれぞれどういう結果になっているか、書いてみようと思います。
permutation(1, 1, 1, 2, 3);
/*---変数objのvalue値 ---*/
// 結果
[3, 1, 1]
/*---各要素数の配列 ---*/
// 結果
[[0, 1, 2], [0], [0]]
/*---それぞれの階乗 ---*/
// 結果
[6, 1, 1]
/*---分子/各分母 ---*/
// 結果
20
まとめ
const permutation = (...arr) => {
const fact = [...Array(arr.length).keys()]
.reduce((a, c) => a *= c + 1, 1);
const obj = {};
for (let e of arr) obj[e] = (obj[e] || 0) + 1;
const total =
Object.values(obj)
.map(v => [...Array(v).keys()])
.map(e => e.reduce((a, c) => a *= c + 1, 1))
.reduce((a, c) => a /= c, fact);
console.log(total);
}
permutation(1, 2, 3, 4); // 24
permutation(1, 1, 2, 2); // 6
permutation(1, 1, 1, 1, 1, 1, 1, 2); // 8
いかがだったでしょうか？
- 他にこんなのもあるよ
- もっと簡潔に書けるよ
- それ間違ってるよ
などありましたら、コメントでお待ちしております。
参考資料