寄り道組み合わせ問題とつきあってみる

大筋については Rubyによる本編を参照されたい。
本編とおおむね同様に解くことができる。
```
"GAKKOU".split(’’).permutation.sort.uniq[100-1]
```
- JSでは Array.prototype.sprit に、空の正規表現（のつもりで） // を引数として渡そうとするとエラーになる。
  - ので、空文字列で split することになる。
  - 空文字列を渡せない訳ではないので、/(?:)/ あるいは new Regexp('') と書いてもいいが（正規表現にこだわるメリットはないね）、
  - // は、JSではコメント文字なので、この形で空正規表現は作れない（このページで議論している）。
- JSでは、（Rubyとは違い）Array#permutation や Array#uniq に相当するネイティブ関数がないので、後述のようにこの両方を用意してから動作確認する必要がある。

道具の準備 1 Array.prototype.uniq

重複要素を削除するメソッド uniq はもとは Unixのuniqコマンド（重複行の削除）に相当する機能を提供するためのもので、隣り合った要素の比較だけを行うことになっている（一般に sort してから使うことを想定しているため）。

たとえば [1,2,1].uniq() は、（２つの１は隣接していないので）何も削除しない。
いくつかの考え方でコーディングできるので列挙して示す。
reduce を使う
```
function uniq(a) {    //
  return(
    a.length < 1 ? a :
      a.slice(1).reduce((r,e)=>
        r.slice(-1)[0]==e ? r : r.concat([e]),
      [a[0]])
  )
}
```
- このメソッドは最初の要素を取り出して、残りの配列に対して .reduce を呼び出す作り方。なので、長さ０の配列を渡した時だけは違う処理が必要になる（ここでは引数として渡された a をそのまま返しているが、[] を返しても同じ）。
- JSの Array.prototype.reduce は、第１引数にリレーするための無名関数、第２引数として（必要ならば）初期値を渡す。
  - ここでは、最初の要素だけを格納した配列（ a.slice(0,1) でもいい）を初期値として、重複しない要素をその後ろに追加しながらリレーしていく。
  - 無名関数の２つの引数（上記では r と e）の型が違うもの（r は配列、e は要素）なので、reduce に初期値を渡す使い方が必要。
- 配列 a の、最初の要素を取り除いた残り、を表すために a.slice(1) を使っている。
  - a.slice(1,a.length) でもいい（が長くなる）。
  - ちなみにRubyではsliceは第２引数を省略するとサイズ１の配列を返すので違う動作になる。
- 無名関数の中で、配列 r の末尾の要素を取り出して e と比較している。末尾の要素は r[r.length-1] でも取り出せるが、ここでは r.slice(-1)[0] とした。
  - 本項と次項は、配列のページでも言及した要注意箇所。
  - rubyでは r[-1] でいいのだが、ここはJSの弱い所でもある。
- 配列 r の末尾に要素 e を追加した新たな配列を作る（つまり push のような破壊的メソッドを使わない）方法として、
  
  （ruby なら演算子 + を使って r+[e] と書けるが）メソッド Array.prototpye.concat を使って、r.concat([e]) と書くことになる。
再帰で書く
```
function uniq2(a) {   // 再帰バージョン
  if(a.length < 1 ) return []
  else {
    let top=a[0],
        r=uniq2(a.slice(1))  // slice(1,a.length) でも同じ
    return top==r[0] ? r : [top].concat(r)
  }
}
```
- 先頭要素（top）を取り除いた残りの配列に対して uniq2 を再帰呼び出ししてから、
  
  その結果（r）の先頭と top を比較し、違う値ならば先頭に挿入する、という手順。
- ただし上記のプログラムは若干ごまかしつつ実装していて、末端の呼び出しが [] を返してきてそれを変数 r で受け取ったあと、r[0] （存在しない要素）を評価している。JSでは、このアクセスは undefined を返すため == による比較式は false となる筈なので、問題なく動作はするが、同じロジックを他の言語で実装すると失敗する可能性はある。
  - ２行目を if(a.length <= 1 ) return a とするのが無難かも知れない。
