wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> rearrange the array.
        
(Message started by: saujin on Sep 3^rd, 2004, 12:53pm)

Title: rearrange the array.
Post by saujin on Sep 3^rd, 2004, 12:53pm

An array {A1,A2,A3,....,An,B1,B2,......,Bn} is given and we have to rearrange it as {A1,B1,A2,B2......} .give an algo with minimum time and space complexity.

Title: Re: rearrange the array.
Post by towr on Sep 4^th, 2004, 8:12am

This is very similar to "Shuffle a deck of cards" (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1084733627) (except we'd need to switch every two consecutive elements in the end)

Title: Re: rearrange the array.
Post by Grimbal on Sep 4^th, 2004, 10:57am

Simpler, it is like shuffling A2..An with B1..Bn-1, using the other method, leaving A1 and Bn in place.

Title: Re: rearrange the array.
Post by Aryabhatta on Sep 6^th, 2004, 2:03pm

saujin, I am curious to know your solution. Could you please post it here?

Title: Re: rearrange the array.
Post by NoName on Sep 7^th, 2004, 12:28pm

on 09/03/04 at 12:53:38, saujin wrote:

An array {A1,A2,A3,....,An,B1,B2,......,Bn} is given and we have to rearrange it as {A1,B1,A2,B2......} .give an algo with minimum time and space complexity.

Here's a simple code that does the job (perl). Not sure this is the same you guys converged on in the shuffle problem, but I'll post it anyway.

Code:

#!/usr/bin/perl -w
use strict;

my $N= $ARGV[0];

my @A= ("");

my $i;

for ($i = 1; $i <= $N; ++$i) {
$A[$i] = "A$i";
$A[$i+$N] = "B$i";
}

print "Initial array:\n @A\n";

for (my $x = 2, my $swaps = 3, $i = 2;
$swaps < 2*$N;
++$swaps) {

my $k = ($i > $N) ? 2*($i - $N) : 2*$i - 1;

swapA($x, $k);

$i = $k;
if ($i == $x) {
$x += 2;
$i = $x;
}
}

print "Output array:\n @A\n";

exit(0);

sub swapA {
(my $i, my $j) = @_;
my $tm = $A[$i];
$A[$i] = $A[$j];
$A[$j] = $tm;
}

Title: Re: rearrange the array.
Post by NoName on Sep 7^th, 2004, 1:02pm

on 09/07/04 at 12:28:08, NoName wrote:

...

Sorry, my bad. This does not work for N>11.

Title: Re: rearrange the array.
Post by saujin on Sep 13^th, 2004, 12:00pm

Hi aryabhatta,

sorry for late replying. But i too donn know exact answer to this Qn. This question was asked to one of my frend at interview. I'll post other Qns from that interview here as well, and will appreciate if i can get some good answers to those Qns.

saurabh

Title: Re: rearrange the array.
Post by NoName on Sep 14^th, 2004, 1:28pm

on 09/07/04 at 13:02:07, NoName wrote:

Sorry, my bad. This does not work for N>11.

OK, here's another try. It's not linear, but I thought it maybe interesting to those who thought about this problem.

Code:

int *A, N;
void re(int from, int many) {
int i, k = (many+1)/2;
int x = (k & 1);

if (many < 2)
return;

re(from, k);
if (x)
re(from+k-1, k);
else
re(from+k, k-1);

for (i = from+1; i < from+k; i += 2)
swapA(i, i + k - 1 + x);
}

int main() {
...
re(0, N);
....
}

BTW, I saw some discussion about the existence of the linear solution to this problem in the "deck of cards" topic, but I have not seen it posted.

My impression is that the idea of shuffling a larger array with only one cycle is good, but wouldn't those "extra" elements that you introduce have to serve as additional storage, so that you can always find an element at the "right place"? I suspect that they cannot just be ignored... So, I see that it will be linear, but I'm not sure it will be O(1) in space. And surely, if it turns out to use O(N) in space, there's a much simpler algorithm for that.

Please prove me wrong, post the code that we all could try and convince ourselves.

Title: Re: rearrange the array.
Post by Aryabhatta on Sep 14^th, 2004, 3:07pm

on 09/14/04 at 13:28:59, NoName wrote:

BTW, I saw some discussion about the existence of the linear solution to this problem in the "deck of cards" topic, but I have not seen it posted.

An algorithm was posted in that thread but was hidden (you will need to highlight to view it). I will repeat it here for convenience.

Given Array A[1...2n].

Algo:

Step 1) Find an m such that 2m+1 = 3^k <= 2n < 3^k+1
Step 2) Right cyclic shift A[m+1 ... n+m] by m.
Step 3) Foreach i = 0 to k - 1, considering only the Array[1...2m] start at 3ⁱ and 'follow the cycle'.
Step 4) Recurse on A[2m+1...2n]

