subsequences

.groovy

Groovy Sequence of a number - Stack Overflow から

def number = 169
// need a method in groovy to find the consecutive numbers that is, 1,6,9,16,69,169
// not 19!


Groovy には List#subsequences があるがどうやら連続しているものだけ欲しいらしい。

// Groovy のコメントによると items.inject([]){ ss, h -> ss.collect { it + [h] }  + ss + [[h]] } の意味
assert [1,6,9,16,19,69,169] == 169.toString().toList().subsequences()*.join()*.toInteger().sort()


Christoph Metzendorf 氏の回答がわかりやすかった。

 1 6 9 
 -----
 0 1 2  <-- index
 =====
[1]6 9  (i=0; j=0)
[1 6]9  (i=0; j=1)
[1 6 9] (i=0; j=2)
 1[6]9  (i=1; j=1)
 1[6 9] (i=1; j=2)
 1 6[9] (i=2; j=2)


同じように実装してみる。

continuous_subsequences = { list ->
  [].with {
    for (i in 0..<list.size())
      for (j in i..<list.size())
        it << list[i..j]
    it
  }
}
assert [1,6,9,16,69,169] == continuous_subsequences(169.toString().toList())*.join()*.toInteger().sort()


同じような問題がないか Rosetta Code を調べてみると 2 つ見つかった。

Greatest subsequential sum

連続する subsequences の中で sum が最大のものを探すらしい。
先程の実装を利用して

assert [3,5,6,-2,-1,4] == ([]+continuous_subsequences([-1,-2,3,5,6,-2,-1,4,-4,2,-1])).max { it.sum()?:0 }


Haskell の実装だと空リストも含んだ結果が返ってくる

subseqs = concatMap inits . tails


functionaljava 3.1 で inits のバグが直ったみたいなのでつかってみる。
functionaljava の作者の Tony Morris 氏が scalaz の作者でもあることに気がついた。
scalaz のソースは MS P ゴシックで表示できたがどのフォントでみればいいのだろう。

@Grab(group='org.functionaljava', module='functionaljava', version='3.1')
import fj.F
import static fj.data.List.list
import static fj.data.Java.List_ArrayList as LA

continuous_subsequences = { xs ->
  LA().f(list(*xs).tails().bind({ it.inits() } as F)).findAll { !it.empty }.collect { LA().f(it) }
}
assert [3,5,6,-2,-1,4] == continuous_subsequences([-1,-2,3,5,6,-2,-1,4,-4,2,-1]).max { it.sum()?:0 }
Non-continuous subsequences

逆に連続しないものだけ欲しいらしい。

先程の実装を使う。

non_continuous_subsequences = { xs -> xs.subsequences() - continuous_subsequences(xs) }
assert non_continuous_subsequences(1..3) == [[1,3]] as Set
assert non_continuous_subsequences(1..4) == [[1,3],[1,4],[2,4],[1,2,4],[1,3,4]] as Set


Category:Ruby - Rosetta Code がわかりやすいので実装してみる。
subsequences から連続していないものだけ選ぶ。

non_continuous_subsequences = { xs ->
  (0..<xs.size()).subsequences().findAll {
    [it, it.tail()].transpose().any { a, b -> a+1 != b }
  }.collect { xs[it] } as Set
}


Haskell で同じ方法のものもあったのでこれも実装してみる。

continuous = null . dropWhile not . dropWhile id . dropWhile not
ncs xs = map (map fst . filter snd . zip xs) $
           filter (not . continuous) $
             mapM (const [True,False]) xs

mapM と dropWhile は Groovy にはないので少し変えてみた。

non_continuous_subsequences = { xs ->
  ([[true, false]] * xs.size()).combinations().findAll { bs ->
    !bs[bs.indexOf(true)..bs.lastIndexOf(true)].every() && bs.any()
  }.collect { bs ->
    [xs, bs].transpose().findAll { x, b -> b }*.first()
  } as Set
}


他に再帰による実装あった。
Haskell の Generalized monadic filter は意味がよく分からない。

2011-06-18 追記

書くのを忘れていたけど functionaljava はセントラルリポジトリにないので自分でビルドしなければならない。
sbt の使い方が分からないので sourceDirectory に core/src を指定して mvn で生成した。


再帰による実装。
多分 monadic filter も >= 3 があるので同じように考えているのだと思う。
[] のケースは collect で消されてしまう。
s が 3 以上になるということは x の選択、未選択、選択を経ているということ。

non_continuous_subsequences = { seq, s=0 ->
  if (seq) {
    def (x, xs) = [seq.head(), seq.tail()]
    def (i, j) = s % 2 ? [0, 1] : [1, 0]
    return non_continuous_subsequences(xs, s + i).collect { [x, *it] } + non_continuous_subsequences(xs, s + j) as Set
  } else
    return s >= 3 ? [[]] : []
}