末尾再帰で書く
```
function uniq3(a) {   // 末尾再帰バージョン
  if(a.length < 1 ) return []     // 長さ０の場合の特別扱い
  function uniq3_(h,t) {      // 内部関数を定義してこれを呼び出す
    // console.log(h,t)
    if(t.length < 1) return h
    else {
      let top=t[0], rest=t.slice(1)
      return(uniq3_(h.slice(-1)[0]==top ? h : h.concat([top]),rest))
    }
  }
  return(uniq3_(a.slice(0,1),a.slice(1)))
}
```
- 末尾再帰の場合、再帰呼び出すを重ねるにつれて、返すべき値を順次形成していき、末端に達したらその値を関数全体の値として返す、という流れになる。
  - そのため、もとの関数に、引数の数が１つ（返すべき値）加えられたものを内部関数として再帰的に使うことが多い
    
    （もとの関数にデフォルト値のある引数を予め準備しておいて、内部関数なしで作る、というアプローチもあるが）。
- 上記の例ではすでに重複検査ずみの前半部（head の頭文字で hとしている）をいずれ返すべき値として受け渡していく。初期値は a の先頭要素だけからなる配列（a.slice(0,1)）。
逐次バージョン
```
function uniq4(a) {   // 逐次バージョン
  let n=a.length, b=[...a], p=0
  for(let i=0; i<n-1 ; i++)
    if(a[i]!=a[i+1]) b[++p]=a[i+1]
  return(b.slice(0,p+1))
}
```
- これは関数型言語らしくない逐次型のコード（性能的には優れているが、この書き方しかできないプログラマにはならないようにしよう）。
- 結果を格納するための配列を（b として）用意する。長さは予測できないが、 a より長くなることはないので、単純に a をコピーすればいいだろう。
  
  ここではスプレッド構文（...を使う）でコピーしているが、 a.concat()、a.slice(0)、Array.from(a) などいくつかの書き方がある。
