Dado un conjunto con enteros positivos y negativos, mueva todos los elementos indexados impares a la izquierda e incluso los elementos indexados a la derecha.
La parte difícil del problema es hacerlo en el lugar mientras se mantiene el orden.
p.ej
7, 5, 6, 3, 8, 4, 2, 1
El resultado debería ser:
5, 3, 4, 1, 7, 6, 8, 2
Si el pedido no importó, podríamos haber utilizado el algoritmo de partición () de ordenación rápida.
¿Cómo hacerlo en O (N)?
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:
Aquí hay diferentes algoritmos O (N log N) in situ, que no necesitan pruebas de teoría de números:
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
Este progtwig lo hace en O (n ^ 2).