2D配列の配列

Question

2D配列の問題を解決しようとしており、ほとんど役に立たない。問題は次のようになります。

一意の要素で構成されるサイズnxnの2D配列Aがあるとします。 Aの要素を次のように並べ替える必要がある。 A11、A12、A21、A22を、それぞれサイズn/2×n/2のAの4つの互いに分離したサブアレイとする。次にA11 < A12 < A21 < A22。これらのサブアレイのそれぞれを再帰的に4つの等しいサイズのサブアレイに分割すると、そのプロパティも保持されます。

ユーザー入力：n、N（≥n2）。 nは2の累乗です

私は多くのことを試みましたが、何も動作していないようです。

Answer 1

0からn * n-1までのインデックスを問題の順序に従って配列の座標に変換する関数を作成する必要があります。次に、通常の1Dソートアルゴリズムを、サイズn * nの配列に実行します。jの要素は、その関数を使用して置換されます。それは問題を解決します。その座標にこの行列でマッピング機能マップ番号：

更新

0 1 4 5 
2 3 6 7 
8 9 12 13 
10 11 14 15 

Answer 2

unkulunkuluの答えに多少ピギーバック、私は次のようにあなたがそれに近づくことができると思う：

は、内のすべての値を取りますあなたの行列（2D）を単純な配列（1D）に入れてください。次に、この配列をとり、値を最低から最高までソートします。

これで、行列をもう一度入力するだけで、指定したルールに従います。 Z-order space filling curve in 2Dを見ると、この順序で（ソートされた要素を使用して）マトリックスに記入すると、結果として得られるマトリックスに望ましい特性があることがわかります。

これを実際にコーディングすることは、あなた次第です。

Answer 3

書籍の数値レシピの章21.8 http://www.nrbook.com/nr3/は、クォッドツリーの座標が与えられている2D配列のインデックスを計算するための解析式を示しています。ここで

私が試した別の簡単な方法があるが、私はできるだけ多く、それを好きではない：

(defun quad-pos (pos) 
    "POS is a list of letters that indicate the position in a 2x2 matrix [a,b; c,d]." 
    (let ((x 0) 
    (y 0) 
    (s 1)) 
    (dolist (e pos) 
     (setf s (/ s 2)) 
     (ecase e 
    ('a) 
    ('b (incf x s)) 
    ('c (incf y s)) 
    ('d (incf x s) (incf y s)))) 
    (values x y))) 
#+nil 
(quad-pos '(a)) ;=> 0, 0 
#+nil 
(quad-pos '(a b c)) ;=> 1/4, 1/8 
#+nil 
(quad-pos '(d d d d)) ;=> 15/16, 15/16