Algorithme de réarrangement en temps réel sur place

Existe-t-il un algorithme de réarrangement temporel sur place linéaire? C'est l'algorithme que certaines mains particulièrement habiles sont capables d'exécuter: diviser uniformément un tableau d'entrée de taille égale, puis entrelacer les éléments des deux moitiés.

Mathworld a une brève page sur le shuffle de fusil . En particulier, je m'intéresse à la variété out-shuffle qui transforme le tableau d'entrée 1 2 3 4 5 6 en 1 4 2 5 3 6. Notez que dans leur définition, la longueur d'entrée est .$2n$

Il est simple d'effectuer cela en temps linéaire si nous avons un deuxième tableau de taille ou plus à portée de main. Copiez d'abord les derniers éléments dans le tableau. Ensuite, en supposant une indexation basée sur 0, copiez les premiers éléments des indices dans . Copiez ensuite les éléments du deuxième tableau dans le tableau d'entrée, en mappant les indices à . (Nous pouvons faire un peu moins de travail que cela, car les premier et dernier éléments de l'entrée ne bougent pas.)$n$$n$$n$$[0,1,2,...,n-1]$$[0, 2, 4,...,2n-2]$$n$$[0,1,2,...,n-1]$$[1,3,5,...,2n-1]$

Une façon de tenter de le faire sur place consiste à décomposer la permutation en cycles disjoints, puis à réorganiser les éléments en fonction de chaque cycle. Encore une fois, en supposant une indexation basée sur 0, la permutation impliquée dans le cas des 6 éléments est

$$\sigma=\begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 2 & 4 & 1 & 3 & 5\end{pmatrix}=\begin{pmatrix}0 \end{pmatrix} \begin{pmatrix}5 \end{pmatrix} \begin{pmatrix}1 & 2 & 4 &3 \end{pmatrix}.$$

Comme prévu, le premier et le dernier éléments sont des points fixes, et si nous permutons les 4 éléments du milieu, nous obtenons le résultat attendu.

Malheureusement, ma compréhension des mathématiques des permutations (et de leur ) est principalement basée sur wikipedia, et je ne sais pas si cela peut être fait en temps linéaire. Peut-être que les permutations impliquées dans ce brassage peuvent être rapidement décomposées? De plus, nous n'avons même pas besoin de la décomposition complète. Il suffit de déterminer un seul élément de chacun des cycles disjoints, car nous pouvons reconstruire le cycle à partir de l'un de ses éléments. Peut-être qu'une approche complètement différente est nécessaire.$\LaTeX$

De bonnes ressources sur les mathématiques connexes sont tout aussi précieuses qu'un algorithme. Merci!

Le problème est étonnamment non trivial. Voici une belle solution d'Ellis et Markov, Fusion in situ, stable par le biais du Perfect Shuffle (section 7). Ellis, Krahn et Fan, Computing the Cycles in the Perfect Shuffle Permutation réussissent à sélectionner des "chefs de cycle", au détriment de plus de mémoire. Le beau papier de Fich, Munro et Poblete, Permuting In Place , qui donne un algorithme général de temps pour le modèle oracle est également lié . Si seul un oracle pour la permutation est disponible, l'algorithme nécessite un espace logarithmique; si nous avons aussi un oracle pour l'inverse, il nécessite un espace constant.$O(n\log n)$

Maintenant pour la solution d'Ellis et Markov. Supposons d'abord . Ensuite, le calcul du shuffle parfait d'ordre n se réduit au calcul du shuffle parfait des ordres x et y , avec une rotation les précédant. Voici une preuve par exemple ( n = 5 , x = 3 , y = 2 ): 012 345 67 89 012 567 34 89 051627 $n = x+y$$n$$x$$y$$n=5$$x=3$$y=2$

$$\begin{array}{cc} 012\mathbf{345} & \mathbf{67}89 \\ 012\mathbf{567} & \mathbf{34}89 \\ 051627 & 3849 \end{array}$$

