wu :: forums
« wu :: forums - CS: ARRAY ROTATION »

Welcome, Guest. Please Login or Register.
Nov 22nd, 2024, 11:38am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: SMQ, towr, william wu, Eigenray, Grimbal, Icarus, ThudnBlunder)
   CS: ARRAY ROTATION
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: CS: ARRAY ROTATION  (Read 2111 times)
S. Owen
Full Member
***





   


Gender: male
Posts: 221
CS: ARRAY ROTATION  
« on: Aug 1st, 2002, 9:05am »
Quote Quote Modify Modify

How about this solution?
 
First, reverse the order of the elements in the whole list:
{xn, xn-1, ..., x1}
 
Then reverse the sublist containing the last k-1 elements, and then also the sublist containing the other n-k+1 elements:
 
{xk, xk+1, ..., xn, x1, ..., xk-1}
 
To illustrate rotating a list of n=5 elements so that k=4 is first:
 
1 2 3 4 5
reverse list:
5 4 3 2 1
break into sublists and reverse:
5 4    3 2 1
4 5    1 2 3
 
Each reversal is clearly O(n) and the swapping requires some small constant amount of storage.
IP Logged
-D-
Guest

Email

Re: CS: ARRAY ROTATION  
« Reply #1 on: Aug 1st, 2002, 10:59am »
Quote Quote Modify Modify Remove Remove

Grrr... I was banging my head against the wall with mods and elements hopping around.  
 
This is like your string reversal answer... hrm...
-D-
IP Logged
yosenl
Guest

Email

Re: CS: ARRAY ROTATION  
« Reply #2 on: Aug 2nd, 2002, 3:19am »
Quote Quote Modify Modify Remove Remove

This problem can also be found in the book by 'Programming Pearls' by Jon Bentley, column 2. It is an excellent book about various facets of computer programming.
 
IP Logged
zameericle
Newbie
*





   
Email

Posts: 8
Re: CS: ARRAY ROTATION  
« Reply #3 on: Aug 5th, 2002, 3:23am »
Quote Quote Modify Modify

how about:
 
array: 0123456789
k: 5
you need a swap(i,k) function that can be done in O(1) memory as follows:
 
i = i XOR k
k = k XOR i
i = i XOR k
 
so to do the rotation the following code:
 
int i=0;
while( k < n )
{
   swap( a[i++], a[k++] );
}
IP Logged
S. Owen
Full Member
***





   


Gender: male
Posts: 221
Re: CS: ARRAY ROTATION  
« Reply #4 on: Aug 5th, 2002, 5:48am »
Quote Quote Modify Modify

This happens to work in the case where k = n/2, but try this for, say, k=6 here and you will not get the desired result.
IP Logged
zameericle
Newbie
*





   
Email

Posts: 8
Re: CS: ARRAY ROTATION  
« Reply #5 on: Aug 6th, 2002, 1:29am »
Quote Quote Modify Modify

oops..
 
what happens if you change the beginning offset to
 k = n - k + 1;  
 
that should fix the problem.
IP Logged
S. Owen
Full Member
***





   


Gender: male
Posts: 221
Re: CS: ARRAY ROTATION  
« Reply #6 on: Aug 6th, 2002, 5:30am »
Quote Quote Modify Modify

Try k=4:
7 8 9 3 4 5 6 0 1 2
or k=8:
3 4 5 6 7 8 0 1 2 9
 
I don't believe that you can get the desired result along these lines.
IP Logged
zameericle
Newbie
*





   
Email

Posts: 8
Re: CS: ARRAY ROTATION  
« Reply #7 on: Aug 6th, 2002, 8:24am »
Quote Quote Modify Modify

gah.. I give up!!!
 
It's tough to get off a current train of thought once you're on it...
IP Logged
Paul Hsieh
Guest

Email

Re: CS: ARRAY ROTATION  
« Reply #8 on: Aug 6th, 2002, 10:00pm »
Quote Quote Modify Modify Remove Remove

Hint: How long does it take to find the minimum element in this rotated list?
IP Logged
Paul Hsieh
Guest

Email

Re: CS: ARRAY ROTATION  
« Reply #9 on: Aug 6th, 2002, 10:46pm »
Quote Quote Modify Modify Remove Remove

Whoops! Answering the wrong question!  You have to differentiate the subjects a bit more I think.
 
Anyhow, the solution to this is:
 
Step 1:  Compute S = gcd (k, n)  (Euclid's algorithm, or Knuth's improvement -- whatever.)
 
Step 2:   Code:
int f(x, n, k) {
  return (x + n + k - 1) % n;
}

Step 3: Code:
for (i=0; i < S; i++) {
  x = i;
  temp = Array [x];
  for (j = f(x, n, k); j != i; j = f(x, n, k)) {
    Array [x] = Array [j];
    x = j;
  }
  Array [x] = temp;
}

