On Jul 3, 2:01 pm, jalaj jaiswal <jalaj.jaiswa...@gmail.com> wrote: > Let an array contain values : a1,a2,... ,an, b1,b2,..., bn Write a program > to change this array to : a1,b1,a2,b2, ..., an,bn in O(n) time and in O(1) > space. > > i did it by shiftng of elements which is not much efficient.. any better way > ?
This is a tricky problem. Here is link to a very elegant solution. It uses some basic number theory to find permutation cycles. http://arxiv.org/pdf/0805.1598v1 Here is code that's tested for n up to 1,000,000. Not this actually produces b1,a1,b2,a2, .... But you could easily make a final pass to swap pairs. #include <stdio.h> void print(char *msg, int *a, int i, int j) { printf("%s: ", msg); while (i < j) printf(" %d", a[i++]); printf("\n"); } // Swap a[i] and a[j]. void swap(int *a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } // Reverse a[i..j) void reverse(int *a, int i, int j) { while (i < j) swap(a, i++, --j); } // Rotate a[i..j) left by m positions. void rotate_left(int *a, int i, int j, int m) { reverse(a, i, i + m); reverse(a, i + m, j); reverse(a, i, j); } // Rotate a[i..j) right by m positions. void rotate_right(int *a, int i, int j, int m) { rotate_left(a, i, j, j - i - m); } // Find index mapping: Shuffle(a[i]) = a[imap(i)] int imap(int i, int n) { return (i & 1) ? i / 2 : i / 2 + n; } // Shuffle a[0..2m) where 2m = 3^k - 1 void shuffle3k(int *a, int m, int k) { int i, p0, p, q, t; for (i = 0, p0 = 0; i < k; i++, p0 = (3 * p0) + 2) { t = a[p0]; for (p = p0, q = imap(p, m); q != p0; p = q, q = imap(q, m)) { a[p] = a[q]; } a[p] = t; } } // Find k and m such that 2m = 3^k - 1 <= 2n < 3^(k+1) - 1 void get_m(int n, int *k_ret, int *m_ret) { int k, p, q; for (k = -1, p = 0, q = 1; q - 1 <= 2 * n; k++, p = q, q *= 3) /* skip */ ; *k_ret = k; *m_ret = (p - 1) / 2; } // Do a perfect shuffle on a, which has 2n elements. void shuffle(int *a, int n) { int k, m, i; i = 0; do { get_m(n, &k, &m); rotate_right(a, i + m, i + m + n, m); shuffle3k(a + i, m, k); i += 2 * m; n -= m; } while (n > 0); } int main(void) { int a[1000000]; int i, n; for (n = 1; n <= sizeof a / sizeof a[0] / 2; n++) { if (n % 1000 == 0) fprintf(stderr, "."); for (i = 0; i < n; i++) { a[i] = i + 1; a[i + n] = i + 1 + 1000; } //print("initial", a, 0, 2 * n); shuffle(a, n); for (i = 0; i < n; i++) { if (a[2 * i] != i + 1 + 1000 || a[2 * i + 1] != i + 1) { print("error", a, 0, 2 * n); return 1; } } //print("result", a, 0, 2 * n); } return 0; } -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
