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

この問題はネットで最近みかけた記事（出典はどこかの駅に掲示された予備校の受験生応援のメッセージを掲載したポスターらしい）から借用したもの。
問題：「GAKKOU の6文字を並び替えてできる360個の文字列を辞書式に並べるとき、100番目の文字列を求めよ」

以下のようにirbで試してみて下さい

"GAKKOU".split(//)
"GAKKOU".split(//).permutation.size   # 6! の値と同じですね
(1..6).reduce(:*)   # 確認
"GAKKOU".split(//).permutation.to_a   # 720個ぶんの行がご丁寧に出力される
    # のでわざわざ to_a しなくてもいいが
"GAKKOU".split(//).permutation.sort   # これでアルファベット順にならぶ
    # が、文字 K が２つあるので、重複が発生する。重複の解消のため、
"GAKKOU".split(//).permutation.sort.uniq.size
    # ちょうど半分になることがわかりますね
"GAKKOU".split(//).permutation.sort.uniq[100]
    # こういう勘違いはRuby(でもCでもJavaでも）あるあるだが、これは101番め
"GAKKOU".split(//).permutation.sort.uniq[100-1]
    # もちろんいきなり99と書いてもいい
# 予想通りの答えでしたか

ついでに Array#permutation を作ってみる

基本的な考え方：
- 文字列の、各文字（あるいは、配列の各要素）を順々に取り出して先頭に置き、
- その文字（要素）を除いた残りの文字列（配列）について順列を生成する。
例として、”ABCDE” の順列は
- ”A”を先頭として、”BCDE”の順列を列挙
- ”B”を先頭として、”ACDE”の順列を列挙
:

というふうに５文字分を順に作って並べればいい
以下の例では、
```
a="ABCDE".split(//)
```
のようなデータが設定されていることを仮定する。
- 各文字を取り出す：
```
for i in 0...a.size do puts i end
  # 添字を順々に取り出す書き方
for i in 0...a.size do puts a[i] end
  # 要素を順々に取り出す書き方
```
これが出発点になる（でもあとで書き換えるが）。
添字 i で指定された以外の（つまり残りの）要素からなる配列（Rubyではこれを１つのメソッドで呼ぶ方法は用意されていない、ので）
```
n=a.size  # これも前提としておこう
a[0,i]+a[i+1,n-1]
  # 0以上n未満 の任意のiの値について、これで「残り」が
  # 取り出せることを確認したい
(0...n).map{|i|a[0,i]+a[i+1,n-1]}
  # この式で取り出せることを確認しよう
# なお、文字（要素）を１つずつ（先頭に置くために）取り出すときも、
(0...n).map{|i|[a[i]]}
  # このように、要素１つの配列の形にしておくといい
  # （あとで Array#+ を使って配列の連結をするため）
```
- 前項では for による繰り返し（.eachメソッドと同じ意味）で表現したが、上記のように .map で結果（ブロックを評価した値）をリストにする方が有用だろう。
- なお、0...n のようにピリオド３つでつないで範囲を生成する、Rangeリテラルの記法では、0からはじまりn-1 までの範囲（終端 n は含まれない）を生成する。配列の要素を網羅的に扱う時に有用な記法。

配列の順列を生成する関数を、たとえば perm という名前で作るとする。と、

def perm(a)
  # これから中身を作る
end
# のように定義することになる。

# 残りの順列は、この関数の中で、部分列を渡す再帰呼び出しを使って
perm(a[0,i]+a[i+1,n])
  # と書けば生成できることになる
  # （まだpermの中身が完成していないので動作しないが）

関数 perm は配列の配列を返す関数、ということになるだろう。

再帰的に読んだpermの値（配列の配列）に収められた、部分列のそれぞれの順列について、先頭に予めとってあった文字（要素）をくっつけるためには、配列の連結（演算子 +）をつかえばいい。

[1,2]+[3,4]
  # これで連結演算子の動作が理解できるだろう
perm(a[0,i]+a[i+1,n]).map{|l|[a[i]]+l}
  # （この式はまだ動作しないが）順列一つ一つが map メソッドの中で
  # 変数 l に拘束されて、先頭の値（リストにしてある）の後ろに
  # 連結され、それらがあらためて配列の形になる、という式がこれ

もとの配列 a に対して、（最初にやったように）要素を１つずつ順に取り出し（つまり添字を順々に変化させて）、それを先頭文字に置いて部分配列の順列と連結する、その手順は、
```
(0...(n=a.size)).map{|i|
  perm(a[0,i]+a[i+1,n]).map{|l|[a[i]]+l}
}
```
このように i を変化させる map メソッドで包むことで実現できる。
- 配列の寸法は Array#size （または length）で得られるが、あとで使うよう、Rangeリテラルの中で変数n に代入している。
  
  （旧来の手続き型言語の感覚で、あらかじめ代入のための一行の文を記述してもいいが、この程度の長さなので代入式を括弧で包んで外側の式に活用する、というスタイルで提示している）

上記の式では map を２階建てで使っていることに注意されたい。 map が配列を生成するので、 map の map は配列の配列を生成する。たとえば、

[[["A","B","C"],["A","C","B"]],
 [["B","A","C"],["B","C","A"]],
 [["C","B","A"],["C","A","B"]]]

のようになる。

これを順列のリストにするために、配列を一段階平坦化する必要がある。 Array#flatten を使おう。

[[["A","B","C"],["A","C","B"]],
 [["B","A","C"],["B","C","A"]],
 [["C","B","A"],["C","A","B"]]].flatten
=> ["A","B","C","A","C","B","B","A","C",
    "B","C","A","C","B","A","C","A","B"]
# これだと全体が１本のリストになる（これは平坦化しすぎ）   
[[["A","B","C"],["A","C","B"]],
 [["B","A","C"],["B","C","A"]],
 [["C","B","A"],["C","A","B"]]].flatten(1)
=>[["A","B","C"],["A","C","B"],
   ["B","A","C"],["B","C","A"],
   ["C","B","A"],["C","A","B"]]
# この形で permが値を返すことにする

perm は再帰関数で、先頭にするための一要素を減らした残りの配列、つまり１つ短くなったリスト再帰呼び出しに使われる、つまり再帰呼び出しが１段深くなるごとに引数（配列）のサイズは１ずつ短くなる。

再帰関数は確実に末端（これ以上の再帰呼び出しをしない状態）に達するように作られている必要があり、

perm では、引数のリストの長さが１か０になった時点で末端だとみなすことができる。
- １でもいいのだが長さ０つまり空配列を末端とする方がコードがシンプルになるので、ここでは空配列かどうかで判定することにする。
- その時に返すべき値は、[[]] （空の配列１つを要素にもつ配列）が適切なもの。
- （これはじっくり考えて納得していただきたいところだが）外側のブラケット（要素１つの配列）は、permの値に対してmap が呼び出される時に、各１回、連結の演算子が実行されるようにするため。
  
  内側のブラケット（空配列）は、その連結演算子の右辺として渡され、何もつかぐものがない（この段では連結演算子は無駄に呼び出される）ことを示すためのもの。
以上をまとめるとこういうコードになる。
```
def perm(a)
  a.empty? ? [[]] : (0...(n=a.size)).map{|i|
    perm(a[0,i]+a[i+1,n]).map{|l|[a[i]]+l}
  }.flatten(1)
end
```
実在の Array#permutation と同じ動作（第２引数で順列の長さを指定できる）にするためにはさらに若干の変更が必要になる。
```
def perm(a,lvl=a.size)
  (lvl<=0 or a.empty?) ? [[]] : (0...(n=a.size)).map{|i|
    perm(a[0,i]+a[i+1,n],lvl-1).map{|l|[a[i]]+l}
  }.flatten(1)
end
```
- 第２引数（省略されたら第一引数の配列寸法の値）lvlが順列の長さを表す。
- 再帰呼び出しの際にそのlvlは１つ少ない値が渡され、 lvl の値で末端の判断を行う。
- 配列 a の長さよりも大きい値を間違えてlvlとして渡してしまった時にも誤動作させないよう、末端判断の式に a.empty? も加えてある。
- 以下のように呼び出すことができる筈。
```
perm "ABCDE".split(//)

  # というふうに、文字列を配列に分解してから呼び出す、
  # という構想で作ってきたが、実は、
perm "ABCDE"
  # のようにいきなり文字列を渡ししても動作する
  # （ただし結果は配列に分解された形になるが）
```
- Rubyでは配列に対するメソッド（要素を抜き出す slice相当のメソッド等）が文字列に対ても同じ名前同じ呼び方のメソッドとして提供されていることが多いためこれが成立する。
- なお、いくつかの言語（Haskell, Erlang 等）ではそもそも文字列が文字のリスト（配列のようなもの）として実装されているので、文字列とリストを区別しないコーディングを行うのが普通になっている。
これをArrayに対するメソッドとして使うためには、以下のように書く。
```
class Array
  def perm(lvl=self.size)
    (lvl<=0 or self.empty?) ? [[]] : (0...(n=self.size)).map{|i|
      (self[0,i]+self[i+1,n]).perm(lvl-1).map{|l|[self[i]]+l}
    }.flatten(1)
  end
end
＃ と定義しておいて
"ABCDEF".split(//).perm
"ABCDEF".split(//).perm(5)
  # のように呼ぶ
```
- class Array の中で関数定義を行う。
- 第一引数として配列を渡す必要がないので省く。変数 a として受け取る代わりに、メソッドのレシーバ（ピリオドの左側）であるオブジェクトは self という　名前でアクセスできる。
- 再帰呼び出しの箇所は、メソッド呼び出しの形に書き換えられる。
Stringクラスに対するメソッドも用意するなら、
- 上記のコードを class String の中にも定義する、というのでもいいし、
- ラッパー関数のようなものを用意して、
```
class String
  def perm(lvl=self.size)
    self.split(//).perm(lvl).map(&:join)
  end
end
```
  こんな形で Array#permを呼び出すという方法もある（ここでは文字列に戻すところまで行っている）。

permutation 関数的な実装１

配列やリストを扱う際に添え字を変化させてループさせる実現方法は、現在の関数型言語では一般的ではない。

添字を使わない書き方もここに示しておこう。

まず、配列の各要素について、[その要素・それを取り去った残りのリスト]を組にしたもの、をリストにする関数を作る。

def pickEach(a)
  if a.empty? then [] else
    top,rest=a.first,a.drop(1)
    [[top,rest]]+pickEach(rest).map{|t,r|[t,[top]+r]}
  end
end

たとえば以下のように動作する筈。

pickEach("ABC".split(//))
=> [["A", ["B", "C"]],
    ["B", ["A", "C"]],
    ["C", ["A", "B"]]]

もう少し詳しく見てみる。
- "ABC".split(//) に対する最初の呼び出しで、
```
top => "A"
rest => ["B,C"]`
```
  なので、
```
[top,rest] => ["A", ["B", "C"]]
```
  これが結果の最初の要素になる（あとで連結させるためにこの時点でもう１重の [] で包んである）。
- 上記の rest (A 以外の列) に対する pickEach(rest) の結果は、
```
=> [ ["B",["C"]], ["C",["B"]]]
```
  というリストであり（再帰呼び出しの結果としてそうなる）、
  
  そのそれぞれの要素を加工するために .map が呼ばれているが、
  
  たとえば最初の要素について（mapのブロック内部を）見れば、
```
t => "B"      # 単独の文字列
r => ["C"]    # 文字列の配列
```
  この状態で [t,[top]+r] の値は、["B", ["A","C"]] となる。つまり右側のリストの先頭に "A" が挿入される。
- このようにして、`[着目した要素, [それ以外のリスト]]`` のリストが生成される。
これを使って、permを定義してみる
```
def perm(a)
  a.empty? ? [[]] :
    pickEach(a).map{|top,rest|
      perm(rest).map{|l|[top]+l}
    }.flatten(1)
end
```
- （再帰呼び出しが進行して末端に達して）a が空の時については後述するとして、
- まず pickEach が呼ばれ（前項参照）、その結果に対して .map が呼ばれる（これを「外側の.mapとしておく）。その最初の要素では、
```
top => "A"
rest => ["B","C"]

  # なので、
perm(rest) => [["B","C"], ["C","B"]]   
  # 再帰呼び出しにより２要素の順列が生成される
```
このリストに対して、さらに（内側の）.map が呼ばれ、たとえば最初の要素では、　
```
l => ["B","C"]
  # なので、
[top]+l => ["A","B","C"]
  # となる
```
これが順列のうちの１つ。
- 内側の .map が（最初の回で）返す値は、 “A” を先頭（top) にした２つの順列（リスト）のリスト、つまり
```
=> [["A","B","C"], ["A","C","B"]]  
```
  これが “B”, “C” についても作られるが、
  
  それぞれのリストはリスト+リスト+リストの形で連結されるのではなく、（外側の）.map が生成するので
```
[リスト, リスト, リスト]
# 或いは
[[順列, 順列], [順列, 順列], ...]
```
  の形になる。これを平坦な [順列, 順列, 順列, 順列, …] の形にするために .flatten(1) が必要になる。
- 再帰呼び出しが１レベル深くなる毎に、引数のリストの長さが１つずつ短くなる。１要素のリスト、たとえば [“A”] を引数 a として perm　が呼ばれると、
```
pickEach(a) => ["A",[]]
# map の中では
top => "A"
rest => []
```
  ここで更に再帰的に perm([]) が呼ばれるが、この perm([]) が空配列を返してしまうと、次の .map で何もせずに .map も空配列を返し、
  
  それを戻された側の（呼び出し元の） perm でも値を持たない、空配列の連鎖が発生してしまう。
  
  ここでは（つまり空配列に対する permは）要素を１つもつ配列を返す必要があり、その要素は空配列であるのが適切（というのを以下に確認しよう）。
```
rest => []
  # のとき、
perm(rest) => [[]]
# このリストに対して `.map` が呼ばれ、
# そのブロックの中では、
l => []
  # さらに
  top => "A"
  # と仮定して説明をしていたので
[top]+[] => ["A"]
```
  これが .map の各要素の値（といってもここでは１つだけだが）なので、 .map の結果は [[“A”]]、 flatten(1) して、[“A”] となる。
  
  大回りしながら結局はこのレベルでは引数の値とまったく同じ値である [“A”] を返しているのだが、
  
  （再帰呼び出しの）浅い所でも深い所でも同じコードでも期待どおりの値を返させるために必要な工夫であると言える。

permutation 関数的な実装２

もう１つ、rotate を使う書き方も紹介しておく。
- 配列を転回させる（指定された数の要素を配列の後ろにまわす）メソッド。
- こんなコードでも代用はできる。 def rot(a,cnt=1) a.drop(cnt)+a.take(cnt) end
たとえば配列の最初３つの要素を転回させる（残りはそのまま）コードは、
```
a[0,3].rotate(1)
# これを使って、
a[0,3].rotate(1)+a[3...a.size]
```
と書ける。
- 最初２つの要素の場合ならば、転回イコール交換なので、rotate(1)でぜんぶの場合を尽くしていることになるが、
- 最初の３つ、の場合、rotate(1)、 rotate(2)を考慮する必要がある。
- 順列の生成においては、それに加えて rotate(0) 、つまりもとの配列から変化しないものも含めて考慮する必要がある。
```
(0...3).map{|i|a[0,3].rotate(i)+a[3...a.size]}
```
- これで最初の３要素を転回させる３つのパターンを生成できる。
- 数字の 3 が入っている箇所を（たとえば変数名）wid に置き換えると「最初の wid 要素」に対するコードになる。
これを使った順列生成は、
- wid=2 から出発して、
- 生成された（最初の２要素の）転回パターン２つ、それぞれについて、
- wid=3 の転回パターンを各３つ（合計６つになる）を生成、さらにそのそれぞれに
- wid=4 … というふうに幅を順次増やしていく。
- これは再帰呼び出しで実現できる。
- wid == a.size の段まで行うと、せんぶの順列の可能性を列挙できることになる。
```
def perm(a)
  def perm_(a,wid)
    p [wid,a]       # 動作確認用。必要なければコメントアウト
    wid>a.size ? [a]:
      (0...wid).
        map{|i|a[0,wid].rotate(i)+a[wid...a.size]}.
        map{|l|perm_(l,wid+1)}.
        flatten(1)
  end
  perm_(a,2)
end
```
- 再帰呼び出しは、perm の内部関数 perm_ で行うことにしよう。
- perm_ が、値を返す直前に flatten(1) を呼ぶ必要があるのは、前に紹介した方法のときと同じ理由。
なお、この手順の場合は、配列の中から要素を「選択する」プロセスを通らないため、 _nP_m のように全体の中から一部を選択した順列を生成するのには不向きだと考えられるので、一部選択の可能なコードにはここでは深入りしないことにしておく。
- 必要ならば、
```
perm([*1..5]).map{|a|a[0...3]}.sort.uniq
# または 集合を扱うデータクラス Set を使って
Set[*perm([*1..5]).map{|a|a[0...3]}].to_a
```
  のような生成は可能（全体の順列を生成する無駄な処理を含むが多くの場合は気にしなくてい大丈夫）だろう。
なお、上記の関数 permはStringクラスを対象にして呼び出すことは（現時点では）できない。
- これは rotateがArrayクラスのメソッドである（Stringには使えない）から。
- 先に示した代用関数 rot も（take, drop もArrayクラス用なので）使えないが、 def rot(a,cnt=1) a[cnt...a.size]+a[0...cnt] end のようにスライスを使う書き方ならば ArrayにもStringにも使える。
- 或いは、データ変換をしてrotateしてから元に戻す、ラッパーメソッドを下記のように用意するという手もあるだろう。
```
class String
  def rotate(wid=1)
    self.split(//).rotate(wid).join
  end
end
```

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

ついでに Array#permutation を作ってみる

permutation 関数的な実装 １

permutation 関数的な実装 ２

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

permutation 関数的な実装１

permutation 関数的な実装２