- for によるループで一時的変数 i を変化させるが、その範囲は（nではなく） n-1 の手前までとしている（添字 i と i+1 が指す要素を比較するためこれでいい）。
- b[0] にはすでに（a が空配列でない限り）a[0] と同じものが格納されているので、 a から b に転写する（その直前の要素と違う値ならば）ものは a[i+1] でいい。
- 転写先の（bの中での）添字は、それまでに転写されている最大添字（を p が保持している）に１を加えた値（引用直前に｀++p` でインクリメントするので）。
- b の（格納場所としての）長さは（a と同じく）n だが、最後に、格納済の範囲だけを .slice で切り出して返す（そのため長さは p+1 になる）。
  - なお、もとの配列 a が空配列だった場合は、forでは何も行われず、p は 0のまま。最後に slice して返すときに、長さとして p+1 つまり 1 が渡されるので、想定しない動作をしそうだが、
    
    実は JSでは Array.prototype.slice の第２第１引数にもとに配列の長さより大きい値を与えても、長過ぎる分は無視されるので、 uniq4([]) は [] を返すことになる
    
    （これはちょっと技巧的な手抜き方法だと言えるので、真似しない方がいいかも知れない）。
メソッドにする
```
Array.prototype.uniq = function () {    // メソッドにする
  return(
    this.length < 1 ? this :
      this.slice(1).reduce((r,e)=>{
        // console.log(r,e)
        return(r.slice(-1)[0]==e ? r : r.concat([e]))
      },[this[0]])
  )
}
```
- このコードは、先に示した関数 uniq(a) （reduce版）を、 Arrayに対するメソッドとして定義する書き方を示したもの。
  
  他のバージョンをメソッド化する時も考え方は同じ（なので省略した）。
- 引数はとらない。代わりに、対象となる配列は this として書くことになる。
- 先に示した例では、無名関数の本体は、単一の式だったのでブレースを省略し、return も省略して書いていたが、
  
  関数本体が複数の文から成る場合（といってもここではデバッグのための出力文はコメントアウトされていて結果的には文は１つになっているが）は上記のようにやや長い記述をする必要がある。

道具の準備 2 Array.prototype.permutation など

ここでも本編と同様に、複数の考え方での書き方を示す。
配列を前後に分解して再帰呼び出し（全要素を並び替える）
- 配列 a の i番目の要素を取り出すのは簡単（a[i]）だが、i番目を除いた配列を作るのは少し面倒。
  
  a.slice(0,i).concat(a.slice(i+1))
  
  （でもこれまでの説明を見ていればわかりますね？）
- これを各添字について生成してリストにする。[...a.keys()] で添字の範囲となる配列が生成できるのはこれまでにも見てきたとおり。
  
  [...a.keys()].map(i=>a.slice(0,i).concat(a.slice(i+1)))
- 関数自体は、以下のような外枠で定義することを前提とする。
```
function perm(a){
  // ...    中身はあとで作るとして
}
```
- 配列aから要素を１つ減らしたものに対する順列生成は、こう呼ぶことになる。 perm(a.slice(0,i).concat(a.slice(i+1)))
- 上記の生成物の先頭に、取り置いておいた１つの要素を付加する。perm が生成するのが順列（配列）の配列なので、それぞれについて同じことをさせるため、map を使う。
  
  perm(a.slice(0,i).concat(a.slice(i+1))).map(l=>[a[i]].concat(l))
- 配列 a の各添字について上記を行う。
```
[...a.keys()].map(i=>
  perm(a.slice(0,i).concat(a.slice(i+1))).map(l=>[a[i]].concat(l))
)
```
- 再帰呼び出しの関数なので、再帰呼び出し１レベルごとに引数となる配列の長さは漸次短くなる。その末端で、空配列（長さゼロ）が渡されたら、それ以上の呼び出しをせず、末端の値を返す。末端の値として [[]] がふさわしいことは、本編で述べたとおり。
```
function perm(a) {
  return a.length<=0 ? [[]] :
    [...a.keys()].map(i=>
      perm(a.slice(0,i).concat(a.slice(i+1))).map(l=>[a[i]].concat(l))
    ).flat()
}
```
  - 本編で（rubyで）解説したのと同様、配列の配列になっているものを、１段階、平滑化するため、ここでは Array.prototype.flat を呼んでいる。
    
    なお、RubyのArray#flattenを引数なしで呼ぶと完全に平滑化して１本の配列にするが、 JSではそれとは違い、flat を引数なしで呼んだときには１段だけ平滑化する仕様。
  これで完成したので、実験してみて下さい。
```
perm([1,2])
perm([1,2,3])
perm([1,2,3,4]).length    // あまり長くなるようなら 長さ（順列の数は n! ね）だけ確認しよう
```
長さを指定して nPm に相当する生成する。
```
function perm(a, lvl=a.length) {  // 長さを指定する（省略値は配列
  return lvl<=0 || a.length<=0 ? [[]] :
    [...a.keys()].map(i=>
      perm(a.slice(0,i).concat(a.slice(i+1)),lvl-1).map(l=>[a[i]].concat(l))
    ).flat()
}
```
変更箇所は３つ。
- 第２引数 lvl を受け取る（省略値は配列aの長さ）。名前はここでは lvl（level を縮めた）とした。
- 再帰呼び出しではその値を１つ減らしたものを渡す。
- 末端の判断（２行目）で、lvl が０かどうかも条件に入れる。

Arrayのメソッドにする

Array.prototype.perm = function (lvl=this.length) {  // Array に対するメソッドとして定義
  return lvl<=0 || this.length<=0 ? [[]] :
    [...this.keys()].map(i=>
      this.slice(0,i).concat(this.slice(i+1)).perm(lvl-1).map(l=>[this[i]].concat(l))
    ).flat()
}

Stringのメソッドにすることもできる
```
String.prototype.perm = function (lvl=this.length) {  // Array に対するメソッドとして定義
  return lvl<=0 || this.length<=0 ? [""] :
    [...this.keys()].map(i=>
      (this.slice(0,i)+this.slice(i+1)).perm(lvl-1).map(l=>[this[i]]+l)
    ).flat()
}
```
Array版との差異はそんなに多くない（ArrayとStringで共通の関数や機能が多いので）。
- 定義場所（String.prototype で Stringクラスのメソッドになる）。
- 文字列の連結は演算子 + で大丈夫（concat 不要）。
- 末端で返す値は、空文字（““）を要素とする長さ１の配列。
- なお、添字列を生成する場面ではその出発点は Array 関数でいいのでここは変更しないこと。
メソッド版は、以下のように動作確認できるだろう。
```
[1,2].perm()
[1,2,3].perm()
[1,2,3,4].perm().length
"abc".perm()
"abcd".perm()
```

道具の準備 3 Array.prototype.permutation の別解１

ここでは、添字を使って配列要素を切り出すことをせず、代わりに [要素１つ, それ以外の要素からなる配列] をタプルにしたもの（実体は配列だが）を、もとの配列の各要素について生成する所から出発する。

関数型言語での順列生成ではこれが標準的なアプローチのようだ。
```
function pickEach(a) {
  // console.log(a)
  if(a.length<=0) return []
  else {
    let top=a[0], rest=a.slice(1)
    return [[top,rest]].concat(pickEach(rest).map(([t,r])=>[t,[top].concat(r)]))
  }
}
```
この関数の動作は本編で解説したのとほぼ同じ、ただ、以下の点には注意が必要だろう。
- 配列の配列に対してmap を呼んだときの挙動は rubyとJavaScriptとで違う。
  - rubyでは .map{|a,b|...}のように２引数で受け取ればいいが、
  - JSではそれをそのまま括弧に変換して .map((t,r)=> ...) とはできず、 .map(([t,r])=> ...) のように配列として受け取る必要がある。
  - JSのmapなどの高階関数の多くは、第２（または関数によっては第３）引数として各要素のインデックス（添字）を受け取る仕様になっているため（これは失念してエラーに陥ってしまうことが多い）。

この pickEach を使うと、permは、比較的楽に書ける。

function perm(a) {
  return a.length<=0 ? [[]] :
    pickEach(a).map(([top,rest])=>perm(rest).map(l=>[top].concat(l))).flat()
}

メソッド版に変換する過程は省略する。

補足

uniq に相当するものを先に作ったが、unix の sort | uniq もしくは sort -u に相当することをJSで行うとき、Set（集合）データ型が使える。
- まず順列を生成し、これをSetに変換する。 new Set("GAKKOU".perm()) これにより重複が除去されている。
- これを、配列に展開（ここではスプレッド構文を使うと楽）してから Array.prototype.sort （これは組み込み関数）を呼ぶ。 [...new Set("GOKAKU".perm())].sort()[99]
この例では、先に作成した String.prototype.perm を使ったが、 Array.prototype.perm で生成すると、 new Set("GAKKOU".split(’’).perm()) 重複が除去されないので、期待した回答は得られない。
- これは、Set での同一性の検査のため === 演算子で比較していて、たとえば [1,2]===[1,2] が false となる（同値の配列を === で比較しても等価とならない）ことによる。

道具の準備４ Array.prototype.permutation の別解２

大筋は本編と同じ。

配列の一部（先頭から、wid個分の幅）を cnt回分転回（先頭要素を該当範囲の末尾にまわす）させる機能をまず実現する。

# 全体を転回するなら
a.slice(cnt).concat(a.slice(0,cnt))

# 部分を転回するなら
a.slice(cnt,wid).concat(a.slice(0,cnt)).concat(a.slice(wid))

# これを関数にしておこう
function p_rot(a,wid,cnt) {
  return a.slice(cnt,wid).
    concat(a.slice(0,cnt)).
    concat(a.slice(wid))
}

再帰的に呼び出すための内部関数を用意する。

function perm_(a,wid){
  # console.log(a,wid)
  return(wid>a.length?[a]:
    [...Array(wid).keys()].
      map(cnt=>p_rot(a,wid,cnt)).
      map(l=>perm_(l,wid+1)).
      flat()
  )}

それを呼び出すメインの関数

function perm(a) {
  return(perm_(a,1))
}

寄り道 組み合わせ問題とつきあってみる

道具の準備 1 Array.prototype.uniq

道具の準備 2 Array.prototype.permutation など

道具の準備 3 Array.prototype.permutation の別解１

補足

道具の準備 ４ Array.prototype.permutation の別解２

寄り道組み合わせ問題とつきあってみる

道具の準備４ Array.prototype.permutation の別解２