Basic idea is as follows:
If for each n, we can find an m (Step 1) for which we can easily do the 'following the cycle' algorithm, we can first shuffle some elements (Step 2), then do the algo for m (Step 3) and then recurse on the remaining elements (Step 4).

'following the cycle': element i1 goes to i2 which goes to i3 ... goes to finally back to i1. We can put the elements of this cycle in their right places by using just one extra location as follows:
Store element i1 in the extra location. Look at what goes into i1. say X1. Store element in X1 in i1. Follow the cycle. Finally store i1 in is right position.

Title: Re: rearrange the array.
Post by NoName on Sep 14^th, 2004, 7:30pm

on 09/14/04 at 15:07:50, Aryabhatta wrote:

Step 1) Find an m such that 2m+1 = 3^k <= 2n < 3^k+1
Step 2) Right cyclic shift A[m+1 ... n+m] by m.
Step 3) Foreach i = 0 to k - 1, considering only the Array[1...2m] start at 3ⁱ and 'follow the cycle'.
Step 4) Recurse on A[2m+1...2n]
...

Thanks. I did misunderstand your algorithm.

Two questions, please:
1. How do you keep track of misplaced elements A[2m+1 ...n+m] (misplaced after previous cyclic shift(s))?

2. You wouldn't be willing, perhaps, to post actual working code perl or C or whatever for the implementation?

Title: Re: rearrange the array.
Post by Aryabhatta on Sep 14^th, 2004, 9:53pm

Here is C code which seems to work on the few values that I have tried.

Sorry about the long post.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

void Inshuffle(int *A, int N);
void follow_cycle(int *A, int N, int seed);
void cyclic_shift(int *A, int size, int distance);
void reverse(int *A, int size);
int Inverseof2(int M);

/***************************
Main Insuffle Algorithm.
Shuffle a1 a2 ..an b1 b2 ...bn
to
b1 a1 b2 a2 .... bn an

Parameters: A = the array
N = 2n, size of the array.

The permutation is given by
i -> 2i mod (N + 1)

We shuffle the array starting
from A[1] for easier coding.
****************************/

void Inshuffle(int *initialA, int initialN)
{

int m =1;
int i;
int power3 = 1;
int seed = 1;
int k = 1;
int n = initialN/2; //N is assumed to be even.
int *A = initialA;
int N = initialN;

while (N > 0){

//Reset Values.
m = 1;
i = 0;
power3 = 1;
seed = 1;
k = 1;
n = N/2;

//Step 1: Find an m such that 2m+1 is the largest power of 3 <= N+1
for (i = 0; i <= N+1; i ++){
if (3*power3 > N+1){
break;
}
power3 = 3*power3;
}
k = i;

m = (power3 - 1)/2;
//Step 2: Cyclic Right Shift A[m+1, n+m] by m
cyclic_shift(A+m+1,n,m);

// Step3: Do inshuffle of A[1....2m] by 'following cycle'.

for (i = 0 ; i < k; i ++)
{
follow_cycle(A,2*m,seed);
seed = 3*seed;
}
// Step 4: Recurse on A[2m+1...,2n]

//Could have made a recursive call here:
//Inshuffle(A+2*m,2*(n-m));
// But to make it O(1) space, convert tail recursion to iteration and put in a while loop.

A = A + 2*m;
N = 2*(n-m);
// Reset Values.
} //End of while loop.
}

