CareerCup

Let me show what my algorithm does with a simple example first. Let the initial array be [1,2,3,4,a,b,c,d]. Let's just say it's 1234abcd. In this example, n=4 according to the problem definition. I swap 3 pairs of elements in the middle around the center of the array as a block. And then, I swap 2 pairs of elements as a block, and finally I swap 1 pair of elements. It's hard to explain so I'll just show how it progresses:
initially: 1234abcd
swapping center 3 pairs, it becomes 1abc234d
swapping center 2 pairs, it becomes 1a23bc4d
swapping center 1 pair, it becomes 1a2b3c4d
It works in place but time complexity is O(n^2).
Here is the code. It's a little hard to understand but basically, it does what I explained above. I assumed an int array for sake of simplicity.

void swap(vector<int> & v, int i, int j) {
	int t = v[i];
	v[i]  = v[j];
	v[j]  = t;
}
void process(vector<int> & v) {
	int n = v.size()/2;	
	for ( int i = n-1; i > 0; i-- )
		for ( int j = n-1; i+j>=n; j-- )
			swap(v,j,i+j);
}

The key here is twofold (I missed the second the first time through). First, given any particular index in the array, we can tell the spot that that element belongs with a simple equation. This means that we can swap elements until we get back to the start, putting them in the right place.

That's not enough however. If we start at position 1 we will get back to position 1 without correcting all of the units. It turns out that we need to do this replacement starting with 1, 3, 5 up until we get to a fourth of the length of the array.

#!/usr/local/bin/python

#generate the array for our test
def generate(n):
    return [i+1 for i in range(n)] + [chr(ord('a') + i) for i in range(n)]
#Play with this to create different sized arrays
arr = generate(2)
print arr 

#actual code
def nextIndex(index, ln):
    nxt = index*2
    if nxt >= ln: 
        nxt = (index - ln/2)*2 + 1 
    return nxt 
for s in range(len(arr)/4):
    start = s*2+1
    n = nextIndex(start, len(arr))
    last = arr[start]
    index, start = n, n
    while True:
        arr[index],last = last,arr[index]
        index = nextIndex(index, len(arr))
        if index == start:
            break;

print arr

say the array is

a1 a2 a3 a4 b1 b2 b3 b4

Now We partition the array into two equal sized arrrays and swap from n/4 to n/2 with n/2+1 to n/2+n/4 ..so it becomes after first
a1 a2 a3 a4 | b1 b2 b3 b4

a1 a2 b1 b2 a3 a4 b3 b4

Now We do the same thing unless length becomes <=2 i.e. n<=2
So we do (here n=4)
a1 a2 |b1 b2
swapping gives
a1 b1 a2 b2 a3 a4 b3 b4
Now length of a1 b1 is 2 so we return
and for a2 b2 is also 2 ..Again we do the same for a3 a4 b3 b4

Time complexity(nlogn)

Code->

void InplaceChange(string a[],int n){
if(n<=2) return;
int x=n/2,i;
if(x%2==0){
for( i=x/2;i<x;i++)
swap(a[i],a[i+x/2]);
InplaceChange(a,x);
InplaceChange(a+x,x);
}else{
for(i=x/2;i<x;i++)
swap(a[i],a[i+x/2+1]);
swap(a[x-1],a[x+1]);
InplaceChange(a,x-1);
InplaceChange(a+x+1,x);
}

}

ideone.com/57nnb

Keep two pointers, one that keeps track of the current character, and one that keeps track of the current index you're replacing. In python code:

def replace(a):
  pos = 1
  ltrpos = len(a) / 2
  stack = []
  while pos < (len(a) - 1):
    if (pos % 2) == 1:
      stack.append(a[pos])
      a[pos] = a[ltrpos]
      ltrpos = ltrpos + 1
    else:
      stack.append(a[pos])
      a[pos] = stack.pop(0)
    pos = pos + 1
  return a

C#

static public void Reorder(char[] A)
        {
            //error checking

            int n = A.Length / 2;

            if (n > 1)
            {
                PartialReorder(A, 1, n);
                PartialReorder(A, 3, n);
            }
        }

        static private void PartialReorder(char[] A, int start, int n)
        {
            char tmp = A[start];

            int dest = start;
            int src = (dest % 2 == 0) ? dest / 2 : n + dest / 2;

            while (src != start)
            {
                A[dest] = A[src];
                dest = src;
                src = (dest % 2 == 0) ? dest / 2 : n + dest / 2;
            }
            A[dest] = tmp;
        }

Can someone please provide explanation to Peiyush Jain's "A Simple In-Place Algorithm for In-Shuffle." paper which provides the answer to the problem but I fail to understand it. :(

