Mueva todos los elementos impares hacia la mitad izquierda e incluso colóquelos en la mitad derecha en su lugar

1. Obtenga la sub-matriz más grande que tenga el tamaño 3 ^k +1
2. Aplique el algoritmo del líder del ciclo a las partes de este subarreglo, comenzando desde las posiciones 1, 3, 9, … 3 ^k-1 : mueva el elemento a su posición correcta en el subarreglo (elementos con índice par a la izquierda del sub -Matriz, impar-indexado – a la derecha), el elemento reemplazado también debe moverse a su posición correcta, etc. hasta que este procedimiento regrese a la posición de inicio. Este documento brinda una explicación de la teoría de números por la cual tal selección de posiciones de inicio mezcla el subarreglo al orden correcto.
3. Procese las partes restantes de la matriz recursivamente, utilizando los pasos 1 y 2.
4. Ahora solo necesitamos unir las partes reordenadas. Comience con las sub-matrices más pequeñas al final de toda la matriz. Para intercambiar las mitades de la matriz secundaria, use el algoritmo inverso: inverso (inverso (a), inverso (b)); o, para mitades de sub-array de igual tamaño, use swaps pares.
5. Ahora todos los elementos incluso posicionados están a la izquierda. Para obtenerlos a la derecha, según sea necesario, intercambie los elementos i e i + N / 2 por todos i = 0 .. N / 2-1.

Algoritmo está en el lugar, la complejidad del tiempo es O (N).

Ejemplo:

 0 1 2 3 4 5 6 7 8 9 10 11 (the original array) 0 1 2 3 4 5 6 7 8 9 # 10 11 (split to sub-arrays) 0 2 4 3 8 1 6 5 7 9 # 10 11 (first cycle leader iteration, starting with 1) 0 2 4 6 8 1 3 5 7 9 # 10 11 (second cycle leader iteration, starting with 3) 0 2 4 6 8 9 7 5 3 1 # 10 11(2nd half of 1st part& 1st half of 2nd part reversed) 0 2 4 6 8 10 1 3 5 7 9 11 (both halves reversed together) 

Variación de este algoritmo, que no necesita el paso 5:

• En el paso 1, obtenga la sub-matriz más grande que tenga el tamaño 3 ^k -1.
• En el paso 2, mueva los elementos pares indexados a la derecha de la sub-matriz, impar-indexado – a la izquierda. Use las posiciones de inicio 0, 2, 8, … 3 ^k-1 -1 para el algoritmo de ciclo líder.

Aquí hay diferentes algoritmos O (N log N) in situ, que no necesitan pruebas de teoría de números:

1. Reinterpreta tu matriz como una secuencia de matrices 2 * 2 de un solo elemento, transpone estas matrices.
2. Reinterpreta el resultado como una secuencia de matrices 2 * 2 de dos elementos y transpórtalas.
3. Continúe mientras el tamaño de las matrices es menor que el tamaño de la matriz.
4. Ahora solo tenemos que unir las partes reordenadas juntas (exactamente como en el algoritmo anterior).
5. Intercambia elementos de las mitades izquierda y derecha de la matriz (exactamente como en el algoritmo anterior).

Ejemplo:

 0 1 2 3 4 5 6 7 (the original array) [0 2] [1 3] [4 6] [5 7] (first transposition) [0 2] [4 6] [1 3] [5 7] (second transposition) 

Este problema es solo un caso especial de la transposición de matrices in situ .