/****************************************
Follow the cycle starting at seed.
For example: insuffle of 1 2 3 4 5 6 7 8
1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1
We follow this cycle in reverse order.
We look at 1. Save A[1].
Then look at what goes to 1, i.e 5 = 1*x
where x is inverse of 2.
Now fill A[1] with A[5].
Now look at what goes into A[5]. 7 = 5*x
(x is inverse of 2)
So fill A[5] with A[7].
And so on.
*****************************************/

void follow_cycle(int *A, int N, int seed)
{
int cur;
int inverse2 = Inverseof2(N+1);
int tmp;
int prev;

cur = (seed*inverse2 % (N+1));

tmp = A[seed];
prev = seed;
while (cur != seed){
A[prev] = A[cur];
prev = cur;
cur = (cur*inverse2 % (N+1));
}
A[prev] = tmp;
}
/*******************************
cyclic right shift an array by a given amount.
********************************/
void cyclic_shift(int *A, int sz, int k)
{
reverse(A,sz - k);
reverse(A+sz-k,k);
reverse(A,sz);
}

/******************************
reverse an array
*******************************/
void reverse(int *A, int sz)
{
int i;
int tmp;
for (i = 0; i < sz/2; i++)
{
tmp = A[i];
A[i] = A[sz-i-1];
A[sz-i-1] = tmp;
}
}

/***************************

find x such that 2x = 1 (mod M)
M is assumed to be an odd integer.
x = (M+1)/2
***************************/
int Inverseof2(int M)
{
return (M+1)/2;
}

int main()
{
int n;
int i;
int *A;
printf("Enter the value of n, (total size of array = 2n): ");
scanf("%d",&n);
A = (int *)malloc((2*n+1)*sizeof(int));
for (i = 0; i <= 2*n; i++){
A[i] = i;
}

Inshuffle(A,2*n);

printf("\n[");
for (i = 1; i <= 2*n; i ++){
printf(" %d",A[i]);
}
printf(" ]\n");
free(A);
return 1;
}

Title: Re: rearrange the array.
Post by NoName on Sep 15^th, 2004, 10:20am

on 09/14/04 at 21:53:47, Aryabhatta wrote:

Here is C code which seems to work on the few values that I have tried.
...

Thanks! Any idea why it wouldn't work for values of n >= 88573 = (3^11-1)/2 ?

Title: Re: rearrange the array.
Post by Aryabhatta on Sep 15^th, 2004, 1:17pm

on 09/15/04 at 10:20:09, NoName wrote:

Thanks! Any idea why it wouldn't work for values of n >= 88573 = (3^11-1)/2 ?

It is most likely an integer overflow in the follow_cycle method due to the cur*inverse2.

Title: Re: rearrange the array.
Post by Aryabhatta on Sep 15^th, 2004, 4:48pm

on 09/15/04 at 13:17:20, Aryabhatta wrote:

It is most likely an integer overflow in the follow_cycle method due to the cur*inverse2.

Maybe not. I changed everything to unsigned long int and 88573 was still the point where the performance went down drastically. My guess is this has to do with paging.
On my machine with 4K sized pages, the array A will require 129 pages of memory. I think the working set limit might be 128 pages. 88572 will require 129 pages too, but our algorithm ends up accessing a lot less pages, because the power of 3 involved is 3¹⁰, so we require no more than 128 pages to remain in memory rather than the 129 which 88573 requires. Maybe the access pattern is fooling the page replacement algorithm of the OS.

Of course this might be all be nonsense.

btw, are you using Visual Studio by any chance?

Title: Re: rearrange the array.
Post by Aryabhatta on Sep 15^th, 2004, 8:07pm

Forget the blabber about paging.

It *is* an integer overflow. Because of that we have an infinite loop.

In the follow_cycle function:

for n = 88573 we have
inverse2 = 88574.
for seed = 1 (the first case)
the variable cur has to become 88573*2 sometime.
(this is because theoretically, cur must iterate through all the numbers relatively prime to 88573*2+1)

now 88574*88573*2 is > 2^32...
so there is an overflow.

It is also possible that cur never achieves 88573*2 because an overflow occured *earlier* causing an infinite loop and never reaching 88573*2.