I used reverse operation repeatedly, and got the expected output. For example

1234abcd, take 234abc, do the following steps,

cba432 //reverse
abc432 // reverse upto middle end
abc234

Do the same operation for the next set bc23,

32cb,
23cb
23bc

next set of string 3b

b3,

final output is 1a2b3c4d, not sure about complexity, but everything in place

void reverse(char str[],int start, int end)
{
        int temp;
        while(start<end)
        {
                temp=str[start];
                str[start++] = str[end];
                str[end--] = temp;
        }
}

void func(char str[])
{
        int end = strlen(str)-2;
        int start = 1;
        while(start<end)
        {
                reverse(str,start,end);
                reverse(str,start,start+((end-start)/2));
                reverse(str,1+start+((end-start)/2),end);
                start++;
                end--;
                printf("%s\n",str);
        }
}

Luke Magil almost had it. However, the outer loop does not go to every odd index (even position) I found this by testing an array of 34 elements. The outer loop starts at positions: 1, 2, 4, 6, 12, done

I am sure there is a way to calculate each starting point for the outer loop mathematically, but that calculation is presently beyond me. Instead, I just have a sub iteration in the outer loop that looks for the next numeric element with an odd index (in an even position) This adds an additional single traversal through the array, but, in terms of complexity, O(2n) = O(n):

void shuffleArray(Vector<char> array) {
    int halfSize = array.size() / 2;
    int i = 1;
    
    //*** Outer Loop
    while (i < halfSize) {

        //*** i is always odd, since we increment it by 2 each time
        //*** if array[i] is an integer, then we have not yet processed it
        //*** I am assuming some function to tell if array[i] is an integer
        if (isInteger(array[i])) {
            int indexToProcess = i;
            
            //*** calculate the destination of the element we are processing
            if (indexToProcess > halfSize) 
                indexToProcess = ((indexToProcess - halfsize) * 2 ) - 1;
            else
                indexToProcess = indexToProcess * 2;
            
            //*** Inner Loop
            while (indexToProcess != i) {
                holder = array[indexToProcess];
                array[indexToProcess] = array[i];
                //*** use array[i] to store the original value of the index we are processing
                array[i] = holder;    

                //*** calculate the new destination of the element we are processing
                if (indexToProcess > halfSize) 
                    indexToProcess = ((indexToProcess - halfsize) * 2 ) - 1;
                else
                    indexToProcess = indexToProcess * 2;
            }
        }

        //*** In the outer loop, go to the next odd index
        i += 2;
    }
}

In place (no extra memory) and O(n).

Yes, there are two loops, but each loop is always less than n (the number of elements), such that if you multiply the iterations in the outer loop by the iterations of the inner loop, you get n (the number of elements)

If somebody can figure out the calculation for incrementing i, you can change "i +=2" to whatever that calculation is.

Assume that we are given 2n element ( n integers , n characters ) .

consider n=3 , then elements to be swapped will be as

1 --> 1 4 --> 2
2 --> 3 5 --> 4
3 --> 5 6 --> 6

Where x --> Y notation means , the value at index X should be placed at index Y .

If we follow the above notation , we can form the chain of movement as
1--> 1
2-->3-->5-->4-->2
6-->6

The second chain here indicates, save the value @ index 2 ,then copy the contents from index 4 to index 2, then from index 5 to index 4 , then from index 3 to index 5 and then copy the saved value to index 3

Essentially , if we can generate these chains , in linear time , we can do the swapping in linear time

Following is the code for the same . The code moves the elements as per the chains constructed above.


#include<iostream>
using namespace std;

#include<string.h>

void do_shuffle(char * str,int n);
int getnext(int next,int n);

int main(int argc,char * argv[])
{
int n;
char * str =argv[1];

if(argc < 2)
{
cout<<"usage "<<argv[0]<<" <string>"<<endl;
return 0;
}
n= strlen(str);

cout<<n;

//check if array lenth is odd
if( n %2 != 0 )
{
cout<<"odd String length"<<endl;
return 0;
}

do_shuffle(str ,n/2);
}

