Gunnar Kudrjavets

Are the arrays already sorted

a1 to an, b1 to bn?

No, the content can be totally random. Sorting in final output is also non-goal. Here's a sample:

INPUT: { 7, 3, 5, 9, 4, 2, 8, 6 }
OUTPUT: { 7, 4, 3, 2, 5, 8, 9, 6 }

More like if you can't solve this problem, send your cv to Microsoft.

I will give it. sounds like one of the questions from an ACM contest

added it to my blog here
http://blog.dotwind.com/archive/2004/05/12/152.aspx

The person who came up with O(N log(N)) solution is at his leisure time coach for my alma mater’s ACM International Collegiate Programming Contest team. Don't know if this is coincidence or not ;-)

I participated in one 2 years ago when I was at university. they are fun and teach you exactly this kind of things. how to make it work and make it work fast. I can say that this problem is puzling me right now very interesting :)

bwt I read some of your other post very nice specially the couch one lol

I'm guessing the O(N log(N)) algorithm is one where you swap ranges (a[1]-a[n/2] with b[1]-b[n/2]) and (a[n/2+1]-a[n] with b[n/2+1]-b[n]), then recursively swap each half of the array. Eventually you get down to n<=2. If n=2, then the swap will put the elements in their correct final order; if n=1, then you dont have to do anything because they are already in order. Swaps can be done in place w/o additional memory. Is this correct?

---

Now, I wonder if the following is a correct O(N) algorithm with constant memory requirement, but let me give a try:

We wish to rearrange: {a[1] ... a[n], a[n+1] ... a[2n]} into {a[1], a[n+1], a[2], a[n+2]... a[n], a[2n]} where a[n+1] is b[1] as indicated originally.

Each element's final location can be defined as follows:

For a[i] where i <= n, a[i] --> a[2i-1]; // elements a
For a[i] where i > n, a[i] --> a[2(i-n)]; // elements b

Assuming n > 2, we have pseudo-code:

1) i = 2;
2) temp = a[i];
3) if (i <= n)
{
swap(temp, a[2i-1]); i = 2i-1;
}
else
{
swap(temp, a[2(i-n)]); i = 2(i-n);
}
4) goto 3 and loop exactly n - 2 times.

This works after exactly n-2 loops because:
A) only the first and last elements are already in their final locations, where as all other elements in between are not.
B) no 2 elements will ever get placed into the same final location. -> no collision
C) each element needs exactly 1 swap to be placed into its correct final location.
D) B and C -> that every time we do a swap, 1 element (temp) is being placed correctly and we get 1 new element (a[xx]) that needs to be rearranged.

So, it follows that we only need n-2 swaps to correctly rearrange an array of n elements.

O(N)?

I looked at your question for the algorithm. I have the solution for O(N log(N)).

Assuming you have:

a0 a1 a2 a3 a4 a5 a6 b0 b1 b2 b3 b4 b5 b6

Assign to the first N a even displacement.

0 2 4 6 8 10 12
a0 a1 a2 a3 a4 a5 a6

Assign to the b0 to bN a odd displacement.

1 3 5 7 9 11 13
b0 b1 b2 b3 b4 b5 b6

So you get:-

0 2 4 6 8 10 12 1 3 5 7 9 11 13
a0 a1 a2 a3 a4 a5 a6 b0 b1 b2 b3 b4 b5 b6



Now just do a quicksort on
0 2 4 6 8 10 12 1 3 5 7 9 11 13
to get
0 1 2 3 4 5 6 7 8 9 10 11 12 13
which corresponds with the solution required.

This took me a good 20 min to solve. I first tried to do it without memory constraints. Then I tried it with.

Very interesting problem. Just need to "think outside the box" as you MS people say :-)

As for proving that there is no better solution: I can't. :-)

Okay.. this method will use 2x the memory usage of the array. Don't know what the datatype of your elements is but using recursive algorithms could result in a stack overflow and also uses memory.

This method assumes that the array contains reference types. An array of big value types will result in lots of data swapping so that wouldn't be very efficiënt.

I like the quicksort method.. But you aren't sorting so why compare all elements all the time because that is not necessary.

object[] DoWeirdSort(object[] input)
{
int l = input.length

Assert(l%2==0, "The array should contain an even number of elements");

int half = l>>1;


object[] output = new object[l];

int possrc = 0;
int posdst = 0;

while(possrc<half)
{
output[posdst] = input[possrc++];
posdst += 2;
}

int possrc = half;
int posdst = 1;

while(possrc<half)
{
output[posdst] = input[possrc++];
posdst += 2;
}
}


By the way, what do you mean with "and uses no more than constant amount of memory"? That his algorithm does not allocate memory at all (thus swapping a lot) or uses allocates one block of memory to store the result? The last would also use a constant amount of memory.

hmm I forgot a line at the end of the function:

return output;

:)

I think the challenge, ramon, is to do this with as little memory use as possible. ie. No doubling the array size :-)

Solution in J:
,|:(2,-:$w)$w=. 7, 3, 5, 9, 4, 2, 8, 6
7 4 3 2 5 8 9 6

