Hatena::ブログ(Diary)

分室の分室 このページをアンテナに追加

2016-09-11 Sun

riffle-shuffle (2つのリスト(の要素)を交互に混ぜる)

【568】(追記アリ)


 前回の記事に、がっくり & 苦笑い系のはてブコメが付いてましたが、そこはまあ諦めてください。 (^^; …人それぞれ微妙に理解度・習熟度・思惑が違うために、食いつく箇所や着地点が変わってしまうのだと思います。。。


 さて。

 リフル・シャッフルとは、カードの山札を半分ずつに分けて、パラパラと交互に重ねていくトランプ札の切り方を言う。詳しくはウィキペディアを参照されたし。》 https://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB …『シャッフル(カード)』をクリックしてください。

で、今回やりたいのは、つまりこういうこと。↓

    (0 2 4 6 8)
    (1 3 5 7 9) → (0 1 2 3 4 5 6 7 8 9)
    ; 2つのリスト(の要素)を交互に混ぜる



 以前、自分はこんなものを作ったことがあった。↓

;; 2014-05-19 Mon (リストを交互に分配)【476】
;; http://d.hatena.ne.jp/foussin/20140519/1400450778
;;
;; 主な目的:x座標、y座標の最大値・最小値や中心座標を求める時に使う
;; (Thanks, takatohさん → ほぼそのまま使わせてもらってます)
;;
;; つまりこういうこと。↓
;; (x0 y0 x1 y1 x2 y2) → ((x0 x1 x2) (y0 y1 y2))
;;
;; 連番を分配すると偶数と奇数に分かれる。↓
;; (0 1 2 3 4 5 6 7)   → ((0 2 4 6) (1 3 5 7))
;;
(define (deal-alternately ls)
  (let loop ((ls ls) (left '()) (right '()))
    (if (null? ls)
      (list (reverse left) (reverse right))
      (loop (cddr ls) (cons (car ls) left) (cons (cadr ls) right)) )))

今回の riffle-shuffle (2つのリストの要素を交互に混ぜる)は、
deal-alternately (リストを交互に分配) の逆を行う手続きになる。



 最近、とあるブログで intersperse という手続きの記事を読んだ。intersperse とは、次のようなことをするプロシージャ。↓

 gosh> (intersperse 0 '(1 2 3 4 5))
 (1 0 2 0 3 0 4 0 5)

 これの引数が文字列だったならば…。intersperse に文字列の引数を渡してやれば、 (apply string-append (intersperse str-sep str-lis))
…を実行するだけで、前回に自分が作った join-strings と同じことが出来る(リスト限定ではあるが)。 ...oh my god(なんてこった)...

 それと、前回の記事で触れた参考ブログに掲載されていた letrec を使ったコードが、引数を交互に cons してリストを作り直す点において、それは intersperse とほぼ同じことをやってると感じた。


 しかし、自分は他人が書いたコードをちらっと見たぐらいで理解できるほどのスキルは残念ながら持ち合わせていない。ただ、ある程度の想像は付く…要はリストを作り直すだけなので、単純に考えれば

sep-lis → '("" ":" ":" ...)

str-lis → '("1" "2" "3" ...)

new-lis → '() ;末尾再帰なら最後に reverse 実行

…のようなリストを作って交互に cons すればいいと思った。末尾再帰なら、何も考えずに最後に reverse すればいいと思う。sep-lis は次のように作ればいいかな。↓

(let ((sep-lis (cons "" (cdr (map (lambda (x) sep) str-lis))))) ...)

 アホみたいなコードだけど、目的は一応果たしているので良しとする。このようにして、sep-lis のリスト長を str-lis と揃えてしまえば、それは riffle-shuffle (2つのリストの要素を交互に混ぜる) という手続きを作ることで解決できる。で、今回は…前回のように map や for-each は使えない感じがする(ここがまだ上手く説明できない…)。

;; 2つのリスト(の要素)を交互に混ぜる (リフル・シャッフル)
;;
;; 今回やりたいのは、つまりこういうこと。↓
;;
;;    (0 2 4 6 8)
;;    (1 3 5 7 9) → (0 1 2 3 4 5 6 7 8 9)
;;
(define (riffle-shuffle lis1 lis2)
  (let loop ((left lis1) (right lis2) (ls '()))
    (if (null? left)
      (reverse ls)
      (loop (cdr left) (cdr right)
            (cons (car right) (cons (car left) ls)) ))))

 ネーミングが『リフル・シャッフル』なので、引数(リスト)は 2つに決め射ちとする。あと、今回はリスト専用(ベクタの場合はヘタに捻らず、素直に vector->list を使うつもり)。


実行例:↓

 gosh> (define (riffle-shuffle lis1 lis2)
   (let loop ((left lis1) (right lis2) (ls '()))
     (if (null? left)
       (reverse ls)
       (loop (cdr left) (cdr right)
             (cons (car right) (cons (car left) ls)) ))))
 riffle-shuffle
 gosh> (riffle-shuffle '(a b c d) '(A B C D))
 (a A b B c C d D)
 gosh> (define str-lis '("1" "2" "3" "4"))
 str-lis
 gosh> (define sep-lis (cons "" (cdr (map (lambda (x) ":") str-lis))))
 sep-lis
 gosh> (riffle-shuffle sep-lis str-lis)
 ("" "1" #0=":" "2" #0# "3" #0# "4")
 gosh> (display (riffle-shuffle sep-lis str-lis))
 ( 1 : 2 : 3 : 4)#<undef>
 gosh> (apply string-append (riffle-shuffle sep-lis str-lis))
 "1:2:3:4"
 gosh> (deal-alternately '(0 11 2 33 4 55))
 ((0 2 4) (11 33 55))
 gosh> (apply riffle-shuffle (deal-alternately '(0 11 2 33 4 55)))
 (0 11 2 33 4 55)

 ↑ Windows10 になって便利になったのは、コマンドラインに [ctrl]-[v] でコピペ出来るようになったこと。このお陰で、お試しコードを逐一ロードせずに直ちに動作検証できるようになった。これは便利。

 このコードでは復改 "\n" をリストに含めることができない。しかし、よく考えれば改行は副作用に過ぎないので、begin で囲んで最後に (newline) を記述すれば済む話だった。。。

 以前に作った deal-alternately は、多値に未対応の Script-Fu で実行する前提のため、((座標群A) (座標群B)) という戻り値を返す仕様だった。これを riffle-shuffle に渡す場合は apply を使えばいい。



 ところで、山札を完全に 2等分し、それを 1枚ずつ交互に噛み合わせる切り方をパーフェクト・シャッフルと呼ぶらしい。リフルでのパーフェクト・シャッフルは難しく、普通はファロー・シャッフルという方法でパーフェクト・シャッフルを実現するそうだ。で、そのパーフェクト・シャッフルを 8回繰り返すと最初の山札の状態に戻る…だそうだ。 → 追記:ただ、これは山札の総数が52枚の時限定の数理なのかもしれない…(そこはシミュレートしてみないと自分には分からない…)

 せっかくなので、これも試してみたい。今回は、山札を 2等分するために Gauche の take, drop を使ってみるつもり…だったんだけど、予想以上の長文になってしまったので、それはまた別の機会にでもやろうかな、と(やらないかも…)。。。

今回はこれでおしまい。


追記:2016.09.12 Mon 21:25

 こちらのブログで、こんな riffle-shuffle もあるよ、と教えてもらいました。

   http://blog.panicblanket.com/archives/3232
   riffle-shuffle (blog.PanicBlanket.com)

 zip, concatenate という手続きを使った例なのだけど、調べてみたら…

 gosh> (map list '(1 2 3) '(4 5 6))      ;(zip lis1 lis2)と等価
 ((1 4) (2 5) (3 6))
 gosh> (apply append (map list '(1 2 3) '(4 5 6)))      ;←!!
 (1 4 2 5 3 6)

 上記『;←!!』と、ほぼ同等のコードであると判明(わずかに apply より concatenate の方が効率がいいらしい)。 ...no way(マジすか)...

…もちろん末尾再帰の方が効率では断然勝ちのハズなんだけど、こんな簡単な方法があるとは思ってもいなかった…『(apply append (map list ...))』…この組み合わせは思いつかなかったな……orz

 と同時に『今回は map が使えない気がする』…と思っていた理由が分かった。append を使うことが避けられなくなるから…かな。。。