void do_shuffle(char * str,int n)
{
int head =2;
int next = 2;
int done = 0;
char saved ;
int t=0;

//Keep track of which elements have been swapped
int *visited = new int[2*n];

for(int i=0;i<2*n;i++) visited[i]=0;


//cout<<"Printing...."<<endl;
cout<<"Input string : "<<str<<endl;

int not_visited = 1;
visited[0]=visited[2*n-1]=1;

while ( not_visited )
{

done = 0;
head = next;

saved = str[next-1];

while ( done != 1 )
{
//cout<<next<<"-->";

visited[next-1]=1;
t = getnext(next,n);

if( t != head )
{
str[next-1]=str[t-1];
}
else
{
str[next-1]= saved;
}

next=t;
if(next == head )
done = 1;
}
//cout<<head<<endl;

//update not_visited
not_visited = 0;
for(int i=0;i<2*n;i++)
{
if(visited[i] == 0 )
{
not_visited = 1;
next = i+1;
}
}
}


cout<<"output string : "<<str<<endl;
}

int getnext(int now,int n )
{

if( now %2 == 0 )
{
int k = ( 2*n - now)/2;
int out = 2*n - k ;
//cout << "in "<<now<<"out "<<out<<endl;
return out;
}
else
{
int out = ( now + 1 )/2;
//cout << "in "<<now<<"out "<<out<<endl;
return out;
}

}

here is my O(n) solution but probably with more swapping no error cases handled here.
ex- 7 9 8 5 1 e f i k z
Main logic:
Since the array has first integers followed by char values so we know that the spike value(change) index would be in the middle of the array.
so change index = 5

step- 1 using the above fact ,divide the array into two logical parts one with all the integers(say array1) and another with all chars (say array2).
array 1 - 7 9 8 5 1
array 2 - e f i k z

step-2 we take two var which would scan the two arrays individually as pt1 and pt2 , swap pt1+1 with pt2 and increment pt1 and pt2 with 2 until pt2 reaches the end of the array2. the resulting array would be:
array 1 - 7 e 8 i 1
array 2 - 9 f 5 k z

step-3 This step is necessay only if the array contains odd no of pairs.
store the end value of array1 in tmp and, Now since the array contains oddNo of pairs so we will move one element to the left starting from the end of array1.

so the resulting array would be
array 1 - 7 e 8 i 9 with tmp =1
array 2 - f 5 k z z
put the value in tmp at the second last indx of array2, so the resulting array would be:
array 1 - 7 e 8 i 9
array 2 - f 5 k 1 z

and the whole array would be like:
array - 7 e 8 i 9 f 5 k 1 z
step -4 Now as you can see the resulting array has <int, char> pairs but the pairs are not in the right order. In this step we swap alternate pairs to get the resulting array.

In the below code forward_ptr1 is the variable operating on logical array1 similarly forward_ptr2 is the variable operating on logical array2
isOdd checks whether the array contains odd no of pairs or not.

#include<stdio.h>

  
void swap(char a[], int i, int j)
{
   char tmp;
   tmp = a[i];
   a[i] = a[j];
   a[j]  =tmp;
}

void
print(char a[], int n)
{

   for(int i=0; i<n;i++)
   printf(" %c", a[i]);
   
   printf("\n");
}

int
 main()
 {
   //char a[]={'7','9','8','5','1','e','f','i','k','z'};
   char a[]={'7','9','8','5','e','f','i','k'};
   int n = sizeof(a)/sizeof(char);
   
   int spike = (n-1)/2;
   int forward_ptr1=0, forward_ptr2=spike+1;
   bool isOdd;
   //step 1
   isOdd = n/2%2 ? true : false;

//step 2
   for(;;)
   {
      swap(a, forward_ptr1+1, forward_ptr2);
      forward_ptr1 += 2;
      forward_ptr2 +=2;
      print(a, n);
      if(forward_ptr2 >= n-1)
      break;
   }
   //step-3
   int tmp;
   if(isOdd)
   {
      tmp = a[forward_ptr1];
      for(int i=forward_ptr1; i<n-1; i++)
      {
         a[i]=a[i+1];   
      }
      a[n-2]=tmp;   
   }
   
//step 4
   forward_ptr1 = 0;
   forward_ptr2 = spike;
   if(!isOdd)
   forward_ptr2++;
   
   for(;;)
   {
      swap(a, forward_ptr1+2, forward_ptr2);
      swap(a, forward_ptr1+2+1, forward_ptr2+1);
      forward_ptr1 +=4;
      forward_ptr2 +=4;
      
      if(forward_ptr1 >= spike)
      break;
   }  

  
   printf("---------------------------- \n");
   print(a, n);
   return 0;
 }

Pseudo Code:
Arr[Start...Finish] ie Arr[1...10] = 12345abcde
end = 10; mid = 5
swap(end-1, mid);
Swap (end-2,mid-1);
swap(end-3,mid-2)
mid=mid-2;
end=end-4;
Do this swapping while mid>Arr's Start

taking help from luke's post

public class ShuffleArray {

