Given an array with positive and negative integers, move all the odd indexed elements to the left and even indexed elements to the right.
The difficult part of the problem is to do it in-place while maintaining the order.
e.g.
7, 5, 6, 3, 8, 4, 2, 1
The output should be:
5, 3, 4, 1, 7, 6, 8, 2
If the order didn't matter, we could have been used partition() algorithm of quick sort.
How to do it in O( N )?
Algorithm is in-place, time complexity is O(N).
Example:
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)
Variation of this algorithm, that does not need step 5:
Here is different O(N log N) in-place algorithm, which does not need number-theoretic proofs:
Example:
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)
This problem is just a special case of the In-place matrix transposition.
0 1 2 3 4 5 6 7 transforms to 0 2 4 3 1 5 6 7 after the first cycle leader iteration? –
Wilkie 0->4,4->6,6->7,7->3,3->1,1->0 and '2->5, 5->2'. As per the paper you suggested, any new permutation is a disjoint set of such cyclic leader rotations. Where does your steps 2-4 fit in? And secondly, is there any guarantee that these rotations won't go for a fairly long time (here it is only 6 and 2 for the 2 sets) so that it no longer remains linear? –
Wilkie 3^k-1, only step 1 suffices. For example, in the length 10 array '4,7,2,9,8,5,1,3,6,5, to convert it into the array 7 9 5 3 5 4 2 8 1 6, only 1 cycle is required: 0->5,5->2,2->6,6->8,8->9,9->4,4->7,7->3,3->1 & 1->0, as summarized by i -> L/2 + i/2` when i%2 == 0, else i -> i/2. Steps 3-4 are not required here. And for the given array in question, two sets of disjoint cycles are required. So when does only 1 cycle suffice, and when more than 1 is needed? And if more than 1 is needed, how to know that? –
Wilkie 3^k-1 there is no way to know how many cycles we have and where are these cycles, no mathematical proof exists for this case (or at least I don't know one). If you know array length in-advance, you can pre-calculate number of cycles and all starting points, and use them in a fixed-length algorithm. –
Manila 3^2-1)? –
Wilkie 3^k-1 lengths, there are always k cycles; see proof in the paper. –
Manila 0->4->6->7->3->1->0 and the other as 2->5->2. –
Wilkie O(N) time with O(1) space? –
Wilkie 3^k-1, right? And secondly, can you elaborate a bit more in reversing the left-out subarray, combining it with the 2nd half of the main array, etc? –
Wilkie k is not O(1) but is O(log(N)), isn't it? –
Kurzawa k or computing base-3 logarithm may be also done in O(1) time. Otherwise you could do it in O(log log N) time and space using binary exponentiation. Or O(log log N) time and O(1) space using bitwise tricks. –
Manila reverse (4.) if we have, say, at least 3 parts? E.g. array of length 16 = 10 + 4 + 2. –
Kurzawa reverse subarrays of five (10/2) and three (4/2 + 2/2) sizes and then both together? –
Kurzawa I tried to implement as Evgeny Kluev said, and here is the result:
#pragma once
#include <iterator>
#include <algorithm>
#include <type_traits>
#include <limits>
#include <deque>
#include <utility>
#include <cassert>
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_;
};
I modified the code here to get this algorithm:
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; }
}
}
}
Here's a Java implementation of Peiyush Jain's algorithm:
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 <T> void inShuffle(T[] array) {
if (array == null) {
return;
}
inShuffle(array, 0, array.length - 1);
}
private static <T> 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 <T> 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 <T> void reverse(T[] array, int startIndex, int endIndex) {
for (int leftIndex = startIndex, rightIndex = endIndex; leftIndex < rightIndex; ++leftIndex, --rightIndex) {
swap(array, leftIndex, rightIndex);
}
}
private static <T> void swap(T[] array, int index1, int index2) {
T temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
private static <T> 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);
}
}
}
And doing an out-shuffle is as simple as:
public static <T> 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<len-j; i+=2)
{
swap(inp, i, i+1);
}
}
System.out.print(inp);
}
private static void swap(char[] inp, int i, int j) {
char tmp = inp[i];
inp[i]= inp[j];
inp[j]=tmp;
}
public static void main(String[] args)
{
doIt("a1b");
}
}
This program does it in O(n^2).
There is a simple in-place algorithm that does exactly N swaps described here: https://mcmap.net/q/581137/-de-interleave-an-array-in-place
Define a source index function to find the value that belongs at a given location in the desired result.
def index(loc, N):
mid = N-N//2
return (loc*2)+1 if loc < mid else (loc-mid)*2
then walk from beginning to the end, swapping every item with the one at the calculated index, but if that index is earlier than the current location, recalculate to see where it was swapped to.
def unshuffle(A):
N = len(A)
for i in range(N):
source = index(i, N)
while source < i:
source = index(source,N)
A[i],A[source] = A[source],A[i]
return A
The number of calls to index is logarithmic, but for large arrays on real hardware, the time cost is minimal compared to the cost of the swaps.
This gives
>>> unshuffle([7, 5, 6, 3, 8, 4, 2, 1])
[5, 3, 4, 1, 7, 6, 8, 2]
© 2022 - 2024 — McMap. All rights reserved.