wu :: forums
« wu :: forums - riffle shuffling an array »
Welcome, Guest. Please Login or Register.
Nov 28th, 2024, 6:38am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs (Moderators: Icarus, Grimbal, william wu, SMQ, ThudnBlunder, Eigenray, towr)
   riffle shuffling an array		 « Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: riffle shuffling an array  (Read 508 times)
inexorable
Full Member
***





   


Posts: 211
riffle shuffling an array  
« on: Jul 15th, 2007, 9:46pm »		 Quote Quote Modify Modify
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?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: riffle shuffling an array  
« Reply #1 on: Jul 15th, 2007, 11:54pm »		 Quote Quote Modify Modify
It helps a lot if n is a power of 2.
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
IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
Aryabhatta
Uberpuzzler
*****






   


Gender: male
 Posts: 1321
Re: riffle shuffling an array  
« Reply #2 on: Jul 16th, 2007, 11:35am »		 Quote Quote Modify Modify
Already on this site:
 
Rearrange Array
 
and
 
Shuffle Deck of cards
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board