wu :: forums - Print Page


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

        riddles >> cs >> riffle shuffling an array
        
(Message started by: inexorable on Jul 15^th, 2007, 9:46pm)

Title: riffle shuffling an array
Post by inexorable on Jul 15^th, 2007, 9:46pm

Given an array with 2n elements a[1], a[2], a[3] .....a[n], ..a[2n]. give an algorithm to rearrange it as a[1], a[n+1], a[2], a[n+2], a[3], a[n+3]....a[n], a[2n] without using extra space in O(n) time?

Title: Re: riffle shuffling an array
Post by towr on Jul 15^th, 2007, 11:54pm

It helps a lot if n is a power of 2.
[hide]in which case you can swap [n/2+1..n] with [n+1..3n/2], then repeat the process for both halves of the array until you reach n=1[/hide]

Title: Re: riffle shuffling an array
Post by Aryabhatta on Jul 16^th, 2007, 11:35am

Already on this site:

Rearrange Array (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1094241218)

and

Shuffle Deck of cards (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1084733627)