I guess by we can get around this by using two 32 bit numbers to represent the intermediates of our computation, without changing the linear order of time...

Title: Re: rearrange the array.
Post by towr on Sep 16^th, 2004, 7:51am

Currently on most computers int and long int are equal in size (i.e. 32 bits). You can try long long int (64) instead if you actually want something bigger.
Or use some a very large integer library :P

Title: Re: rearrange the array.
Post by Aryabhatta on Sep 16^th, 2004, 9:26am

on 09/16/04 at 07:51:21, towr wrote:

Isn't the distinction between int and long int compiler dependent and not the machine? I guess most compilers make a distinction between int and short int and keep int and long int the same...

Anyway for our purposes, we don't need a large integer library because we will be multiplying at most two u_ints which will fit nicely in 2 u_ints. If we use a large integer library, the running time of the algorithm might not be linear anymore, in fact space usage might not be constant too, but that is an interesting problem to think about.

Title: Re: rearrange the array.
Post by NoName on Sep 16^th, 2004, 10:47am

Yeah, I forgot to tell you guys yesterday. After I switched to using 64 bit integers, that problem went away. The runtime went up, though, getting longer than for the O(N log(N)) algorithm I posted before. Because I don't have native 64-bit arithmetics. BTW, I'm using gcc-3.2.2 on i386-Linux.

I must say, I admire your solution, Aryabhatta, it's great. I can't help wondering, though, if there's a simpler way...

Title: Re: rearrange the array.
Post by towr on Sep 16^th, 2004, 11:21am

well, a (theoretical) O(N) algorithm may for all practical purposes always take longer than an O(N log(N)) algorithm.
One big problem is reading/writing of very large arrays, because you can't keep the whole array in memory/cache. This means that if you try to swap an element in the front of the array with one somewhere near the back, you'll have to swap from disk to memory (or memory to cache), again and again (since this is essentially what happens when we swap elements cyclicly). So it will be much better to divide and conquer, dealing mostly with one consecutive part of the array at a time.
On an ideal computer that shouldn't be a problem, but unfortunately it doesn't exist.

Title: Re: rearrange the array.
Post by Grimbal on Sep 16^th, 2004, 12:31pm

That would call for a method like this:

def proc shuffle(a, n) // a is 2n elements, starts at 0
- k = n/s
- swap a[k]..a[n-1] with a[n]..a[n+k-1]. The sizes of the parts to exchange might not be equal, but if it is the case, it is a rotation that is actually easier to do.
- shuffle(a,k)
- shuffle(a+2k,n-k)
end proc

The good thing is that when you begin and swap big parts, you go through them sequentially, so you access only 2 pages at a time. Later, when the interval becomes small, you swap small parts that fit in 1 or 2 pages.

It is O(n log n) if I am not mistaken.

Title: Re: rearrange the array.
Post by Aryabhatta on Sep 17^th, 2004, 9:02am

Thanks NoName, I hope there is a simpler solution too.
Btw, why don't you register as a member? Registering gives you more features...

Title: Re: rearrange the array.
Post by John_Gaughan on Sep 21^st, 2004, 8:40am

on 09/16/04 at 10:47:23, NoName wrote:

The runtime went up, though, getting longer than for the O(N log(N)) algorithm I posted before. Because I don't have native 64-bit arithmetics. BTW, I'm using gcc-3.2.2 on i386-Linux.

As long as your CPU supports MMX or SSE, you have 64 bit integer arithmetic. 32 bit CPUs perform 64 bit arithmetic by using MMX and SSE registers. While it is not as fast as a true 64 bit CPU, it is much faster than emulation. The version of GCC you use supports these extensions, although you may have to enable them with a compiler flag.

Also, keep in mind that any inefficiencies in the implementation are constants, so they will not affect your algorithmic asymptotic notation. It is still O(N lg(N)).

Title: Re: rearrange the array.
Post by m_aakash on Apr 9^th, 2008, 3:11am

a) If all the elements are positive then here is a simple O(n) and O(1) space algorithm.
i/p: a1 a2 a3 a4 b1 b2 b3 b4
o/p: a1 b1 a2 b2 a3 b3 a4 b4

