Commande d'un tableau 2D

Question

J'essaie de résoudre un problème sur des tableaux 2D et j'ai besoin de peu d'aide. Le problème est le suivant:

Supposons que nous ayons un tableau 2D de taille nxn comprenant des éléments uniques. La nécessité de réorganiser les éléments de A comme suit. Soit A11, A12, A21, A22 quatre sous-réseaux mutuellement disjoints de A, chacun de taille n/2 x n/2. Alors A11 < A12 < A21 < A22. Si chacune de ces sous-matrices est scindée récursivement en quatre sous-matrices de taille égale, alors la propriété est également vérifiée.

Entrée utilisateur: n, N (≥ n2). n est une puissance de 2

J'ai essayé beaucoup de choses mais rien ne semble fonctionner.

Answer 1

Vous devez créer une fonction qui va convertir un index entre 0 et n * n-1 en coordonnées dans votre tableau en fonction de la commande en question. Ensuite, vous exécutez un algorithme de tri habituel 1D, sur un tableau de taille n * n, dont l'élément j est remplacé par cette fonction. Cela résout le problème.

Mise à jour: les numéros de cartes de fonction de mappage dans cette matrice à leurs coordonnées:

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

Answer 2

ferroutage quelque peu sur la réponse de Unkulunkulu Je pense que vous pouvez l'aborder comme suit:

Prendre toutes les valeurs votre matrice (2D) et placez-les dans un tableau simple (1D). Ensuite, prenez ce tableau et triez les valeurs du plus bas au plus haut.

Maintenant, ce que vous devez faire est de remplir à nouveau la matrice mais de manière à ce qu'elle soit conforme aux règles que vous avez spécifiées. Si vous jetez un oeil à un Z-order space filling curve in 2D, vous constaterez que si vous remplissez votre matrice dans cet ordre (avec les éléments triés), que la matrice résultante a vos propriétés désirées.

Maintenant, coder ce serait à vous de décider.

Answer 3

Le livre recettes livre chapitre 21.8 http://www.nrbook.com/nr3/ donne une expression analytique pour calculer un index dans le tableau 2D donné les coordonnées d'un quadtree.

Voici une autre approche avant droite que j'ai essayé, mais je ne l'aime pas autant:

(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