Traté de implementarlo como dijo Evgeny Kluev, y aquí está el resultado:

 #pragma once #include  #include  #include  #include  #include  #include  #include  template< typename Iterator > struct perfect_shuffle_permutation { static_assert(std::is_same< typename std::iterator_traits< Iterator >::iterator_category, std::random_access_iterator_tag >::value, "!"); using difference_type = typename std::iterator_traits< Iterator >::difference_type; using value_type = typename std::iterator_traits< Iterator >::value_type; perfect_shuffle_permutation() { for (difference_type power3_ = 1; power3_ < std::numeric_limits< difference_type >::max() / 3; power3_ *= 3) { powers3_.emplace_back(power3_ + 1); } powers3_.emplace_back(std::numeric_limits< difference_type >::max()); } void forward(Iterator _begin, Iterator _end) const { return forward(_begin, std::distance(_begin, _end)); } void backward(Iterator _begin, Iterator _end) const { return backward(_begin, std::distance(_begin, _end)); } void forward(Iterator _begin, difference_type const _size) const { assert(0 < _size); assert(_size % 2 == 0); difference_type const left_size_ = *(std::upper_bound(powers3_.cbegin(), powers3_.cend(), _size) - 1); cycle_leader_forward(_begin, left_size_); difference_type const rest_ = _size - left_size_; if (rest_ != 0) { Iterator middle_ = _begin + left_size_; forward(middle_, rest_); std::rotate(_begin + left_size_ / 2, middle_, middle_ + rest_ / 2); } } void backward(Iterator _begin, difference_type const _size) const { assert(0 < _size); assert(_size % 2 == 0); difference_type const left_size_ = *(std::upper_bound(powers3_.cbegin(), powers3_.cend(), _size) - 1); std::rotate(_begin + left_size_ / 2, _begin + _size / 2, _begin + (_size + left_size_) / 2); cycle_leader_backward(_begin, left_size_); difference_type const rest_ = _size - left_size_; if (rest_ != 0) { Iterator middle_ = _begin + left_size_; backward(middle_, rest_); } } private : void cycle_leader_forward(Iterator _begin, difference_type const _size) const { for (difference_type leader_ = 1; leader_ != _size - 1; leader_ *= 3) { permutation_forward permutation_(leader_, _size); Iterator current_ = _begin + leader_; value_type first_ = std::move(*current_); while (++permutation_) { assert(permutation_ < _size); Iterator next_ = _begin + permutation_; *current_ = std::move(*next_); current_ = next_; } *current_ = std::move(first_); } } void cycle_leader_backward(Iterator _begin, difference_type const _size) const { for (difference_type leader_ = 1; leader_ != _size - 1; leader_ *= 3) { permutation_backward permutation_(leader_, _size); Iterator current_ = _begin + leader_; value_type first_ = std::move(*current_); while (++permutation_) { assert(permutation_ < _size); Iterator next_ = _begin + permutation_; *current_ = std::move(*next_); current_ = next_; } *current_ = std::move(first_); } } struct permutation_forward { permutation_forward(difference_type const _leader, difference_type const _size) : leader_(_leader) , current_(_leader) , half_size_(_size / 2) { ; } bool operator ++ () { if (current_ < half_size_) { current_ += current_; } else { current_ = 1 + (current_ - half_size_) * 2; } return (current_ != leader_); } operator difference_type () const { return current_; } private : difference_type const leader_; difference_type current_; difference_type const half_size_; }; struct permutation_backward { permutation_backward(difference_type const _leader, difference_type const _size) : leader_(_leader) , current_(_leader) , half_size_(_size / 2) { ; } bool operator ++ () { if ((current_ % 2) == 0) { current_ /= 2; } else { current_ = (current_ - 1) / 2 + half_size_; } return (current_ != leader_); } operator difference_type () const { return current_; } private : difference_type const leader_; difference_type current_; difference_type const half_size_; }; std::deque< difference_type > powers3_; }; 

Modifiqué el código aquí para obtener este algoritmo:

 void PartitionIndexParity(T arr[], size_t n) { using std::swap; for (size_t shift = 0, k; shift != n; shift += k) { k = (size_t)pow(3, ceil(log(n - shift) / log(3)) - 1) + 1; for (size_t i = 1; i < k; i *= 3) // cycle-leader algorithm { size_t j = i; do { swap(arr[(j = j / 2 + (j % 2) * (k / 2)) + shift], arr[i + shift]); } while (j != i); } for (size_t b = shift / 2, m = shift, e = shift + (k - k / 2), i = m; shift != 0 && k != 0; ) // or just use std::rotate(arr, b, m, e) { swap(arr[b++], arr[i++]); if (b == m && i == e) { break; } if (b == m) { m = i; } else if (i == e) { i = m; } } } } 

Aquí hay una implementación de Java del algoritmo de Peiyush Jain:

 import java.util.Arrays; public class InShuffle { public static void main(String[] args) { Integer[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }; inShuffle(nums); System.out.println(Arrays.toString(nums)); } public static  void inShuffle(T[] array) { if (array == null) { return; } inShuffle(array, 0, array.length - 1); } private static  void inShuffle(T[] array, int startIndex, int endIndex) { while (endIndex - startIndex + 1 > 1) { int size = endIndex - startIndex + 1; int n = size / 2; int k = (int)Math.floor(Math.log(size + 1) / Math.log(3)); int m = (int)(Math.pow(3, k) - 1) / 2; rotateRight(array, startIndex + m, startIndex + n + m - 1, m); for (int i = 0, cycleStartIndex = 0; i < k; ++i, cycleStartIndex = cycleStartIndex * 3 + 2) { permuteCycle(array, startIndex, cycleStartIndex, 2 * m + 1); } endIndex = startIndex + 2 * n - 1; startIndex = startIndex + 2 * m; } } private static  void rotateRight(T[] array, int startIndex, int endIndex, int amount) { reverse(array, startIndex, endIndex - amount); reverse(array, endIndex - amount + 1, endIndex); reverse(array, startIndex, endIndex); } private static  void reverse(T[] array, int startIndex, int endIndex) { for (int leftIndex = startIndex, rightIndex = endIndex; leftIndex < rightIndex; ++leftIndex, --rightIndex) { swap(array, leftIndex, rightIndex); } } private static  void swap(T[] array, int index1, int index2) { T temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } private static  void permuteCycle(T[] array, int offset, int startIndex, int mod) { for (int i = ((2 * startIndex + 2) % mod) - 1; i != startIndex; i = ((2 * i + 2) % mod) - 1) { swap(array, offset + i, offset + startIndex); } } } 

Y hacer una salida aleatoria es tan simple como:

 public static  void outShuffle(T[] array) { if (array == null) { return; } inShuffle(array, 1, array.length - 1); } 

 public class OddToLeftEvenToRight { private static void doIt(String input){ char[] inp = input.toCharArray(); int len = inp.length; for(int j=1; j< len; j++) { for(int i=j; i