or in tacit form:
([:,[:|:(2:,[:-:$)$])w
7 4 3 2 5 8 9 6

No sorts. Just a transpose. If the number of elements is odd it will give an error.

In the apl J (www.jsoftware.com) the job is done in linear time by ({~ [:([:,i.+/0&,)-:@#)

For random arrays of length 100, 1000, 10000, 100000, 1000000, 10000000 the performance figures - execution time and
execution space - are
0.0001729368986 5248
0.001191916101 23168
0.009927548667 330432
0.1201951976 2624192
1.207780134 20974272
12.26773846 335547072
So, executiontime over arraylength times 1e6 equals
1.7294 1.1919 0.9928 1.2020 1.2078 1.2268

R.E. Boss

My J solution:
,@(({.,.}.)~-:@#)

It's more or less the same approach as Don Guinn's, but I don't bother with the transpose because as long as the length of the input is even ,. will suffice.

I would handle odd-length inputs (and use the transpose) only if the spec allowed me to choose a value to pair with a[n].

-Dan

Dave Kong's proposed O(N) solution above won't work in all cases unfortunately.

It will work for n=2,3,6 but not n=4,5 (for example).

Not without keeping track of which elements have already been moved and that (may) defeat the purpose of the exercise.

I think that Dave Kong's solution is very good, as it can be implemented in almost any language, keeping a constant amount of memory and a linear function order.

Dave, The only flaw I've found in your algorithm is that you have to loop 2n-2 times, because the array length is 2n.

Jose.

Dave: can you write up a simple program and post the source code? Yes, based on the pseudo-code everyone can do it, but if author will do it himself, it’ll be better (my implementation didn’t work properly and I want to make sure that I’m not misinterpreting something).

Sushant: the Quicksort solutions is a very good one, but the trick with Quicksort is that you’ll end up using O(log(N)) of memory because of recursion (memory needed for stack). Even removing recursion will force you to implement your own private stack which will require O(log(N)) of heap memory. Also, how do you keep track of indices while doing the Quicksort? We wouldn’t like to destroy the original contents of the array.

Ramon: "and uses no more than constant amount of memory" is one way of saying that the amount memory used can’t be a function of N. Yes, a “very big” constant can be picked, but then one can always define the N in such way that this constant amount of memory won’t be enough.

Don Guinn/R.E. Boss/D. Bron: you are just so cool ;-) and remind of gurus for specific languages who offer to solve some interview questions with one line Perl script or write a simple Prolog program to solve the problem of eight queens ;-) That’s definitely outside the box thinking.

Dave,

After some more testing, I found that your algorithm is not valid for some values of N. For instance, this is a kind of trace for N=4 :

N = 4 // Array length = 8;
I = 2

I <= N (2 <= 4) -> I = 2I-1 -> I = 3;
I <= N (3 <= 4) -> I = 2I-1 -> I = 5;
I > N (5 > 4) -> I = 2(I-N) -> I = 2;
I <= N (2 <= 4) -> I = 2I-1 -> I = 3;

As you can see, after third iteration the I values begin to repeat, and it works only if each item in the I sequence is unique, i.e. all the array items are swapped sooner or later.

It's weird, because it fails for N = 4,5,8 or 9 but it works for N = 1,2,3,6,7 or 10. Just curious about why exactly that values make the algorith to fail.

Jose.

* Shuffle one at a time

n = 10
half = n/2

Dimension theArray[n]

* Load the array
For i = 1 to n/2
- theArray[i] = "A"+Transform(i)
- theArray[(n/2)+i] = "B"+Transform(i)
EndFor
showArray()

* Move around
seed = 2
i = seed
move = theArray[i]
DO while forever
- If i<=half Then
- i = i*2-1
- Else
- i = (i-half)*2
- Endif

* swap
- temp = theArray[i]
- theArray[i] = move
- move = temp

- If i=seed Then
- seed = getNewSeed()
- i = seed
- Endif
EndDo

showArray()

Note: find a new unused index when stuck

But I think it's best to used non-interleaved audio data format, one separate buffer for each channel.

btw, the biggest array i could test for in one shot was n=2^14-2 and n=60000 takes two seeds

Unfortunately foxpro doesn't let me use arrays bigger than 64k

I'll try .Net at home ;-)

Wait a minute. Why use normal Arrays. Why not use a singly linked list? You get the same data, albiet with a bit more memory use but I bet you can sort that in one pass. O(N). I'll work on the code for that now.


Or better yet....use an ArrayList and change the index for the element as you go through it. :-)

I still prefer the Linked list way though but here is the code for the ArrayList way.

<myCode>
//---------------------------------------------------------
// May 12 2004
// Code by Sushant Bhatia
// Use freely but is provided as is.
// I dont take responsibility if this screws up your system
//---------------------------------------------------------
using System;
using System.Collections;

namespace BlogProg
{
/// <summary>
/// Summary description for Class1.
/// </summary>
class Class1
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
ArrayList array = new ArrayList();

int n = 8;

#region CREATING ITEMS
// Add Items to Array in even order
// 0 2 4 6 8 10 ....
for(int i = 0; i < n; i++)
{
array.Add((i*2));
}

int max = n*2 - 1; // max value for odd

// Add Items to Array in odd order
// 1 3 5 7 9 11 ...
for(int i = 1; i <= max; i = i + 2)
{
array.Add(i);
}

#endregion

// Begin sort

int insertAt = 1; // location to add the values at
for(int i = n; i <= max; i++)
{
int val = (int) array[i]; // copy the item
array.RemoveAt(i); // delte from array
array.Insert(insertAt, val); // insert at insert point
insertAt = insertAt + 2; // add every 2 indicies
}

// Print the sorted array
for(int i = 0; i <(2*n); i++)
{
Console.WriteLine(array[i]);
}

}
}
}


</myCode>

Jose, Jonathan,

You guys are right, my algorithm is flawed. (I tested n=1,2,3 but not 4... crap) :(

Like you waid, I dont want to use an array or bitfield to track which elements have been placed since that will require O(N) memory usage.

I'm trying to see if I can do a single pass through the array and detect which elements have already been moved w/o O(N) memory. I think the cycles fall into equivalence classes of some sort, so i won't be checking the same element more than twice (once to swap, once to see if it's already been moved). So hopefully it's still O(N).

I will let you know. And if it's indeed still O(N), I will post working code.

And yes, I meant 2n-2. (can't even count anymore...)

Dave & All,

Can't you recursively replace the items. I noticed from my doodling that there seemed to be a pattern.


Given:

a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7

a0 b0 a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7


In order to do b0 -> a1 you need to do
a1 -> a2 -> a4 -> b0 -> a1

In order to do b1 -> a3 you need to do
a3 -> a6 -> b4 -> b1 -> a3

In order to do b2 -> a5 you need to do
a5 -> b2 -> a5

In order to do b3 -> a7 you need to do
a7 -> b6 -> b5 -> b3 -> a7

So its a recursive replacement. You dont need to use any more memory than that used for a swap.

I haven't tried this but i believe that for even N the number of recursive replacements will be no more than N / 2. But thats just a theory.

The trick here is to predict which ones will be affected and which ones go where. But this is just my though...I dont know how to code this, maybe someone more skilled could try that.

It seems that the official name for the problem is "Out-Shuffle". See http://mathworld.wolfram.com/Out-Shuffle.html for more detailed information.

I just tested my above code with a profiler. Here are the results for N.

<b>N = 10</b>
Total Timing: 1,065,176.0 Microseconds

<b>N = 100</b>
Total Timing: 1,128,405.8 Microseconds

b>N = 1000</b>
Total Timing: 1,453,121.6 Microseconds

b>N = 5000</b>
Total Timing: 2,855,583.9 Microseconds

b>N = 10,000</b>
Total Timing: 4,879,072.0 Microseconds

b>N = 100,000</b>
Total Timing: 120,548,764.2 Microseconds

Interesting thing I found was that it takes N = 2610
in order to beat the 2s mark.

-- let SQL do the work --

create table numbers (
num int,
value varchar(2)
)

delete from numbers
insert into numbers values (0,'A0')
insert into numbers values (1,'A1')
insert into numbers values (2,'A2')
insert into numbers values (3,'A3')
insert into numbers values (4,'A4')
insert into numbers values (5,'A5')
insert into numbers values (6,'A6')
insert into numbers values (7,'A7')
insert into numbers values (8,'B0')
insert into numbers values (9,'B1')
insert into numbers values (10,'B2')
insert into numbers values (11,'B3')
insert into numbers values (12,'B4')
insert into numbers values (13,'B5')
insert into numbers values (14,'B6')
insert into numbers values (15,'B7')

select * from numbers


update a set a.value = b.value
from numbers b, numbers a where b.num = ((a.num + (16 * (a.num % 2))) /2)

select * from numbers

drop table numbers

Kev Mar,

That falls into the realm of A) special language tricks and B) doesn't meet the challenge.

Anyone can write an algorithmn to do it, it's a matter of a) doing it in constant memory and b) O(N log(N)) time or better.

I can write one in seconds that does it in O(N) time and O(N) memory usage. Similarly, you can write a much faster sort routine that Quicksort if you allow non-inplace sorts.

Your SQL query uses a cross join which is neither of those.


David, your solution is very, very close to mine.

1 Set either 0+1 OR 2n-2 as my initial spot to fill.

2 Copy my inital spot value to the temp variable.
3 Find the value that goes into my "vacant" spot, and copy it there.
4 Find the value that goes into the spot I just copied from, and copy the value to that spot.
5 Repeat previous step until I would copy my initial value into the empty spot, then I copy the temp into it and I know I've ended a cycle.

6 figure out from counters/various maths if I have more cycles left. In which case, set my initial spot to an element of an unprocessed cycle, and proceed to 2.


Unfortunately, my present step at 6 starts failing erratically at 12 and above, with no clear pattern.

My new instinct is that O(N) is impossible using constant memory (without a lot more math theory than I have ;)

I'll have to see if I can pull off O(N) after I pull out some books that deal with cycles, but I have a feeling it would involve more math that I can put into it right now.

Actually, I think I can redo step 6 above in a way that I know should work, but would push me into O(N log(N)) operations despite O(N) copies :)

/*
Kevin Marquette
Yes there is a pattern to predicting what value will replace another.
given i = index
if i < n/2 then i -> 2n
if i > n/2 then i -> n-((n-i)*2)

to predict what value replaces the current index
if i % 2 = 0 then i <- i/2
if i % 2 = 1 then i <- (n+i)/2
or
i <- (i+(n*(i%2)))/2

the pattern will loop back onto itself and some sets will have several non-intersecting loops.

a 54 element array is one continious loop, but a 32 element array has 5. 2^n numbers usualy have higher number of loops (I think).

I have not figured out how to predict the loops yet, so I keep track of elements copied.

here is my working solution. Each value is read only once and it is inserted directly into its final location. (all but the first item in a loop)
*/

static void Main(string[] args)
{


int[] list = new int[5400];
bool[] check = new bool[5400];
int len = list.Length;

// Fill list with values
for( int i = 0; i != list.Length; i++)
{
list[i] = i;
}
// suma is the sum of 0 to N
int suma = (len*(len-1))/2;
int sumb = len - 1;

// index is the current index in the list
int index = 1;

int value;
int nextIndex;
int startIndex;

int loopCount = 0;
do
{
loopCount++; // result tracking

// find the first value that has not been replaced
while( index != (check.Length) && check[index] == true){
index+=2; // It is never an even value (usualy prime)
}

// save the first value so we dont loose it
value = list[index];
nextIndex = index;
startIndex = index;

do
{
// calculate the index that should replace the current index
nextIndex = ((index + (len * (index % 2))) / 2) ;
// replace the values in memory, read once, write once
list[index] = list[nextIndex];
check[index] = true; // marks the index as replaced
sumb += index;
index = nextIndex;

}while (index != startIndex);

// place the first value where is goes
list[startIndex + startIndex] = value;

} while (suma > sumb); // if suma = sumb then we have replaced all indexes


// display results
for(int i = 0; i != list.Length; i++)
{
System.Console.WriteLine(list[i]);
}
System.Console.WriteLine("N={0} OuterLoops={1}",len, loopCount);

int buffer = System.Console.Read();

}

Why not build a B+ Tree and use that to sort the elements in buckets. But I guess that would be overkill. :-)

Below is a Python implementation which exchanges the elements in place; it performs 1 exchange per element (actually 2n-3 exchanges). It is based on the observation that, as you move 'a' elements to the second half of the array by exchanging them, the 'a' elements sort themselves like this (using 0-based indexes):

index orig. index
n 1 * 2**x
n+1 3 * 2**x
n+2 5 * 2**x

where x starts with 0 (when swapping a b element for an a element) and increments when you swap an a element for another a element.

(Sorry about the leading underscores, but it appears from previous posts that leading whitespace is stripped. Also, to be clear, // is the Python integer division operator, and the for loop will give i the values 0..n-2, inclusive).

def exchange(arr, i1, i2):
____if i1 == i2: return
____temp = arr[i1]
____arr[i1] = arr[i2]
____arr[i2] = temp

def arrange(arr):
____n = len(arr) // 2
____for i in range(n-1):
________if i:
____________dest = i*2 # index a element will be moved to
____________j = i
____________while True:
________________while not (j & 1):
____________________j >>= 1
________________src = (j // 2)+n # current index of a element
________________if src >= dest:
____________________break
________________# if src < dest, need to redo with src, since
________________# element which was in src has been swapped
________________# further back in the array
________________j = src
____________exchange(arr, dest, src)
________# b element is in i+n (original position)
________exchange(arr, i*2+1, i+n)

Yet another version in O(n log n)...



for( long i=1; i<list_size/2; i++ )
{
// optional quick reject
//{
if( i>1 && (i&(i-1))==0 )
continue;
//)

long j = i;

do
{
j = (j/half) + (j%half) * 2;
}
while( i<j );

if( j!=i )
continue;

for(;;)
{
j = (j/half) + (j%half) * 2;
if( j==i )
break;
xch( i,j );
}
}



Comments/explanation later (too sunny outside right now)

-Thomas

Thomas, I'm curious what the optional quick reject does exactly? I suppose I could have ran your code without it to see what the difference is, but it's late :)

My sort is a moral equivalent of yours and Dave's.

I've found that hunting down cycles is the hardest part. I think we're only O(N LOG(N)) on average, cause theres a few cases that absolutely kill our algorithmns.

One improvement you might think about is keeping a counter of how many elements you've processed so you can bail out early.

For an N of 63452, there are 404 cycles and you end up running your cycle finding loop loop something like 404+63032 times. (Granted, I think most of the ones on the end are probably very few iterations before it finds out it is on a bad cycle.)

Mine for the same N runs it's cycle finding loop 404-1+26790 times.


If I had the higher maths, I'd try to find the relationships between N and the beginning of the cycles, but right now it looks completely random to me. Maybe I'll cheat and see if someone has a white paper somewhere :)


Anyway, here's my sort. It's subtly different in a copule of areas from yours.:

private void Sort(int[] array)
{
// sanity check.
if (array.Length <= 2 ) return;

int length = array.Length;


int iterations=0;
int totalSwaps=0;
int cyclesRechecked =0;

int initial = 1;

int pos = initial;
int target;

int temp;

for(;;)
{
++iterations;

target=-1;
temp = array[pos];

#region Process Cycle

for(;;)
{
// Process the cycle

target= ((pos&1)*(length-1)+pos)/2;

if (target != initial)
{
array[pos] = array[target];
pos = target;
++totalSwaps;
}
else
{
array[pos]=temp;
++totalSwaps;
break;
}
}
#endregion

if (totalSwaps == length-2)
break;

#region Find Next Cycle To Process
for (;;)
{
pos = initial = initial + 2;

if (pos>1 && (pos&(pos-1))==0)
continue;

for (;;)
{
pos = ((pos&1)*(length-1)+pos)/2;

if (pos <= initial)
break;
}

if (pos == initial)
{
System.Diagnostics.Debug.Assert(!(pos>1 && (pos&(pos-1))==0), "Skip Condition Not True?!?");
break;
}

++cyclesRechecked;
}
#endregion
}

Console.WriteLine("{0},{1},{2}", totalSwaps, iterations, cyclesRechecked);
}

If I have time, I have an idea for a braiding sort that probably won't work for large N's, but it's interesting none-the-less.

Computer Journal, Volume 43, Issue 1, pp. 40-53: Abstract.


In situ, Stable Merging by Way of the Perfect Shuffle
John Ellis1, and Minko Markov1

With minimality proofs!

I added the pointer to "In situ, Stable Merging by Way of the Perfect Shuffle" yesterday, but I never had time to read through the article.

P. S. Aitäh viite eest ;-) (Thanks for the reference – for those of you who don’t speak Estonian ;-))

