swiftでアナグラム
swift playgrouds での6番目のプログラミング。今回はアナグラムの生成。
アナグラムとは、単語の文字をいくつか入れ替えることで、別の単語を作り上げて、別の意味を持たせる遊びです。
ノストラダムスがナンダッテー ΩΩΩ に出てくる文字を入れ替えて別の単語にするアレです。
“/usr/share/dict/words” に英単語集があります。この単語集とコレクションクラスの各種メソッドを使って、与えられた英単語からアナグラムになる英単語を出力します。
入力例
let theAnagram = MTFAnagrams()
print(theAnagram.anagrams("thinker")) // thinker(思想家) -> rethink(再考)
print(theAnagram.anagrams("canoe")) // canoe(カヌー) -> ocean(海)
print(theAnagram.anagrams("orange")) // orange(オレンジ) -> onager(投石機)
print(theAnagram.anagrams("valencia")) // valencia(スペインの地名？) -> valiance(たれ布?カーテン?)
出力例
["rethink"]
["acone", "ocean"]
["onager"]
["valiance"]
ソースコードを分けた
ソースコードを分けて、別ファイルに入れると実行スピードが上がる。 おそらく、別ファイルにすることでトレース機能が及ばなくなるのだと思われる。
アナグラムを探し出すクラスは以下のようになってます。ファイルanagrams.swiftに書いている。
import Foundation
public struct MTFAnagrams
{
let wordSet: Set<String>
public init()
{
// - テキストファイルから読み込み、単語の集合を作る
let wordArray:[String] =
try! String.init(contentsOfFile:"/usr/share/dict/words") // ファイルから読み込み
.components(separatedBy:"\n") // 改行で分割し
self.wordSet = Set<String>(wordArray) // 単語の存在確認のために、集合にしておく。
}
public func anagrams(_ word:String) -> Set<String>
{
// 1単語毎に単語を入れ替えた仮のアナグラムを生成。
let anagrams = Set(
word.characters // 文字毎に分解
.flatMap{ String($0) } // 型を文字列に変換
.permutations() // 文字順を入れ替えた仮のアナグラムの配列を生成
.map{ $0.joined() } // 1文字毎だったものを連結
.flatMap // 仮のアナグラムが単語集wordSetにある場合は、アナグラムである。元の文字列と同じものは除く
{
(anagram:String) -> String? in
word != anagram && self.wordSet.contains(anagram) ? anagram : nil
}
)
return anagrams
}
}
swiftで特徴的なのは、クラスやメソッドの可視スコープです。 今まで、プレイグラウンドで1つのファイルでやっていたので気がつかなかったが、ファイルや、フレームワークがスコープの範囲になっています。
ファイルを分けたことで、別ファイルから利用するには、 “public” キーワードを付けました。
アルゴリズムに関してはコメントを参考にしてください。
また、アナグラムを作るのに、arrayにメソッド “permutations” を追加しました。ファイル “ArrayExtension.swift” にエクステンションを書いています。
import Foundation
extension Array
{
// 各要素の順列違いを全て生成する。n!個のパターンを作る。nが8を越えると猛烈に遅くなる。
// 注意：nが大きくなると爆発的に巨大な数になるのでカードゲームのシャッフルなどには使わないこと
// https://stackoverflow.com/questions/34968470/calculate-all-permutations-of-a-string-in-swift
public func permutations() -> [[Element]]
{
var scratch = Array(self) // This is a scratch space for Heap's algorithm
var result: [[Element]] = [] // This will accumulate our result
// Heap's algorithm
func heap(_ n: Int)
{
if n <= 1
{
result.append(scratch)
return
}
for i in 0..<n-1
{
heap(n-1)
let j = (n%2 == 1) ? 0 : i
swap(&scratch[j], &scratch[n-1])
}
heap(n-1)
}
// Let's get started
heap(scratch.count)
// And return the result we built up
return result
}
}
これは、可能な組合せの配列を返すメソッドです。コードは stackOverFlow から引用したものをコンパイルが通るように修正を加えただけ。
参考文献のサンプルコードからの移植の感想
元のコードはC++のSTLを使ったサンプルコードです。以下C++やObjective-Cとの違いの感想です。
- C++よりもエラーメッセージがわかりやすい
- クロージャーのおかげで、関数オブジェクトの事を考えなくて良く楽
- unixのフィルターを使った1行プログラミングに近い感じがする
- forよりもmapを使うと見た目がスッキリする事が多い
- 今回は使用しなかったが、forとカウンタ変数を使うよりも数列 ( 1…5 ) の表記とmapを組み合わせた方がキレイ。
- reduceよりも使えるならばjoinedを使うと見た目がキレイ。
後の課題は、オプショナルとアンラップがまだよくわかっていない。
参考文献とソースコード
- STL標準テンプレートライブラリによるC++プログラミング
- https://www.amazon.co.jp/STL―標準テンプレートライブラリによるC-プログラミング-Higher-education-computer/dp/4795296987