Ellis et Markov ont trouvé un moyen facile de calculer le shuffle parfait lorsque , en utilisant un espace constant et un temps linéaire. En utilisant cela, nous obtenons un algorithme pour calculer le mélange parfait pour n arbitraire . D'abord, écrivez n = 2 k 0 + ⋯ + 2 k w en utilisant l'encodage binaire de n , et soit n i = 2 k i + ⋯ + 2 k w . Tournez le milieu n 0 bits, mélangez la main droite 2 $n=2^k$$n$$n = 2^{k_0} + \cdots + 2^{k_w}$$n$$n_i = 2^{k_i} + \cdots + 2^{k_w}$$n_0$ bits. En ignorant les2 k 0 bits dedroite, tournez lesn1bitsdu milieuet mélangez les2 k 1 bits dedroite. Etc. Notez que la rotation est facile car les premiers éléments tournés fonctionnent comme des leaders de cycle. La complexité totale de la rotation estO(n0+⋯+nw)=O(n), puisquen t + 1 <nt/2. La complexité totale des shuffles internes estO$2^{k_0}$$2^{k_0}$$n_1$$2^{k_1}$$O(n_0 + \cdots + n_w) = O(n)$$n_{t+1} < n_t/2$ .$O(2^{k_0} + \cdots + 2^{k_w}) = O(n)$

Reste à montrer comment calculer le shuffle parfait lorsque . En fait, nous serons en mesure d'identifier les dirigeants du cycle, après un travail classique sur des colliers (Fredricksen et Maiorana, Colliers de perles en k couleurs et k -aire de séquences Bruijn , Fredricksen et Kessler, un algorithme pour générer des colliers de perles en deux couleurs ).$n=2^k$$k$$k$

Quel est le rapport? Je prétends que la permutation aléatoire correspond au décalage vers la droite de la représentation binaire. Voici une preuve par exemple, pour : 000 001 010 011 100 101 110 111 000 100 001 101 010 110 011 111 Par conséquent, pour trouver des chefs de cycle, nous devons trouver un représentant de chaque classe d'équivalence de la rotation de chaînes binaires de longueur k . Les articles mentionnés ci-dessus donnent l'algorithme suivant pour générer tous les chefs de cycle. Commencez avec 0 $n=8$

$$\begin{array}{cccccccc} 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\ 000 & 100 & 001 & 101 & 010 & 110 & 011 & 111 \end{array}$$ $k$$0^k$. À chaque étape, nous sommes à un moment donné . Trouver l'indice maximal i d'un bit zéro, diviser k par i pour obtenir k = d ⋅ i + r , et laisser le point suivant être ( a 1 … a i - 1 1 ) d a 1 … a r . Chaque fois que r = 0 , la nouvelle chaîne est un leader de cycle.$a_1 \ldots a_k$$i$$k$$i$$k = d\cdot i + r$$(a_1\ldots a_{i-1}1)^d a_1\ldots a_r$$r = 0$

Par exemple, lorsque cela génère la séquence 0000 , 0001 , 0010 , 0011 , 0101 , 0110 , 0111 , 1111$n=16$

$$\mathbf{0000}, \mathbf{0001}, 0010, \mathbf{0011}, \mathbf{0101}, 0110, \mathbf{0111}, \mathbf{1111}.$$

Les chefs de cycle sont mis en évidence.

C'était une question d'amorçage sur cs.stackexchange.com et une réponse est ici: /cs/332/in-place-algorithm-for-interleaving-an-array/400#400

Il s'agit d'une explication du document: http://arxiv.org/abs/0805.1598 .

$k$$2$$k$$3^2$$k=2$

$j \to 2j \mod 2n+1$

$m$$n = m-2$$i$$f(i) = 2\cdot i$$i \leq n/2$$f(i) = 2 \cdot (i \mod n/2) - 1$$i > n/2$

$O(1)$$O(\log n)$