element at index (i *n) % (2n-1) goes to index i. follow up this cycle. since elements are positive keep track of which elements are moved to correct positions by negating them.
Take the next index which is positive and again continue the above process till all elements moved to their correct locations.

b) for general array of size n, we need n bits to know which elements moved to correct positions.

edit: rewritten b to make it clear suggested by aryabatta

Title: Re: rearrange the array.
Post by pscoe2 on Apr 9^th, 2008, 6:47am

@m_aakash

i dont think the algo will work as intended
because once u know the pos of say 2nd element will u swap it with the 3rd one.
If u swap the index or third one will be lost....
If u dont do so how will u save the indexes in O(1) space....
The only way i can think this algo can be implemented is by finding the index of the next one b4 swapping...
wht do u say

Title: Re: rearrange the array.
Post by m_aakash on Apr 9^th, 2008, 10:00am

on 04/09/08 at 06:47:57, pscoe2 wrote:

Why do you want to save index at all....i am just traversing cycle by cycle..
Example: Assume the array starts from index 0

1<--- 4 <----- 2 <------ 1 this is one cycle
3<--- 5 <----- 6 <------ 3 this is second cycle

Title: Re: rearrange the array.
Post by Aryabhatta on Apr 9^th, 2008, 10:25am

Aakash, did you read the algo that was posted?

It is O(n) time and O(log n) bit space, so it is minimum in terms of time and space complexity.

O(n) bits is not mimimum space... as we can do better (O(logn) bits).

So the statement, "... we _need_ a bit array of size n ..." is misleading.

Title: Re: rearrange the array.
Post by m_aakash on Apr 9^th, 2008, 10:37am

i did..
no doubt it is better in terms of space complexity...
whatever i have given is best only if the data is positive.

one more positive side of algorithm i have given is its simplicity.

i edited that post as per your suggestion

Title: Re: rearrange the array.
Post by Aryabhatta on Apr 9^th, 2008, 5:26pm

Well if you are willing to trade on space for simplicity, why not just create another array and put the elements in their right place? O(nlogn) space, but really simple algorithm.

I think you are missing the spirit of the puzzle. And if not, I apologize and won't say anything further.

Title: Re: rearrange the array.
Post by m_aakash on Apr 10^th, 2008, 12:32am

on 04/09/08 at 17:26:58, Aryabhatta wrote:

Well if you are willing to trade on space for simplicity, why not just create another array and put the elements in their right place? O(nlogn) space, but really simple algorithm.

If you create other array it will take O(n) element space. but we only need O(n) bit space to implement my algorithm. it is certainly better. The needed logic is what i have given in my algorithm. If the elements are positive even we dont need that O(n) bit space.

Quote:

I think you are missing the spirit of the puzzle. And if not, I apologize and won't say anything further.

one insight to the puzzle is what i presented that is definitely not trivial.

Title: Re: rearrange the array.
Post by Aryabhatta on Apr 10^th, 2008, 9:23am

on 04/10/08 at 00:32:01, m_aakash wrote:

You don't need O(n) element space. O(nlogn) bit space is enough. (You can store the indices and not the elements themselves).

Anyway, I think there is no point discussing this further.

Title: Re: rearrange the array.
Post by m_aakash on Apr 10^th, 2008, 10:05am

yes..O(nlogn) bit space is sufficient but it still more than O(n) bit space.

i feel it needs attention because this idea is used for transposing rectangular array inplace as well. This puzzle is just a special case of transposing 2*n array.

Title: Re: rearrange the array.
Post by Devil on Apr 12^th, 2008, 8:53pm

my shot at it
2n = no of items

for(i = 0; i < n - 1; i++)
{
y = x[n + i];
for(j = n + i; j > (2 * i + 1); j--)
{
x[j] = x [j - 1];
}

x[2 * i + 1] = y;
}

Title: Re: rearrange the array.
Post by Grimbal on Apr 13^th, 2008, 12:47pm

That is O(n²)

Title: Re: rearrange the array.
Post by game_iiith on Nov 24^th, 2009, 10:01pm

My try at the problem, but I feel its too trivial looking at the discussion which this problem has aroused. Can somebody please point out an error in my understanding/algorithm of the problem.

