119 完美洗牌问题（1）
Table of Contents

ac

序号 1 2 3 4 5 6 7 8
原始 a1 a2 a3 a4 b1 b2 b3 b4
洗牌后 b1 a1 b2 a2 b3 a3 b4 a4 
a1：1 -> 2
a2：2 -> 4
a3：3 -> 6
a4：4 -> 8
b1：5 -> 1
b2：6 -> 3
b3：7 -> 5
b4：8 -> 7

前一半位置i 变成2 * i
后一半位置i 便成(i - n/2) * 2 -1 即 2*i - n - 1
或者 (2 * i) % (n + 1)

环形思路

从1出发的环
【1】 2 4 8 7 5 1
还剩下从3出发的环
【3】 6 3

论文 《A Simple In-Place Algorithm for In-Shuffle》,结论

2*n = 3^k-1这种长度的数组，恰好只有k个环，且每个环的起始位置分别是1,3,9，…3^(k-1)

若2n != 3^k-1，则总可以找到最大的整数m，使得m < n，并且2m =（3^k-1）。我们的做法是使用循环左移算法将[m+1……n]之间的元素移动到m+n之后，将[1……m] 和[n+1……n+m]合并成为一个长度为2*m的数组进行环操作，这个2m数组是可以被完整移动的，我们直接找到所有的环，进行环操作,如此递归

参考博文：https://blog.csdn.net/sunnyyoona/article/details/43795243

实际例子：

序号 1 2 3 4 5 6 7 8 9 10 11 12
原始 a1 a2 a3 a4 a5 a6 b1 b2 b3 b4 b5 b6
第一次移动 a1 a2 a3 a4 b1 b2 b3 b4 a5 a6 b5 b6
前8个洗牌好 b1 a1 b2 a2 b3 a3 b4 a4 a5 a6 b5 b6
再移动一次 b1 a1 b2 a2 b3 a3 b4 a4 a5 b5 a6 b6
再洗好2个 b1 a1 b2 a2 b3 a3 b4 a4 b5 a5 a6 b6
最好剩下两个洗好 ｜ b1 a1 b2 a2 b3 a3 b4 a4 b5 a5 b6 a6

ac代码

【1】 2 4 8 7 5 1

1 2 3 4 5 6 7 8
5 1   2 7   8 4

【3】 6 3

1 2 3 4 5 6 7 8
    6     3

1 2 3 4 7 8 9 10
7 1 8 2 9 3 10 4

运行时间：2198ms，占用内存：114620k

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }

        // 自测
//        int n = 10000;
//        int[] arr = new int[n];
//        for(int i=0;i<n;i++){
//            arr[i] = i +1;
//        }

        perfectShuffle(arr, n);
        // print
        for(int i=0;i<n-1;i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println(arr[n-1]);
    }

    static void reverse(int[] chars, int l, int r) {
        int temp;
        while(l < r) {
            temp = chars[l];
            chars[l] = chars[r];
            chars[r] = temp;
            l++;
            r--;
        }
    }

    static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    static void cycle(int[] arr, int startIndex, int n, int firstPos){
        int pre = arr[startIndex + firstPos - 1];
        int firstIndex = firstPos;
        int next = (2 * firstIndex) % (2*n + 1);
        while (next != firstPos){
//            System.out.print(next + " ");
//            swap(arr, startIndex + firstIndex - 1, startIndex + next - 1);
            int tmp =  arr[startIndex + next - 1];
            arr[startIndex + next - 1] = pre;
            pre = tmp;
            next = (2 * next) % (2*n + 1);
        }
        arr[startIndex + firstPos - 1] = pre;
    }

    static void move(int[] arr, int startIndex, int n, int m){
        // startIndex   startIndex + m  startIndex + n
        // startIndex + n   startIndex + n + n - m startIndex + 2n
        reverse(arr, startIndex + m, startIndex + n - 1);
        reverse(arr, startIndex + n, startIndex + n + m - 1);
        reverse(arr, startIndex + m, startIndex + n + m - 1);
    }

    static void perfectShuffle(int[] arr, int len){
        int n = len / 2;
        int startIndex = 0;
        while (n >= 1){
            int k = 0;
            int r = 1;
            while (r - 1 <= 2*n){
                r = r * 3;
                k++;
                if(r-1 == 2*n){
                    break;
                }
            }
            if(r - 1 == 2 * n){ // 刚刚好 3^k - 1
                // 再cycle, 开始位置依次是 3^(k-1)
                int firPost = 1;
                for(int i=0;i<k;i++) {
                    cycle(arr, startIndex, (r - 1) / 2, firPost);
                    firPost *= 3;
                }
                break;
            }else {
                int m = (r/ 3 - 1) / 2;
                k--;
                // 字符串内块移动，三步翻转即可
                move(arr, startIndex, n, m);
                // 再cycle, 开始位置依次是 3^(k-1)
                int firPost = 1;
                for(int i=0;i<k;i++) {
                    cycle(arr, startIndex, m, firPost);
                    firPost *= 3;
                }
                // 最后递归
                startIndex = startIndex + r/3 - 1;
                int left = 2*n - 2*m;
                n = left / 2;
            }
        }
    }

}
/*
12
1 2 3 4 5 6 7 8 9 10 11 12

18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
*/