Author |
Topic: CS: ARRAY ROTATION (Read 2111 times) |
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
CS: ARRAY ROTATION
« on: Aug 1st, 2002, 9:05am » |
Quote 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
|
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
|
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
Posts: 8
|
|
Re: CS: ARRAY ROTATION
« Reply #3 on: Aug 5th, 2002, 3:23am » |
Quote 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:
Posts: 221
|
|
Re: CS: ARRAY ROTATION
« Reply #4 on: Aug 5th, 2002, 5:48am » |
Quote 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
Posts: 8
|
|
Re: CS: ARRAY ROTATION
« Reply #5 on: Aug 6th, 2002, 1:29am » |
Quote 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:
Posts: 221
|
|
Re: CS: ARRAY ROTATION
« Reply #6 on: Aug 6th, 2002, 5:30am » |
Quote 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
Posts: 8
|
|
Re: CS: ARRAY ROTATION
« Reply #7 on: Aug 6th, 2002, 8:24am » |
Quote 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
|
Hint: How long does it take to find the minimum element in this rotated list?
|
|
IP Logged |
|
|
|
Paul Hsieh
Guest
|
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) .
|
|
IP Logged |
|
|
|
NoNamePlease
Guest
|
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:
Posts: 7527
|
|
Re: CS: ARRAY ROTATION
« Reply #11 on: May 25th, 2004, 4:51pm » |
Quote 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:
Posts: 459
|
|
Re: CS: ARRAY ROTATION
« Reply #12 on: May 26th, 2004, 4:21pm » |
Quote 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:
Posts: 7527
|
|
Re: CS: ARRAY ROTATION
« Reply #13 on: May 26th, 2004, 7:34pm » |
Quote Modify
|
Well, it could have been worse: Code:a[i] = (a[i]^a[i-k])^(a[i-k]=a[i]); |
| 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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: CS: ARRAY ROTATION
« Reply #14 on: May 28th, 2004, 7:52am » |
Quote 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:
Posts: 1321
|
|
Re: CS: ARRAY ROTATION
« Reply #15 on: Sep 8th, 2004, 8:22am » |
Quote 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 |
|
|
|
|