RubyのcombinationをSwiftでも使いたい

2016年9月15日追記

Swift 3.0 に対応させました。

memowomome.hatenablog.com

めちゃくちゃ久しぶりに Swift 触ったわ。。。

追記ここまで。

---

最近codeIQの問題にSwiftでもちょくちょく挑戦してます。
それまでRubyで解くことが多かったので、配列操作のあれが無いこれが無いといった感じで不便さを満喫しております。

combinationとrepeated_combinationはその中でも特に良く使うのでSwift版を作りました。

all-user/swift_combination

stack overflowから拾ってきたコード

ググってたらすでに良い感じのコードがあった。
Rubyのrepeated_combinationと同じように動く。

stack overflow : Apple Swift - Generate combinations with repetition

func combos(var array: Array, k: Int) -> Array<Array> {
    if k == 0 {
        return [[]]
    }

    if array.isEmpty {
        return []
    }

    let head = [array[0]]
    let subcombos = combos(array, k - 1)
    var ret = subcombos.map {head + $0}
    array.removeAtIndex(0)
    ret += combos(array, k)

    return ret
}

シンプルで分かりやすいのですが、遅い。

再帰呼び出しを使って配列をちぎっては投げを繰り返しているので、大量に配列を扱うことになりコストが高くなっているのだと思います。

forループで書きなおす

forループで書き直したら約８倍速くなりました。

できるだけRubyと同じように使えるようにしました。
だったらRuby使えばいいじゃんていうね、ありがとうございます。

基本的な使い方

let a = [1, 2, 3, 4]

println(combination(a, 1)) // => [[1], [2], [3], [4]]
println(combination(a, 2)) // => [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
println(combination(a, 3)) // => [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
println(combination(a, 4)) // => [[1, 2, 3, 4]]
println(combination(a, 0)) // => [[]]
println(combination(a, 5)) // => []

配列のインスタンスメソッド

// Array method

println(a.combination(3))
// => [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

引数にブロック（クロージャ）を渡す

// with closuer

a.combination(2){ println($0) }
// =>
// [1, 2]
// [1, 3]
// [1, 4]
// [2, 3]
// [2, 4]
// [3, 4]


let chrs = ["h", "e", "l", "o", "!"]
chrs.repeatedCombination(6){ combo in
    if join("", combo) == "hello!" { println(combo) }
}
// => [h, e, l, l, o, !]