/*
First idea:
Copy element by element like this (N = 4)
c=a2; a2=b1; b1=a3; a3=c; c= a4; a4=b2; b2=b3; b3=c;
This has the complexity of O(N) and need only extra memory for element c.

But for a large array (many memory pages) it is not optimal for performence (memory caching) to jump between pages very frequently.

Second idea:
Copy page by page and use only 2 additional physical memory pages and has the complexity of O(N).
See code sample below (C++, Windows XP).
*/

void test()
{
typedef DWORD T; // the type of the element
typedef T *PT;
SYSTEM_INFO systemInfo;
GetSystemInfo(&systemInfo);
DWORD pageSize= systemInfo.dwPageSize;
DWORD nPages= 8; // the number of pages in the element array
DWORD bufferSize= nPages * pageSize; // the number of bytes in the element array
DWORD n= (bufferSize / sizeof(T)) / 2; // the array contains 2 N elements
DWORD nPerPage= pageSize / sizeof(T); // the number of elements in a page
// only reserve virtual memory, no physical memory
PT pBuffer1= (PT)VirtualAlloc(0, bufferSize, MEM_RESERVE, PAGE_NOACCESS); // read array
PT pBuffer2= (PT)VirtualAlloc(0, bufferSize, MEM_RESERVE, PAGE_NOACCESS); // write array

// alloc physical memory to the array 1 (read array)
VirtualAlloc(pBuffer1, bufferSize, MEM_COMMIT, PAGE_READWRITE);
// for testing, initialize the read array with the array index
{
for(DWORD i= 0; i < 2*n; i++)
{
pBuffer1[i]= i;
}
}

// write the array page by page
// alloc late as possible
// free early as possible
{
PT a= pBuffer1; // a1, a2, a3, ..., an
PT b= pBuffer1 + n; // b1, b2, b3, ..., bn
PT c= pBuffer2; // a1, b1, a2, b2, ..., an, bn
for(DWORD i= 0; i < nPages; i+= 2)
{
// alloc 2 pages in the array 2
VirtualAlloc(c, 2*pageSize, MEM_COMMIT, PAGE_READWRITE);
for (DWORD n1= 0; n1 < nPerPage; n1++)
{
c[2*n1]= a[n1];
c[2*n1+1]= b[n1];
}
// free 2 pages in array 1
VirtualFree(a, pageSize, MEM_DECOMMIT);
VirtualFree(b, pageSize, MEM_DECOMMIT);
a+= nPerPage;
b+= nPerPage;
c+= 2*nPerPage;
}
}

// use the array 2
// free array 1 and 2 or use again
}

