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

## はじめに
仮に4つの数字があるとします。順列で、その総数を求めたいと考えています。順列の総数は、数字の個数の階乗で求める事が出来ます。
- 1, 2, 3, 4 ⇒ n! = 4! = 24

と、このように、4つの数字の順列の総数を、4の階乗で求める事が出来ました。では、4つの数字のパターンが次のようなケースだとどうなるでしょう？

- 1, 1, 1, 1 ⇒ n! = 4! = 24? え？1通りじゃん…24も無いよね？

と、こんな感じになるわけです。このようなケースは「同じものを含む順列」として扱い、単なる階乗では求められません。別の公式が必要になってくるわけです。
### 「同じものを含む順列」公式

:::note info
「同じものを含む順列」公式

n = 使われている数字の総数
a, b ... = 各数字が使われている個数
```math
\frac{n!}{a!・b!・...}
```

:::

数学的には、このような公式が使われます。これを元に、各数字のパターンを考えると、

:::note
　問：与えられた数字の順列の総数を求めよ

例題 1： 1, 2, 3, 4

n = 4　使われている数字の個数
a = 1 「1」が使われている個数
b = 1 「2」が使われている個数
c = 1 「3」が使われている個数
d = 1 「4」が使われている個数

```math
\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」が使われている個数

```math
\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()`を使うのがよさそう

## やりたいこと

1. 「同じものを含む順列」その総数を求める
2. 上記公式を元にコードを作る
3. 分子に、nの階乗を置く
4. 分母用に、数字の個数と重複数を求める
5. 分子/各分母を、`.reduce()` で行う

それではこれを元に、コードを作成していこうと思います。

### nの階乗を求める（分子用）
まず始めに、nの階乗を求めていきます。
n は、与えられた数字の全体の個数となります。
尚、階乗の求め方はいろいな方法があるとは思いますが、今回は、`.reduce()` を使った方法で行っています。

```js
const permutation = (...arr) => {

    /*---n の階乗を求める ---*/
    const fact = [...Array(arr.length).keys()]
        .reduce((a, c) => {
            return a *= c + 1;
        }, 1);
		
    console.log(`${arr.length}! = ${fact}`);
} 
```

```js: 結果
permutation(1, 2, 3, 4); // 4! = 24
permutation(1, 1, 1, 2, 3); // 5! = 120
```

- 引数はスプレッド構文により可変長で、配列に変換される
- 配列を直接引数に入れたい場合は、スプレッドだけ取ってやれば、関数の他をいじらなくても動く
- 乗算なので`.reduce()` の初期値は「1」
- `.reduce()` の部分をもっと簡潔に書きたい場合は、波カッコと`return` を省略する

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

```js:after
        .reduce((a, c) => a *= c + 1, 1);
```

### 数字の個数と重複数を求める（分母用）
分母でもそれぞれの数字の階乗を作りたいので、使われている数字の個数と重複を調べる必要があります。しかし、どのような方法で出来るのか、ぱっとすぐには浮かびません。適当にネットを漁っていたら、よさそうな方法があったので、それを使っていきたいと思います。

```js
const permutation = (...arr) => {

    /*---数字の個数と重複数を求める ---*/
    const obj = {};
	for (let e of arr) {
        obj[e] = (obj[e] || 0) + 1;
    }
    
    console.log(obj);
} 
```

```js:結果
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
// }
```

うまく重複のカウントが出来ているようですね。
[参考元の記事](https://qiita.com/saka212/items/408bb17dddefc09004c8
)では、`.reduce()`や、通常の`for`文で回す方法や、三項演算子で計算する方法も紹介されていましたが、すっきり簡潔に書けそうなのは、`.forEach()`や `for of`文と理論演算子の組み合わせかなと思いました。

### 順列の総数を求める（分子/各分母）
必要な材料がそろってきましたので、順列の総数を求めていきたいと思います。手順としては、次のように進めたいと思います。
- 手順1: 変数objのvalue値を抜出す（分母用）
- 手順2: 手順1を元に各要素数の配列を作る
- 手順3: 手順2を元にそれぞれの階乗を出す
- 手順4: `.reduce()` で「分子/各分母」を行う（初期値はn!）

```js
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);
} 
```

```js:結果
permutation(1, 2, 3, 4); // 24
permutation(1, 1, 1, 2, 3); //20
```

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

```js:手順1
permutation(1, 1, 1, 2, 3);

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

```js:手順1 → 2
/*---各要素数の配列 ---*/
//　結果
[[0, 1, 2], [0], [0]]
```

```js:手順1 → 2 → 3
/*---それぞれの階乗 ---*/
//　結果
[6, 1, 1]
```

```js:手順1 → 2 → 3 → 4
/*---分子/各分母 ---*/
//　結果
20
```

## まとめ

```js:「同じものを含む順列」の総数を求めるコード
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);
} 
```

```js:結果
permutation(1, 2, 3, 4); // 24
permutation(1, 1, 2, 2); // 6
permutation(1, 1, 1, 1, 1, 1, 1, 2); // 8
```

いかがだったでしょうか？
- 他にこんなのもあるよ
- もっと簡潔に書けるよ
- それ間違ってるよ

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

### 参考資料

https://qiita.com/saka212/items/408bb17dddefc09004c8

https://qiita.com/shepabashi/items/27b7284d1f0007af533b