LoginSignup
3

More than 5 years have passed since last update.

Go言語でアルゴリズムレッスンやってみるヅラ(再帰呼び出しとか)part1

Last updated at Posted at 2017-06-09

再帰呼出しとは

Wikipedia-再帰
簡単に言うと関数内で自分自身の関数を呼び出すこと
for文とかWhile文の代わりに使える

example.go
func example() {
    // somethig
    example()
}

題材

順列問題を題材にしましょう
Wikipedia-順列

区別可能な特定の元から有限個を選んで作られる重複の無い有限列をいう
アナグラムは順列の具体的な例なのでこれを求めるプログラムを書いてみよう

とあるファイルにアルファベットの文字列がたくさんはいってます。
この中からアナグラムの関係にある文字列を全て探し出しましょう。

一番最初に思いつくのは順列全パターン探しだして、
ファイルの上から順に探していくアルゴリズム。
まあ、理論上いけるはずなのでやってみよう。

N文字のアナグラムはNの階乗個存在しうるので、
単純なプログラムで書いた場合、計算時間は

(計算時間) = O(n!)

になります。

しかもメモリ上に13文字のアナグラムを全てのっけようとすると、
単純に

13!(bytes)=6.2270208(GB)

うーん。。僕の手元のマシンがメモリ8ギガなのでギリギリです。
14文字のアナグラムだと当然アウトです。
ファイルから14文字以降の文字列は予め消しておきます。

一旦再帰呼出しでアナグラムを全て求めよう。

やってみた

ソースコードはこちら

anagram.go
func anagramList(word string) []string {
  if len(word) == 1 {
    return []string {word}
  }

  ret := []string {}
  for i := 0; i < len(word); i++ {
    words := anagramList(word[0:i] + word[i+1:len(word)])
    for _, w := range(words) {
      ret = append(ret, word[i:i+1] + w)
    }
  }
  return ret
}

この部分が実際にアナグラムの候補を全パターン探し出す関数です。
引数にはアナグラムの元となる文字列をとります。

関数が何をしているのか

1.引数の文字列の長さをチェックし、1文字の場合、それ自身を配列に格納し返却
2.引数が2文字以上だった場合、文字列のi番目を取り除いたものを自分自身の関数に渡す
3.2の返却結果配列の要素全てについて2で取り除いたi番目の文字を先頭として文字列を結合し返却

これでアナグラムの候補が全て求まります。
2,3文字くらいで紙などに書いて試してみるとよくわかると思います。
ポイントは
1.1文字のアナグラム候補は自分自身1通りしかないこと
2.1文字取り除いて、残りの文字列でアナグラム候補を作り、先頭に取り除いた文字をくっつける、を全文字に対して処理することで求める全パターンが手に入る
ex) 'abc'のアナグラム候補は
'a' + アナグラム候補('bc') = 'a' + 'bc' or 'a' + 'cb'
'b' + アナグラム候補('ac') = 'b' + 'ac' or 'b' + 'ca'
'c' + アナグラム候補('ab') = 'c' + 'ab' or 'c' + 'ba'
∴('abc', 'acb', 'bac', 'bca', 'cab', 'cba')

これを文字数が増えても同じことをどんどん繰り返していく、ということです。

感想

再帰は難しいですが、使いこなせると非常に強力ですね。
リポジトリのコードはGo ver1.8で動作確認しているので動かしてみてください。
※めちゃくちゃ遅いです。

part2ではもっと速くアナグラム候補を探し出すアルゴリズムを実装します。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3