「同じものを含む順列」その総数を求める（練習） #JavaScript

はじめに

仮に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 を省略する

before

        .reduce((a, c) => {
            return a *= c + 1;
        }, 1);

after

        .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

ついでと言っては何ですが、各手順がそれぞれどういう結果になっているか、書いてみようと思います。

手順1

permutation(1, 1, 1, 2, 3);

/*---変数objのvalue値 ---*/
//　結果
[3, 1, 1]

手順1 → 2

/*---各要素数の配列 ---*/
//　結果
[[0, 1, 2], [0], [0]]

手順1 → 2 → 3

/*---それぞれの階乗 ---*/
//　結果
[6, 1, 1]

手順1 → 2 → 3 → 4

/*---分子/各分母 ---*/
//　結果
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

いかがだったでしょうか？

他にこんなのもあるよ
もっと簡潔に書けるよ
それ間違ってるよ

などありましたら、コメントでお待ちしております。

「同じものを含む順列」その総数を求める（練習）