wu :: forums - Print Page


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

        riddles >> cs >> CS: ARRAY ROTATION
        
(Message started by: srowen on Aug 1^st, 2002, 9:05am)

Title: CS: ARRAY ROTATION
Post by srowen on Aug 1^st, 2002, 9:05am

How about this solution?

First, reverse the order of the elements in the whole list:
{x_n, x_n-1, ..., x₁}

Then reverse the sublist containing the last k-1 elements, and then also the sublist containing the other n-k+1 elements:

{x_k, x_k+1, ..., x_n, x₁, ..., x_k-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.

Title: Re: CS: ARRAY ROTATION
Post by -D- on Aug 1^st, 2002, 10:59am

Grrr... I was banging my head against the wall with mods and elements hopping around.

This is like your string reversal answer... hrm...
-D-

Title: Re: CS: ARRAY ROTATION
Post by yosenl on Aug 2^nd, 2002, 3:19am

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.

Title: Re: CS: ARRAY ROTATION
Post by zameericle on Aug 5^th, 2002, 3:23am

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++] );
}

Title: Re: CS: ARRAY ROTATION
Post by srowen on Aug 5^th, 2002, 5:48am

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.

Title: Re: CS: ARRAY ROTATION
Post by zameericle on Aug 6^th, 2002, 1:29am

oops..

what happens if you change the beginning offset to
k = n - k + 1;

that should fix the problem.

Title: Re: CS: ARRAY ROTATION
Post by S. Owen on Aug 6^th, 2002, 5:30am

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.

Title: Re: CS: ARRAY ROTATION
Post by zameericle on Aug 6^th, 2002, 8:24am

gah.. I give up!!!

It's tough to get off a current train of thought once you're on it...

Title: Re: CS: ARRAY ROTATION
Post by Paul Hsieh on Aug 6^th, 2002, 10:00pm

Hint: How long does it take to find the minimum element in this rotated list?

Title: Re: CS: ARRAY ROTATION
Post by Paul Hsieh on Aug 6^th, 2002, 10:46pm

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), f²(x), f³(x), f⁴(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) ;D.

Title: Re: CS: ARRAY ROTATION
Post by NoNamePlease on Nov 24^th, 2003, 4:27pm

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";

Title: Re: CS: ARRAY ROTATION
Post by grimbal on May 25^th, 2004, 4:51pm

on 08/06/02 at 05:30:18, 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]

Title: Re: CS: ARRAY ROTATION
Post by Leonid Broukhis on May 26^th, 2004, 4:21pm

on 05/25/04 at 16:51:51, 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.

Title: Re: CS: ARRAY ROTATION
Post by grimbal on May 26^th, 2004, 7:34pm

Well, it could have been worse:

Code:

a[i] = (a[i]^a[i-k])^(a[i-k]=a[i]);

;D

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. :) 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. ;)

Title: Re: CS: ARRAY ROTATION
Post by grimbal on May 28^th, 2004, 7:52am

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;
}
}

Title: Re: CS: ARRAY ROTATION
Post by Aryabhatta on Sep 8^th, 2004, 8:22am

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.