Scrap the “quick reject” bit, it was a desperate (and pointless) attempt to get rid of the cases where “i” is a power of 2.

Agree that finding that you’ve not already met a cycle was not the best approach, here’s a new one, much faster.

Let’s see it with an example:
The starting point i=3 in a list of 20 elements will give the following cycle:
3 6 12 5 10 1 2 4 8 16 13 7 14 9 18 17 15 11 3

At each step you multiply by 2 and the new value is above 20, you wrap around and add 1. Each time you ‘wrap around’ you have a new seed. Here they are: 3, 5, 1, 7, 9, 17, 15, 11.

To know how many times you need to multiply by 2 before you can find a new seed, you try to find ‘b’, the largest solution to: i * 2^b < S; where S is the size of the list, here S=20.
That translates to: b = Log2(S/i)

The new algo is:
1 - j = ‘i’ with the zeros (in base 2) stripped out from the right; that’s our initial seed
2 - find how many time you need to multiply by two
3 - compute the new seed
4 - if the seed j’ is <i the cycle has been visited for a smaller value of i; if j’ = i, it’s done we can proceed with permutations.

In C:


void do_it_again()
{
| for( long i=1; i<list_size/2; i++ )
| {
| | long j = remove_power_2( i );
| | if( j<i )
| | | continue;
| |
| | do
| | {
| | | const long b = log2(list_size/j);
| | | j <<= b;
| | | j = ((j % half)<<1) + 1;
| | }
| | while( j>i );
| |
| | if( j!=i )
| | | continue;
| |
| | for(;;)
| | {
| | | j = (j/half) + (j%half) * 2;
| | |
| | | if( j==i )
| | | | break;
| | | xch( i,j );
| | }
| }
}


