巡回置換の積 (2)

http://www.sampou.org/cgi-bin/haskell.cgi?blog%3aEveryday%3a2005-01-04&l=jpより。

篩い。

sieve _ [] = []
sieve elem (x:xs) = x:sieve elem [y | y <- xs, not (head y `elem` x)]

orbits elem span = sieve elem . map span

数学的にはelemはパラメータにしなくてもいいのだけれど。

置換群の場合(軌道*1 )。

toCycles p = orbits elem span
  where span =  (\(x:xs) ->  x:takeWhile (/= x) xs) . iterate p

p1 = (listArray (1, 9) [5,3,9,4,7,2,1,8,6] !)

*D050104> toCycles p1 [1..9]
[[1,5,7],[2,3,9,6],[4],[8]]

整数の場合(軌道もどき*2 )。

primes = map head $ orbits elem' span [2..]
  where 
    x `elem'` xs = x `elem` takeWhile (<= x) xs
    span n = map (* n) [1..]

*D050104> take 10 primes
[2,3,5,7,11,13,17,19,23,29]

関連

[Haskell] 巡回置換の積 (1) [id:yts:20050106#p1]

*1: 群<p>が集合[1..9]に作用している

*2:自然数しか掛けていない