0
$\begingroup$

If A is an array with the following elements: $$ a_1,a_2,...,a_n,b_1,b_2,...,b_n $$

How to shuffle A to form: $$ a_1,b_1,a_2,b_2,...,a_n,b_n $$

with minimal swaps and using no additional space?

I read this answer and wrote the following code:

def shuffle(a,left,right):
if right - left>=4:
    half = (right - left)/2
    for i in xrange(half/2):
        tmp = a[left + half + i]
        a[left + half+i] = a[left + half/2 + i]
        a[left + half/2 + i] = tmp
    shuffle(a,left,left + (right - left)/2)
    shuffle(a,left + (right - left)/2, right)

a = ['a1','a2','a3','a4',
     'b1','b2','b3','b4']
shuffle(a,0,len(a))

This gives an algorithm with O(nLog(n)) swaps. But I realized that this works only when n = 2k for some integer k. Is there a minor tweak that one could make to get the same complexity for arbitrary n?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Can you discover something about the cycles that for with that permutation for various $n$? $\endgroup$ – ratchet freak Jun 30 '17 at 15:47
  • $\begingroup$ I didn't quite catch you - "that for with that permutation"? $\endgroup$ – Erric Jun 30 '17 at 17:17
  • $\begingroup$ $a2$ moves to index 3 which replaces $a3$ which moves to index 5 which replaces $a5$ which moves to index 9, eventually that will loop back to index 2. That's a cycle, Investigate how the cycles evolve as n increases. $\endgroup$ – ratchet freak Jun 30 '17 at 17:54
  • $\begingroup$ Consider the permutation $\sigma: \{1,2,\dots,2n\} \to \{1,2,\dots,2n\}$ that you're trying to implement, i.e., $\sigma(i)=2i-1$ for $i\le n$ and $\sigma(i)= 2(i-n)$ for $i>n$. Can you characterize its cycle structure? How many cycles does it have of each possible length? Then use the fact that you can permute a cycle of length $\ell$ using $\ell-1$ swaps, and sum over all the cycles. See cs.stackexchange.com/q/71154/755. $\endgroup$ – D.W.♦ Jun 30 '17 at 19:25
  • $\begingroup$ That link already describes how to handle the case of arbitrary $n$. I'm not sure what your question is, exactly -- it seems like it is already answered by the answers over there. $\endgroup$ – D.W.♦ Jun 30 '17 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.