You just need to define Log2(x) :

long log2_internal( unsigned long& x, unsigned long bit )
{
| if( x >= (1U<<bit) )
| {
| | x >>= bit;
| | return bit;
| }
| else
| | return 0;
}

long log2( unsigned long x )
{
| long result;
| result = log2_internal( x, 16 );
| result += log2_internal( x, 8 );
| result += log2_internal( x, 4 );
| result += log2_internal( x, 2 );
| result += log2_internal( x, 1 );
| return result;
}

And remove_power_2:

void remove_power_2_internal( long& x, long shift )
{
| if( (x & ((1<<shift)-1))==0 )
| | x >>= shift;
}

long remove_power_2( long x )
{
| remove_power_2_internal( x, 16 );
| remove_power_2_internal( x, 8 );
| remove_power_2_internal( x, 4 );
| remove_power_2_internal( x, 2 );
| remove_power_2_internal( x, 1 );

| return x;
}

On a list of 10,000 entries the previous version was testing 576,265 points, now it only tests 28,366.

-Thomas

Hmm

Looks like it would be good if blogs could take PRE or CODE tags to present code in a more readable fashion.

It is possible to do it in O(n) time and constant space..( O(log n) bit space actually.)

We need to shuffle a1 a2 .. an b1 b2 ... bn
to a1 b1 a2 b2 .... an bn.

Instead of this, we will do a similar permutation:
b1 a1 b2 a2 .... bn an

(can get to the required one from here easily)

Basically we have a permutation, Which can be decomposed into disjoint cycles.

For the given permutation, element i goes to element 2*i mod (2n+1).