	public static int nextIndex(int index, int len) {
		int nxt = index*2;
		if (nxt >= len) {
			nxt = (index - len/2)*2 + 1;
		}
		return nxt;
	}
	
	public static void main(String args[]) {
		char[] arr = { 'a', 'b', 'c', 'd', 'e', 'A', 'B', 'C', 'D', 'E'};
		int len = arr.length;
		boolean[] b= new boolean[len];
		
		for (int i = 0; i < len; i++)
			b[i] = false;
		
		
		/* Idea is to start from index 1, find what should be its position
		 * using method nextIndex. then replace the element and find the desired
		 * position for that element. Keep on doing that, until you have
		 * touched all positions.
		 */
		int count = 0;
		for (int i = 1; i < len/2; i++) {
		
			// Finding reqd position for i.
			int n = nextIndex(i, len);
			int j = i;
			char temp1 = arr[i];
			
			// you may reach back to original position or the one that has been touched already.
			while ( (n != j) && b[n] != true	) {
				System.out.print("j=" + j + ", n=" + n);
				char temp2 = arr[n];
				arr[n] = temp1;
				temp1 = temp2;
				j = n;
				
				// indicate the position is touched.
				b[n] = true;
				n = nextIndex(j, len);
				for (int k = 0; k < len; k++) System.out.print(arr[k] + ", ");
				System.out.println();
				count++; 
			}
		}
		System.out.println(count);
	}
}

inline int newpos(int i, int n) {                                                    
        if(i<n) return 2*i;                                                          
        else return (i-n) * 2 + 1;                                                   
}

void shuffle2(int n, char *arr) {                                                    
        if(n==0) return;
        int i=1, ni=newpos(1, n);
        char tmp = arr[1];                                                           
        do {
                char tmp2 = arr[ni];
                arr[ni] = tmp;                                                       
                tmp = tmp2;
                i = ni;
                ni = newpos(i, n);                                                   
        } while (ni != 1);
        arr[1] = tmp;
}

O(n) solution:

//[1,7,9,4,a,x,r,d] => [1,a,7,x,9,r,4,d]
const int size = 2; //in our case
public int getIndex(int curr_index, int N)
{
return (curr_index%size)*N + (curr_index/size);
}

public void convertArray(char[] A)
{
int N = A.Length/size;
int swap_index = 0;
char swap = '\0';
for(int i =0;i<A.Length;i++)
{
swap_index = getIndex(i, N);
while(swap_index<i)
swap_index= getIndex(swap_index, N);
swap = A[i];
A[i] = A[swap_index];
A[swap_index] = swap;
}
}

O(n) solution:

//[1,7,9,4,a,x,r,d] => [1,a,7,x,9,r,4,d]
const int size = 2; //in our case
public int getIndex(int curr_index, int N)
{
return (curr_index%size)*N + (curr_index/size);
}

public void convertArray(char[] A)
{
int N = A.Length/size;
int swap_index = 0;
char swap = '\0';
for(int i =0;i<A.Length;i++)
{
swap_index = getIndex(i, N);
while(swap_index<i)
swap_index= getIndex(swap_index, N);
swap = A[i];
A[i] = A[swap_index];
A[swap_index] = swap;
}
}

const int size = 2; //in our case
public int getIndex(int curr_index, int N)
		{
			return (curr_index%size)*N + (curr_index/size);
		}
		
		public void convertArray(char[] A)
		{
			int N = A.Length/size;
			int swap_index = 0;
			char swap = '\0';
			for(int i =0;i<A.Length;i++)
			{
				swap_index = getIndex(i, N);
				while(swap_index<i)
					swap_index= getIndex(swap_index, N);
				swap = A[i];
				A[i] = A[swap_index];
				A[swap_index] = swap;
			}	
		}

#include<iostream.h>
int main()
{
char c[]={'2','2','4','5','6','q','e','t','p'};
int n=sizeof c/sizeof(char);

char a[9]={0};
int low=0;
int high=8;
int mid;
for(int i=0;i<9;i++)
{
if(c[i]=='q')
{ mid=i; }

}
cout<<mid;
int c1=0;
for(int i=0;i<mid;i++)
{ a[c1]=c[i];
c1+=2;}
c1=1;
for(int i=mid;i<9;i++)
{ a[c1]=c[i];
c1+=2; }
for(int i=0;i<9;i++)
{cout<<" [ "<<a[i]<<" ] ";}


cin>>c1;
return 1;
}

When you say the sequence should be i1,c1..... so by this you mean first integer in the element followed by first character in the array or integer followed by character but integer and character subarrays sorted. One more thing are the number of characters and integers equal.