Code:

#include <stdio.h>

int main()
{
int n, i, j , k, t1, l;
scanf("%d",&n);
int arr[n<<1+1];
for (i=1,j=n<<1,k=-1,l=0;i <= j ; i++ )
{
if ( i <= n )
arr[i] = k+=2; // 1 3 5 7
else
arr[i] = l+=2;
}
arr[0]=0;
// Shuffleing starts
i = 1;
int chk[j+1]; // To check if each element was visited only once
for (i=0;i<=j;i++)chk[i]=0;
i = 1;
while (i <= j)
{
while (i<=j && arr[i] == i) i++;
if (i >j)
break;
t1 = arr[i]; // swap with temp
k = i; // note the curr. loc in array
l = i;
printf("%d : Value of i entering loop\n",i);
while (1)
{
k = k&1?(k+1)/2:n+k/2;
chk[k]++;
if ( k == i)
break;
arr[l] = arr[k];
l = k;
}
arr[l] = t1;
}
for (i=0;i<=j;i++)
printf("%d ",arr[i]);
printf("\n");
for (i=0;i<=j;i++)
if (chk[i]>1)
printf("%d %d\n",i,chk[i]);
return 0;
}

Title: Re: rearrange the array.
Post by hary on Feb 7^th, 2010, 9:24am

Aryabhatta, i went through the link where you have posted the problem. I read the entire paper you wrote. I personally feel the algorithm you have presented has a sound proof w.r.t Mathematical Analysis. One thing i want to say, in your paper you have nowhere talkes about the space complexity - although a header seems to be there. Although i read grimbals post where he insited on the fact that the space complexity would be O(logn). I am still not getting how can we claim it. i will read the posts once again to work on the space complexity part. Thanks.

Title: Re: rearrange the array.
Post by hary on Feb 7^th, 2010, 9:38am

Additionaly, towr could you help me with this.

I read the O(nlogn) solution in one of the posts.

Call Rearrange(A,1,2N) initially, it will rearrange the array in O(1) space. The time complexity is discussed at the end.

Rearrange(A,p,q)
1. if p is not equal to q do the following
2. r ←- (p+q)/2
3. Exchange A[(p+r)/2..r] ←→ A[(p+q)/2 +1 ..(r+q)/2].
4. Rearrange(A,p,r)
5. Rearrange(A,r+1,q)
6. return

I have doubts about step3. Can someone throw light on this.

Title: Re: rearrange the array.
Post by towr on Feb 7^th, 2010, 10:05am

on 02/07/10 at 09:38:01, hary wrote:

I have doubts about step3. Can someone throw light on this.

What that algorithm does is to ensure that each subarray you work with in later steps has some number of A's followed by the same number of Bs: {A_i, A_i+1, .., A_j, B_i, B_i+1, .., B_j}

So it goes
A₁, A₂, A₃, A₄, A₅, A₆, A₇, B₁, B₂, B₃, B₄, B₅, B₆, B₇
A₁, A₂, A₃, A₄, B₁, B₂, B₃, B₄, A₅, A₆, A₇, B₅, B₆, B₇
A₁, A₂, B₁, B₂, A₃, A₄, B₃, B₄, A₅, A₆, B₅, B₆, A₇, B₇
A₁, B₁, A₂, B₂, A₃, B₃, A₄, B₄, A₅, B₅, A₆, B₆, A₇, B₇

Title: Re: rearrange the array.
Post by bmudiam on Feb 8^th, 2010, 7:14pm

Try this.

A1 B1
Nothing to be done

A1 A2 B1 B2
Start at n/2+1 = 3 position i.e B1 and move it one element backward. Now A2, moves 1 element forward, if A3 exists it moves one element forward etc..

A1 A2 A3 B1 B2 B3
-> A1 B1 A2 B2 A2 B3

A1 A2 A3 A4 B1 B2 B3 B4
-> A1 B1 A2 B2 A3 B3 A4 B4

The idea is as below.

Start from n+1 to 2n.

Move the A2, 1 point, A3, 2 points forward etc..

If you cannot find a position to put an element, start from N+1 and move them back filling in the spaces.

This takes minimum number of steps.