For an O(n) time algo: We can easily pick one element and follow the cycle with that element and do the transpositions. Then go to next cycle and repeat until all cycles are done. But the problem we get is if there are many cycles, to get O(1) space usage, we need to be able to pick the 'next' cycle
in O(1) space and O(1) time.

The case when 2n+1 is prime, we have only one cycle and the algorithm is easy.

Primes always give us trouble though.

So let us consider a different case of n first.

Consider the case when 2n+1 is of the form 3^k for some k. It can be shown that 1,3,9,....,3^k, all belong to different cycles and those are the only cycles. (using the basic fact: (Z/p^e)* is a cyclic group)

for those n, we can easily pick the 'next' cycle.

The algorithm for those cases is:

i = 1;
while (i <= 3^k) {
permutecycle(i); //start at i and do the cycle shift
i = i*3;
}

which can be done in O(n) and O(1) space.


Now for a general n, find an M such that 3^M <= 2n+1 < 3^(M+1). (can in done in O(log n) time)

Let 2t+1 = 3^M.

view the array as

[a1 a2 ...at] [a(t+1) ... an b1 b2 ... bt] [b(t+1) ... bn]

we now make the array look like:
[a1 a2 ...at] [b1 b2 ... bt] [a(t+1) ... an] [b(t+1) ... bn]

(this can be done in O(n) time and O(1) space too, a block shift in the middle part..)


Do our special case of 2n+1 = 3^k on the first 2t+1 elements.

Recursively apply the same for the remaining part.

So we have O(n) time. We also have O(1) space because we recurse only on the tail..
so it is tail recursive and hence the recursion can be done in O(1) space.

I have left out the details of the proof and time/space analysis.
But i think this algorithm is correct works within the specified time and space limits.

Correction: if 2n+1 is prime we *need not* have just one cycle. (but that is irrelevant to the algorithm)

Also a typo: for the case 2n+1 = 3^k, the cycles we need to look at start with 1,3,3^2,...,3^(k-1) (3^k lies beyond the end of the array!)

The competition is pretty obviously starting to get out of my league :)

Thomas, that's what I kind of thought the code was, but wasn't sure. I inserted it into my own sort to see if it was ever triggered, and I neglected to remove it before posting my sort. Oops.

Nice improvement though :) That's a route I was originally going to try to take, but I just couldn't pull the math off.



Aryabhatta, are you sure that is still an O(N) sort?

When you switch to subdividing you break it into 2 pieces of size A and B, then do A/2 swaps. At best, you then have another A swaps to perform. Recursing on the second part could lead to another increase in the number of swaps, which I think can lead to A+A/2+C+C/2+......+Z+Z/2

Unfortunately, I can't really do the math right now to figure out if that's a greater than O(N) number of swaps, but still I'm impressed by some of the Math Kung Fu going on in your solution.


I really wish I would've kept myself in better mathematical fighting shape over the years :)

Okie i think in these terms

let the arrays be as follows (just for descriptive clarity)

A B C D E F G H
S T U V W X Y Z

step 2
consider these as chunks logically
A B C D E F G H
S T U V W X Y Z
replace 1 of second in these chunks with 2 of first row
A S C U E W G Y
B T D V F X H Z

consider these as chunk of 2 now
replace the lower (two) part with upper

A S C U E W G Y
B T D V F X H Z

To

A S B T E W F X
C U D V G Y H Z


Consider now these as chunk of 4

A S B T E W F X
C U D V G Y H Z

do the same action now for chunk of 4

A S B T C U D V
E W F X G Y H Z


till n / 2 (n - no of elements in each array)

The sorted ones are there

A S B T C U D V E W F X G Y H Z


In case of the odd elements the last one needs to be taken care of and appended at the end

Jason, the time complexity is O(N).

Let N = 2n.
We do the 3^k thing for at least N/6 elements and do the recursion only for the remaining elements.

So we have that:
T(N) <= A*N + T(5N/6)

T(N) is the time taken for N elements.
A*N is time to do the block shift, cyclic shift etc all added up. (A is some constant)

so T(N) <= A*N + (5/6)A*N + ((5/6)^2)*A*N + ....
(the RHS is a geometric progression)

so T(N) <= (1/(1-5/6))A*N = 6A*N

so T(N) = O(N).

I doubt, with all the research on the subject, that you could do better than something like

http://citeseer.ist.psu.edu/cache/papers/cs/7993/ftp:zSzzSzgodot.uvic.cazSzpubzSzPublicationszSzElliszSzmerge.pdf/ellis99insitu.pdf/

I'd much rather cheat:


using System;

class ShuffleCheat
{

private static int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 };
private static int it, step;


private static int
GetValue(int index)
{
return arr[index / 2 + (index % 2 == 0 ? 0 : arr.Length / 2)];
}


private static void
Reset()
{
it = 0;
step = arr.Length / 2;
}

private static int
Next()
{
int v = arr[it];

if (it < step)
it += step;
else
it += (1 - step);

return v;
}


public static void
Main(string[] args)
{
for (int i = 0; i < arr.Length; i++)
Console.WriteLine(GetValue(i));

Reset();

for (int i = 0; i < arr.Length; i++)
Console.WriteLine(Next());
}
}


...which gives you both the positional and "optimized" iterator methods.

Fixing this code for uneven array sizes is left as an excercise for someone with more time on their hands than I currently have :-)

start with n=8:
a1 a2 a3 a4 a5 a6 a7 a8 b1 b2 b3 b4 b5 b6 b7 b8

split it into quarters:
a1 a2 a3 a4 | a5 a6 a7 a8 | b1 b2 b3 b4 | b5 b6 b7 b8

now swap the two middle quarters:
a1 a2 a3 a4 b1 b2 b3 b4 | a5 a6 a7 a8 b5 b6 b7 b8

