Author |
Topic: rearrange the array. (Read 6460 times) |
|
saujin
Newbie
Posts: 9
|
 |
rearrange the array.
« on: Sep 3rd, 2004, 12:53pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7526
|
|
Re: rearrange the array.
« Reply #2 on: Sep 4th, 2004, 10:57am » |
Quote Modify
|
Simpler, it is like shuffling A2..An with B1..Bn-1, using the other method, leaving A1 and Bn in place.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: rearrange the array.
« Reply #3 on: Sep 6th, 2004, 2:03pm » |
Quote Modify
|
saujin, I am curious to know your solution. Could you please post it here?
|
|
IP Logged |
|
|
|
NoName
Guest
|
on Sep 3rd, 2004, 12:53pm, 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;
}
|
|
|
|
IP Logged |
|
|
|
NoName
Guest
|
on Sep 7th, 2004, 12:28pm, NoName wrote:
Sorry, my bad. This does not work for N>11.
|
|
IP Logged |
|
|
|
saujin
Newbie
Posts: 9
|
|
Re: rearrange the array.
« Reply #6 on: Sep 13th, 2004, 12:00pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
NoName
Guest
|
on Sep 7th, 2004, 1:02pm, 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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: rearrange the array.
« Reply #8 on: Sep 14th, 2004, 3:07pm » |
Quote Modify
|
on Sep 14th, 2004, 1:28pm, 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 = 3k <= 2n < 3k+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 3i 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.
|
| « Last Edit: Sep 14th, 2004, 3:09pm by Aryabhatta » |
IP Logged |
|
|
|
NoName
Guest
|
on Sep 14th, 2004, 3:07pm, Aryabhatta wrote:
Step 1) Find an m such that 2m+1 = 3k <= 2n < 3k+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 3i 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?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: rearrange the array.
« Reply #10 on: Sep 14th, 2004, 9:53pm » |
Quote Modify
|
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;
}
|
|
|
| « Last Edit: Sep 14th, 2004, 9:55pm by Aryabhatta » |
IP Logged |
|
|
|
NoName
Guest
|
|
Re: rearrange the array.
« Reply #11 on: Sep 15th, 2004, 10:20am » |
Quote Modify
 Remove
|
on Sep 14th, 2004, 9:53pm, 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 ?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: rearrange the array.
« Reply #12 on: Sep 15th, 2004, 1:17pm » |
Quote Modify
|
on Sep 15th, 2004, 10:20am, 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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: rearrange the array.
« Reply #13 on: Sep 15th, 2004, 4:48pm » |
Quote Modify
|
on Sep 15th, 2004, 1:17pm, 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 310, 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?
|
| « Last Edit: Sep 15th, 2004, 5:23pm by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: rearrange the array.
« Reply #14 on: Sep 15th, 2004, 8:07pm » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: rearrange the array.
« Reply #15 on: Sep 16th, 2004, 7:51am » |
Quote Modify
|
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 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: rearrange the array.
« Reply #16 on: Sep 16th, 2004, 9:26am » |
Quote Modify
|
on Sep 16th, 2004, 7:51am, towr wrote: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 |
|
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.
|
|
IP Logged |
|
|
|
NoName
Guest
|
|
Re: rearrange the array.
« Reply #17 on: Sep 16th, 2004, 10:47am » |
Quote Modify
Remove
|
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...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: rearrange the array.
« Reply #18 on: Sep 16th, 2004, 11:21am » |
Quote Modify
|
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.
|
| « Last Edit: Sep 16th, 2004, 11:23am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: rearrange the array.
« Reply #19 on: Sep 16th, 2004, 12:31pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: rearrange the array.
« Reply #20 on: Sep 17th, 2004, 9:02am » |
Quote Modify
|
Thanks NoName, I hope there is a simpler solution too.
Btw, why don't you register as a member? Registering gives you more features...
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
Gender:
Posts: 767
|
|
Re: rearrange the array.
« Reply #21 on: Sep 21st, 2004, 8:40am » |
Quote Modify
|
on Sep 16th, 2004, 10:47am, 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)).
|
| « Last Edit: Sep 21st, 2004, 8:42am by John_Gaughan » |
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: rearrange the array.
« Reply #22 on: Apr 9th, 2008, 3:11am » |
Quote Modify
|
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
|
| « Last Edit: Apr 9th, 2008, 10:40am by m_aakash » |
IP Logged |
|
|
|
pscoe2
Junior Member
Gender:
Posts: 77
|
|
Re: rearrange the array.
« Reply #23 on: Apr 9th, 2008, 6:47am » |
Quote Modify
|
@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
|
|
IP Logged |
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: rearrange the array.
« Reply #24 on: Apr 9th, 2008, 10:00am » |
Quote Modify
|
on Apr 9th, 2008, 6:47am, pscoe2 wrote:@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 |
|
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
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print