Perfect Shuffle Algorithm

In-shuffle Algorithm

initial deck:       1 2 3 4 5 6 7 8
shuffled deck:      5 1 6 2 7 3 8 4

suppose i is the index of element in the original array, j is the index of that element in the new array.

We can easily get the formation: i, j starts with 1

j= 2*i mod (2*n+1)

Reference papaer:

[A Simple In-Place Algorithm for In-Shuffle](http://att.newsmth.net/att.php?p.1032.47005.1743.pdf)

Explanation:

A = [1, 2, 3, 4, 5, 6, ...,n, n+1, n+2, n+3, n+4,...,2*n]

Find 2*m = 3^k-1 such that 3^k<= 2n < 3^(k+1)

[1, 2, 3,..., m, m+1, m+2,..., n,    n+1, n+2, n+3,..., n+m, n+m+1,..., 2*n]
                  |                                      |
                  |....... Right shift m step ...........|

[1, 2, 3,..., m, n+1, n+2,....., n+m,      m+1, m+2,..., n,  n+m+1,..., 2*n]

do for remaining [m+1, m+2,..., n, n+m+1,..., 2*n]

Out shuffle:

Given a 2n size array [a1, a2, a3, a4,..,an, b1, b2, b3,...,bn] shuffle it in place to [a1, b1, a2, b2,...,an, bn].

Here In place means O(n) time complexity and O(1) space complexity.

initial deck:       0 1 2 3 4 5 6 7
shuffled deck:      0 4 1 5 2 6 3 7

Analysis

suppose i is the index of element in the original array, j is the index of that element in the new array. We can easily get the formation:

j=
F(i)=2*i          if i<n 
     2*(i-n)+1    if i>=n

start from any index, we keep applying the function F(i) and We get the sequence of index by shifting which we can arrange all the element in this sequence from original position to the new array position in O(1) space complexity.

Implementation

public void shuffle(int[] origin){
    if(origin==null || origin.length<=2) return;
    int n=origin.length/2;
    boolean[] visited=new boolean[origin.length];
    for(int i=0;i<2*n;i++){
      if(!visited[i]) cycle(i,origin,visited,n);
    }
}

public void cycle(int start, int[] arr, boolean[] visited, int n){
    visited[start]=true;
    int i=start<n?2*start:(2*(start-n)+1);//Function 'F'
    int prevalue=arr[start];
    while(i!=start){
        visited[i]=true;
        int tmp=arr[i];
        arr[i]=prevalue;
        prevalue=tmp;
        i=i<n?2*i:(2*(i-n)+1);
    }
    arr[i]=prevalue;
  }

def shuffle(A):
    N = len(A)/2
    movetoidx = lambda x: 2*x if x<N else 2*(x-N)+1
    for i in range(N-2):
        p = i
        prev = A[p]
        while movetoidx(p) != i:
            A[movetoidx(p)], prev = prev, A[movetoidx(p)]
            p = movetoidx(p)
        A[movetoidx(p)], prev = prev, A[movetoidx(p)]
    return A

def p(N):
    movetoidx = lambda x: 2*(x-N) if x>=N else (2*x+1)
    visited = set()
    ans = []
    for i in range(2*N):
        if i in visited:
            continue
        tmp = [i]
        p = i
        while movetoidx(p)!=i:
            tmp.append(movetoidx(p))
            p = movetoidx(p)
        if len(tmp)>1:
            ans.append(tmp[0])
        visited.update(tmp)
    return ans