both ends of each half are now in the correct place, so you can now run the same logic to each half, like it was an n=4 section.

a1 a2 | a3 a4 | b1 b2 | b3 b4
becomes
a1 a2 b1 b2 | a3 a4 b3 b4

again we do the same thing here:
a1 | a2 | b1 | b2
becomes:
a1 b1 a2 b2

which is now in order.

You have to make a slight change when n is odd (don't use the middle two pieces when breaking it apart, and then swap those middle two pieces individually)

This ends up being approx T(N) = N/2 + 2*T(N/2), which is O(n log n)

Kudrjavets fejtoro

I think I have a solution with O(2n-2) and no additional memory. So it is faster for bigger values of n (n>=100).
It just goes straight forward to exchange only 2 values; it only needs to remember only value; which was just exchanged.

[code]
using System;

namespace Out_Shuffle
{
class Class1
{
static void Main(string[] args)
{
int [] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.Diagnostics.Debug.Assert(arr.Length % 2 == 0);
int n = arr.Length / 2;

System.Console.WriteLine(GetArrString(arr));

int swapCount = 0;
int aktIdx = 1; // start with 1 (counting from zero!)
int memIdx = -1; // -1 means not used
int memValue = 0; // contains the value of the mem
while(swapCount < ((2*n)-2))
{
int newIdx = GetNewIdxForThisIdx(aktIdx, n);

System.Console.Write(swapCount + ": aktIdx=" + aktIdx + ", newIdx=" + newIdx + ", ");
System.Console.WriteLine(GetArrString(arr));

if (memIdx < 0)
{
memValue = arr[aktIdx];
memIdx = aktIdx;
arr[aktIdx] = arr[newIdx];
arr[newIdx] = -1; // only for debug
aktIdx = newIdx; // no go further with the now free "newIdx" entry
}
else
{
if (newIdx == memIdx)
{
// now we need to insert the mem-value into the index
arr[aktIdx] = memValue;
memIdx = -1; // signal that the memed-value is free
aktIdx++;
}
else
{
// we can continue to swap...
int tmp = arr[newIdx];
arr[newIdx] = arr[aktIdx];
arr[aktIdx] = tmp;
aktIdx = newIdx;
}
}
swapCount++;
} // while
System.Console.WriteLine(GetArrString(arr));
}

static int GetNewIdxForThisIdx(int idx, int n)
{
System.Diagnostics.Debug.Assert(n > 0);
System.Diagnostics.Debug.Assert(idx >= 0);
System.Diagnostics.Debug.Assert(idx < (2*n));
// this method calculates the transformation from input to output indexes
if ((idx % 2) == 0)
{
int tmp = idx / 2;
return tmp;
}
else
{
int tmp = (idx-1) / 2;
return n + tmp;
}
}

static string GetArrString(int [] arr)
{
string s = "";
foreach(object o in arr)
{
s += o.ToString() + ",";
}
return s;
}
}
}
[/code]

I think I have a solution with O(2n-2) and no additional memory. So it is faster for bigger values of n (n>=100).
It just goes straight forward to exchange only 2 values; it only needs to remember only value; which was just exchanged.

[code]
using System;

namespace Out_Shuffle
{
class Class1
{
static void Main(string[] args)
{
int [] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.Diagnostics.Debug.Assert(arr.Length % 2 == 0);
int n = arr.Length / 2;

System.Console.WriteLine(GetArrString(arr));

int swapCount = 0;
int aktIdx = 1; // start with 1 (counting from zero!)
int memIdx = -1; // -1 means not used
int memValue = 0; // contains the value of the mem
while(swapCount < ((2*n)-2))
{
int newIdx = GetNewIdxForThisIdx(aktIdx, n);

System.Console.Write(swapCount + ": aktIdx=" + aktIdx + ", newIdx=" + newIdx + ", ");
System.Console.WriteLine(GetArrString(arr));

if (memIdx < 0)
{
memValue = arr[aktIdx];
memIdx = aktIdx;
arr[aktIdx] = arr[newIdx];
arr[newIdx] = -1; // only for debug
aktIdx = newIdx; // no go further with the now free "newIdx" entry
}
else
{
if (newIdx == memIdx)
{
// now we need to insert the mem-value into the index
arr[aktIdx] = memValue;
memIdx = -1; // signal that the memed-value is free
aktIdx++;
}
else
{
// we can continue to swap...
int tmp = arr[newIdx];
arr[newIdx] = arr[aktIdx];
arr[aktIdx] = tmp;
aktIdx = newIdx;
}
}
swapCount++;
} // while
System.Console.WriteLine(GetArrString(arr));
}

static int GetNewIdxForThisIdx(int idx, int n)
{
System.Diagnostics.Debug.Assert(n > 0);
System.Diagnostics.Debug.Assert(idx >= 0);
System.Diagnostics.Debug.Assert(idx < (2*n));
// this method calculates the transformation from input to output indexes
if ((idx % 2) == 0)
{
int tmp = idx / 2;
return tmp;
}
else
{
int tmp = (idx-1) / 2;
return n + tmp;
}
}

static string GetArrString(int [] arr)
{
string s = "";
foreach(object o in arr)
{
s += o.ToString() + ",";
}
return s;
}
}
}
[/code]

A little bit more explaination:

We assume n=4:
0 1 2 3 4 5 6 7 (Index in the array)
a0 a1 a2 a3 b0 b1 b2 b3 (Values)

a0 an b3 al already ok, so we start at a1:
Now we need to calculate the index which should be placed in index 1 => index 4

So we remember the value of a1 (index 1) in m, and replace index 1 with b0 (index 4)=>
a0 b0 a2 a3 -- b1 b2 b3 (-- means "free")

Now we try to find the correct index for the now free index 4 => index 2 (a2) and put the value into index 4 =>
a0 b0 -- a3 a2 b1 b2 b3

Now we repeat this step: Index 2 => a1 (this is stored in m) =>
a0 b0 a1 a3 a2 b1 b2 b3

Now our memory (m) is free and we continue with the next index: 3 and start with the same algo

a0 b0 a1 b1 a2 -- b2 b3 (m=a3)
=>
a0 b0 a1 b1 a2 b2 -- b3
=>
a0 b0 a1 b1 a2 b2 a3 b3 (from m)

Finished.

Greetings
Jochen

Upps... forget it... it does not work...

Greetings
Jochen

APL, J, and Gunnar Shuffle

i think sorting is not needed for these tables to be merged . only the position

I thought it would be best to have a go at this without looking at anyone elses.
This is what I came up with, which looks very similar to Dave Kongs, and to be honest I have read down the whole thread to see if anyone else has ended up with the same result.
In terms of swaps this appears to be O(n) - in fact it takes fewer than n swaps, as Dave mentioned above.

(oh it is coded with a loop to get a sample of numbers of values for the number of swaps, varying n, in case anyone wonders what the extra bit is for)

static void Main(string[] args)
{
int n=1024;
{
int [] data=new int[n];
int swaps=0;
for (int i=0;i<n;data[i]=i,i++);
int p=1;
while (p<(n+1)/2)
{
int p2=fp(p,n);
while (p!=p2)
{
int temp=data[p];
data[p]=data[p2];
data[p2]=temp;
swaps++;
p2=fp(p2,n);
}
while ((fp(data[p],n)==p) && (p<=(n+1)/2))
{
p++;
}
}
Console.WriteLine(n.ToString() + "Swaps : " + swaps.ToString());
}
Console.ReadLine();
}
static int fp(int i,int n)
{
if (i<((n+1) / 2))
{
return i*2;
}
else
{
return 2*i+1-n-(n % 2);
}
}

Well, actually that isn't coded with a loop, the previous version was and I forgot I had changed it to a declaration of 'n'
if you want the loop, change
int n=1024;
to something like
for(int n=10;n<6500010;n+=63488)

:-)

