[質問] [アルゴリズム]2次元配列の45度回転

[izy00466]

はじめまして。一瀬といいます。
もしかするとポピュラーなアルゴリズムかもしれませんが質問です。

元の2次元配列から、「時計回りに45度回転させた配列」と「逆時計回りに45度回転させた配列」を取得したい。というか、斜め同士の要素を連結したリ
ストに変形したい。

こんなときのやり方を教えて頂きたく投稿しました。

具体的には、元の配列として
((1 2 3 4) (11 12 13 14) (21 22 23 24) (31 32 33 34)
つまり
( (1 2 3 4)
(11 12 13 14)
(21 22 23 24)
(31 32 33 34))
があるとき、上を時計周りに45度回転させた配列
1
11 2
21 12 3
31 22 13 4
32 23 14
33 24
34
つまり、「((1) (11 2) (21 12 3) (31 22 13 4) (32 23 14) (33 24) (34))」
や、逆時計回りに45度回転させて
4
3 14
2 13 24
1 12 23 34
11 22 33
21 32
31
つまり、「((4) (3 14) (2 13 24) (1 12 23 34) (11 22 33) (21 32) (31))」
を取得するポピュラーな方法を教えて下さい。
※ 各要素に座標インデックスを付けて無理矢理配列をつくるというより、リスト操作でうまいことできたら気持ち良いだろうなと思ったりしています。

[Masakazu Takahashi]

いまいちスマートじゃありませんが、リスト操作で右ななめ 45 度やってみました。

(def a '((1 2 3 4) (11 12 13 14) (21 22 23 24) (31 32 33 34)))

(defn tilt [l m r]
(if (and (empty? l) (empty? m))
r
(let [fl (first l)
nm (filter not-empty (map rest m))
nr (map first m) ]
(recur (rest l)
(if (empty? l) nm (cons (rest fl) nm))
(cons (if (empty? l) nr (cons (first fl) nr)) r) ))))

(println (reverse (tilt a () ())))
;; -> ((1) (11 2) (21 12 3) (31 22 13 4) (32 23 14) (33 24) (34))

2011/3/19 izy00466 <izy0...@gmail.com>:

--
Masakazu Takahashi (emasaka)

[Toshiaki Maki]

makingです

久々にClojureで書いてみました(汗)

リストの破壊的操作をしたかったのですが、Clojureだと汚くなっちゃいますね、、

(defn rearrange [m]
(map deref
(loop [n 0 ret '()]
(if (>= n (count zm))
ret
(recur (inc n)
(concat (take n ret)
(keep-indexed (fn [i e]
(if (> (count ret) (+ n i))
(ref
(let [r (nth ret (+ n i))]
(dosync
(ref-set r (concat @r
(list e))))))
(ref (list e))))
(nth m n))))))))

(defn clockwise-rotate "時計回りに45度回転" [m]
(rearrange (apply map list m)))

(defn counterclockwise-rotate "逆時計回りに45度回転" [m]
(rearrange (map reverse m)))

もとのリストを

(1 11 21 31)
(2 12 22 32)
(3 13 23 33)
(4 14 24 34)

にしてから
一行ずつ

1
11
21
31
↓

1
11 2
21 12

31 22
32
↓

1
11 2
21 12 3
31 22 13

32 23
33
↓
…
としたかっただけです。。

2011年3月19日16:19 izy00466 <izy0...@gmail.com>:

--
#|--------------------------------------
Toshiaki Maki
E-mail: ma...@ik.am
URL: http://blog.ik.am
----------------------------------------|#

[izy00466]

速攻の対応に感謝いたします。
一瀬です。

2次元配列の斜め方向の検索という意味で考えると何かポピュラーな方法がありそうな気がして質問を出したのですが、やはりゴリゴリと並べ替えるというの
が一般的な考え方ということでよいのでしょうか?
90度や180度の回転モノはけっこう簡単にできたのですが、45度(ななめ)の場合まで含めて考えると何か一般的なアルゴリズムがありそうな気がして
ムズムズしております。

[Takahiro Hozumi]

こんにちは。

＞ 2次元配列の斜め方向の検索という意味で考えると何かポピュラーな方法がありそうな気がして質問を出したのですが、やはりゴリゴリと並べ替えるとい
うのが一般的な考え方ということでよいのでしょうか?

分からないですが、結局私もゴリゴリと並べ替える感じになりました。
ただ、90度にも45度にも取れるので少し汎用的かもしれません。

まずもとのリストを反時計回りに270度回転したのをベースに考えます。
((31 21 11 1)
(32 22 12 2)
(33 23 13 3)
(34 24 14 4))
右端から縦に値を取ることで目的のリストを取得するようにしたいと思います。
このまま右端から縦に値を取るともとのリストになります。

反時計回りに45度回転するには
(( 31 21 11 1 nil nil nil)
( nil 32 22 12 2 nil nil)
( nil nil 33 23 13 3 nil)
( nil nil nil 34 24 14 4))
のようにリストを一段ずつシフトして、空きを適当な値で埋めます。
右端から縦に値を取り、余計なのを取り除けば目的のリストが得れます。

((4) (3 14) (2 13 24) (1 12 23 34) (11 22 33) (21 32) (31))

https://gist.github.com/877755

[izy00466]

おはようございます。
一瀬です。

ほんとうに、ありがとうございます。
これだけの人数で考えても、やはりゴリゴリ感は残るのはしょうかがないということのようですね。
Common Lispだったら、このゴリゴリ感は気にならないのですが、Clojureの場合だともっとスッキリと解決できそうな気がするムズムズ感
は伝わったでしょうか。

[Yasuto TAKENAKA]

こんばんわ。竹中です。

On Saturday, March 19, 2011 10:33:12 PM UTC+9, izy00466 wrote:

2次元配列の斜め方向の検索という意味で考えると何かポピュラーな方法がありそうな気がして質問を出したのですが、やはりゴリゴリと並べ替えるというの
が一般的な考え方ということでよいのでしょうか? 

作ってみたけど、予め４５度になった物を更に４５度回転をさせるというものには対応させてません。一応、n*mの２次元リストまでは対応できてます。この手の物って、インデックスに必ず法則性があるので、それを上手に使えるかどうかじゃないですかね？ここではリストの位置を[x,y]とすると４５度回転させたものは x+yが全て一定になるという性質がありますね。それを活かすということを考えた。インデックスから始めるということで、趣旨に合わないかもしれません。

(defn mk-idx [lst]

  (let [len-x (count lst) len-y (count (first lst))]

    (filter not-empty

    (map #(reverse

   (for [x (range len-x) y (range len-y) :when (= % (+ x y ))]

     [x y]))

 (range (dec (* len-x len-y)))))))

(defn rotate45 [lst]

  (let [idx-lists (mk-idx lst)]

    (map (fn [idx-list]

    (map (fn [[x y]]

   (nth (nth lst x) y))

 idx-list))

 idx-lists)))

(defn rotate-45 [lst]

  (map reverse

       (rotate45 (map reverse

      lst))))

user> (def a

'( (1  2  3  4) 

 (11 12 13 14) 

 (21 22 23 24) 

 (31 32 33 34)) )

#'user/a

user>  (rotate45 a)

((1) (11 2) (21 12 3) (31 22 13 4) (32 23 14) (33 24) (34))

user>  (rotate-45 a)

[Yasuto TAKENAKA]

すいません mk-index関数のところで掛け算と足し算を間違ってしまって、先程の回答はややこしいものになってます。少し簡単になります。

(defn mk-idx [lst]

  (let [len-x (count lst) len-y (count (first lst))]

    (map #(reverse

  (for [x (range len-x) y (range len-y) :when (= % (+ x y ))]

    [x y]))

(range (dec (+ len-x len-y))))))