The idea is that you are just pushing the array entries to their correct position in the disjoint contiguous rings { x, f(x), f2(x), f3(x), f4(x), ... } and realizing that there are gcd(n,k) such rings for any given (n,k).  There may be a faster way, but this is the way that occurs to me.
 
Now of course, you can argue that Step 1 alone is slower than O(n) (I don't know/remember if it is or not) by itself.  So to work around that, you can modify Step 3, to sort of compute the gcd() on the fly by noting it, then when i==1, the lowest value of j not equal to i within the inner most loop, will be equal to the gcd itself.
 
Hmmm ... if gcd() were slower than O(n), then the above described algorithm would be a faster way of computing it ... which is not bloody likely.  So just ignore that comment ... I assert that the Knuth algorithm for figuring out gcd(n, k) is at worst O(n)  Grin.
IP Logged
NoNamePlease
Guest

Email

Re: CS: ARRAY ROTATION  
« Reply #10 on: Nov 24th, 2003, 4:27pm »
Quote Quote Modify Modify Remove Remove

I think Paul Hsieh gave a similar solution, but this seems easier (Perl):
Code:

#!/usr/bin/perl -w
use strict;
 
my $N = $ARGV[0];
my $K = $ARGV[1];
 
$N = 10 unless defined $N;
$K = 3  unless defined $K;
 
my @a = (1..$N);
my $k;
my $tmp;
for (my ($i, $j, $l) = (0, 0, 0), $tmp = $a[0]; $i <$N-1; ++$i) {
    $k = $j + $K;
    $k -= $N if $k >= $N;
    if ($k == $l) {
 $a[$j] = $tmp;
 ++$j;
 $tmp = $a[$j];
 $l = $j;
    } else {
 $a[$j] = $a[$k];
 $j = $k;
    }
}
 
$a[$k] = $tmp;  
 
print "@a\n";
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: CS: ARRAY ROTATION  
« Reply #11 on: May 25th, 2004, 4:51pm »
Quote Quote Modify Modify

on Aug 6th, 2002, 5:30am, S. Owen wrote:
Try k=4:
7 8 9 3 4 5 6 0 1 2
or k=8:
3 4 5 6 7 8 0 1 2 9
 
I don't believe that you can get the desired result along these lines.

 
What about this:
 
void rot(int a[], int n, int k){
    int i;
    k = n-k;
    for( i = n-1 ; k<n ; i-- ){
      int tmp = a[i];
      a[i] = a[i-k];
      a[i-k] = tmp;
      if( i==k ){
          k = k - n%k;
          n = i;
      }
    }
}
 
[corrected BAD code]
« Last Edit: May 27th, 2004, 3:07pm by Grimbal » IP Logged
Leo Broukhis
Senior Riddler
****





   


Gender: male
Posts: 459
Re: CS: ARRAY ROTATION  
« Reply #12 on: May 26th, 2004, 4:21pm »
Quote Quote Modify Modify

on May 25th, 2004, 4:51pm, grimbal wrote:

 
What about this:
 
 a[i] ^= a[i-k] ^= a[i] ^= a[i-k];
 

 
This is BAD. There are two assignments to a[ i ] without a sequence point which means the result is undefined.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: CS: ARRAY ROTATION  
« Reply #13 on: May 26th, 2004, 7:34pm »
Quote Quote Modify Modify

Well, it could have been worse:
Code:
a[i] = (a[i]^a[i-k])^(a[i-k]=a[i]);

 Grin
 
Regarding the x ^= y ^= x ^= y, I know it is bad.  I just wanted to make the code as succint as possible.  Every serious C programmer will recognize a swap.  Smiley It is bad because it does unnecessary operations.  It is also undefined for C, because there are no sequence points to guarantee the order of the assignations.  But I read somewhere that this might be changed in a coming revision of the C Standard.  It would show that it is not the program that is wrong, but the C language.  Wink
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: CS: ARRAY ROTATION  
« Reply #14 on: May 28th, 2004, 7:52am »
Quote Quote Modify Modify

Same idea, a little simpler
Code:
void rot(int a[], int n, int k){
    int i = n;
    while( k || (k=n%i, n=i, k) ){
      int t = a[--i];
      a[i] = a[--k];
      a[k] = t;
    }
}
« Last Edit: May 28th, 2004, 7:53am by Grimbal » IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: CS: ARRAY ROTATION  
« Reply #15 on: Sep 8th, 2004, 8:22am »
Quote Quote Modify Modify

This is similar to Paul Hsieh's solution without the need for computing the gcd of (n,k).
 
Basically the permutation is f(i) = i + k (mod n)
The permutation is composed of rings. Each ring has a min element called the seed. One property of this set of seeds is:
Start following the ring for each seed in ascending order of their values. If we just completed the ring of the seed of value i and not all elements of the array have been touched, then i+1 is the next seed.
 
I don't remember where I read this. I guess the proof of this should not be very difficult.
 
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