I wasn't much decsriptive explaining the logic
Assume two arrays
Below is logic explaination not the exact way the logic is to be implemented : The logic inmplementation will require swapping operations


(It has 0 memory reqts)
A = 1 , 3 , 5, 7 , 9, 11 , 13, 15

B = 2, 4 , 6, 8 , 10, 12, 14, 16

Creating Two Paired squares

1 3 5 7 9 11 13 15
2 4 6 8 10 12 14 16


Swap diagonally
Right First Row to Left Second Row
=>

1 2 5 6 9 10 13 14
3 4 7 8 11 12 15 16


--------------


Create 4 paired squares with the resultant

1 2 5 6 9 10 13 14
3 4 7 8 11 12 15 16

Last swapping was with n= 1 no
now swap with twice 2n = 2
two nos in the left most second row swap with the right most in first row

=>

1 2 3 4 9 10 11 12
5 6 7 8 13 14 15 16


-----------------

Create pairs of 8 (Square is just a analogy)

after swapping 2 * 2* n nos

1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16


--------------

arrays are sorted ----------alternate

This one I wrote is of 0(n) time and o(n/4) memory usage.


using System;

namespace Shuffle
{
/// <summary>
/// out-shuffle class.
/// Performs in N time O(N) and
/// N/4 memory usage O(N/4)
///
/// Input = 'a','b','c',....,'z','A','B','C',....,'Z'}
/// Output = {'a','A','b','B','c','C',....,'z','Z'};
/// </summary>
class Shuffle
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
char[] arr = new char[52];

//fill input data
for (int i=0; i<26; i++)
{
arr[i] = (char) ((int)'a' + i);
}

for (int i=26; i<52; i++)
{
arr[i] = (char) ((int)'A' + i-26);
}

int length = arr.Length;
if ( (length <= 2) || ( (length % 2) != 0) )
{
return;
}

//initialize circular queue. Avg size needed is N / 4
MyCircularQueue queue = new MyCircularQueue((length / 4)+ (length % 4));

int j=0;
int halfLength = length / 2;
for (int i = 1; i < length-1; i++)
{
if ((i % 2) == 1)
{
if (i < halfLength)
{
queue.insert(arr[i]);
}

arr[i] = arr[j + halfLength];
j++;
}
else
{
if (i < halfLength)
{
queue.insert(arr[i]);
}

arr[i] = queue.remove();
}

}

for (int i=0; i<length; i++)
{
Console.WriteLine(arr[i]);
}
}
}


/// <summary>
/// Basic circular queue
/// </summary>
class MyCircularQueue
{
char[] arr = null;
int start = -1;
int end = 0;
int MAX = 0;

/// <summary>
/// constructor
/// </summary>
/// <param name="size"></param>
public MyCircularQueue(int size)
{
arr = new char[size];
MAX = size;
}


/// <summary>
/// insert into queue
/// </summary>
/// <param name="c"></param>
public void insert(char c)
{
end = (end % MAX);

if (end == start)
{
throw new Exception("queue full");
}

arr[end] = c;
end++;

if (start == -1)
{
start = 0;
}
}

/// <summary>
/// remove from queue
/// </summary>
/// <returns></returns>
public char remove()
{
if ( (start == -1 ) )
{
throw new Exception("no elements");
}

char c = arr[start];

start++;
start = (start % MAX);

return c;
}
}
}

Anyone know how to do the perfect shuffe using Prolog?