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?

Improve this question
$\endgroup$
7
  • $\begingroup$ Can you discover something about the cycles that for with that permutation for various $n$? $\endgroup$
    – ratchet freak
    Jun 30, 2017 at 15:47
  • $\begingroup$ I didn't quite catch you - "that for with that permutation"? $\endgroup$
    – Erric
    Jun 30, 2017 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, 2017 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, 2017 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, 2017 at 19:34

0

Reset to default

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.