フィッシャー・イェーツのシャッフル

長さ N の配列 arr = [ 0, 1, 2, ... (N-1) ] をシャッフルしたとき、どの要素から c = arr[c]; というように辿っていっても巡回する。
　
source:

function Shuffle(arr) {
    for (let i = arr.length - 1; 0 < i; i--) {
        let j = Math.floor(Math.random() * (i + 1));
        let wk = arr[i];
        arr[i] = arr[j];
        arr[j] = wk;
    }
}

function ShowRings(arr) {
    let b = Array(arr.length).fill(true);
    for (let i = 0; i < arr.length; i++) {
        if (b[i]) {
            let c = i;
            let a = [];
            do {
                a.push(c);
                b[c] = false;
                c = arr[c];
            }
            while (c != i);
            
            let s = "+--> " + a.join(" --> ") + " --+";
            console.log(s);
            console.log("|" + " ".repeat(s.length - 2) + "|");
            console.log("+" + "-".repeat(s.length - 2) + "+");
            console.log();
        }
    }
}

let N = 30;
let arr = [...Array(N).keys()];

Shuffle(arr);

console.log("[ " + arr.join(", ") + " ]");
console.log();

ShowRings(arr);

outputs:

[ 4, 10, 19, 13, 8, 6, 12, 29, 17, 26, 28, 21, 1, 18, 0, 23, 27, 15, 7, 9, 2, 24, 22, 3, 20, 11, 16, 25, 5, 14 ]

+--> 0 --> 4 --> 8 --> 17 --> 15 --> 23 --> 3 --> 13 --> 18 --> 7 --> 29 --> 14 --+
|                                                                                 |
+---------------------------------------------------------------------------------+

+--> 1 --> 10 --> 28 --> 5 --> 6 --> 12 --+
|                                         |
+-----------------------------------------+

+--> 2 --> 19 --> 9 --> 26 --> 16 --> 27 --> 25 --> 11 --> 21 --> 24 --> 20 --+
|                                                                             |
+-----------------------------------------------------------------------------+

+--> 22 --+
|         |
+---------+

[ 20, 28, 13, 17, 6, 1, 14, 7, 26, 27, 12, 4, 23, 2, 22, 15, 5, 19, 24, 11, 21, 10, 29, 3, 8, 18, 16, 9, 25, 0 ]

+--> 0 --> 20 --> 21 --> 10 --> 12 --> 23 --> 3 --> 17 --> 19 --> 11 --> 4 --> 6 --> 14 --> 22 --> 29 --+
|                                                                                                       |
+-------------------------------------------------------------------------------------------------------+

+--> 1 --> 28 --> 25 --> 18 --> 24 --> 8 --> 26 --> 16 --> 5 --+
|                                                              |
+--------------------------------------------------------------+

+--> 2 --> 13 --+
|               |
+---------------+

+--> 7 --+
|        |
+--------+

+--> 9 --> 27 --+
|               |
+---------------+

+--> 15 --+
|         |
+---------+

[ 5, 2, 12, 13, 16, 29, 28, 14, 9, 6, 24, 20, 3, 19, 4, 11, 21, 22, 8, 26, 25, 1, 23, 27, 10, 0, 18, 15, 7, 17 ]

+--> 0 --> 5 --> 29 --> 17 --> 22 --> 23 --> 27 --> 15 --> 11 --> 20 --> 25 --+
|                                                                             |
+-----------------------------------------------------------------------------+

+--> 1 --> 2 --> 12 --> 3 --> 13 --> 19 --> 26 --> 18 --> 8 --> 9 --> 6 --> 28 --> 7 --> 14 --> 4 --> 16 --> 21 --+
|                                                                                                                 |
+-----------------------------------------------------------------------------------------------------------------+

+--> 10 --> 24 --+
|                |
+----------------+

　
...となるのですが、シャッフルをちょっとだけ変えると

<<<        let j = Math.floor(Math.random() * (i + 1));
>>>        let j = Math.floor(Math.random() * i);

source:

function Shuffle(arr) {
    for (let i = arr.length - 1; 0 < i; i--) {
        let j = Math.floor(Math.random() * i);
        let wk = arr[i];
        arr[i] = arr[j];
        arr[j] = wk;
    }
}

function ShowRings(arr) {
    let b = Array(arr.length).fill(true);
    for (let i = 0; i < arr.length; i++) {
        if (b[i]) {
            let c = i;
            let a = [];
            do {
                a.push(c);
                b[c] = false;
                c = arr[c];
            }
            while (c != i);
            
            let s = "+--> " + a.join(" --> ") + " --+";
            console.log(s);
            console.log("|" + " ".repeat(s.length - 2) + "|");
            console.log("+" + "-".repeat(s.length - 2) + "+");
            console.log();
        }
    }
}

let N = 30;
let arr = [...Array(N).keys()];

Shuffle(arr);

console.log("[ " + arr.join(", ") + " ]");
console.log();

ShowRings(arr);

outputs:

[ 5, 25, 23, 4, 22, 12, 8, 9, 26, 19, 14, 10, 29, 27, 6, 21, 13, 11, 24, 28, 1, 16, 0, 17, 15, 7, 3, 20, 2, 18 ]

+--> 0 --> 5 --> 12 --> 29 --> 18 --> 24 --> 15 --> 21 --> 16 --> 13 --> 27 --> 20 --> 1 --> 25 --> 7 --> 9 --> 19 --> 28 --> 2 --> 23 --> 17 --> 11 --> 10 --> 14 --> 6 --> 8 --> 26 --> 3 --> 4 --> 22 --+
|                                                                                                                                                                                                          |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

[ 25, 11, 28, 6, 17, 1, 13, 19, 18, 12, 15, 10, 26, 20, 22, 23, 14, 24, 0, 21, 27, 3, 9, 29, 5, 4, 2, 8, 7, 16 ]

+--> 0 --> 25 --> 4 --> 17 --> 24 --> 5 --> 1 --> 11 --> 10 --> 15 --> 23 --> 29 --> 16 --> 14 --> 22 --> 9 --> 12 --> 26 --> 2 --> 28 --> 7 --> 19 --> 21 --> 3 --> 6 --> 13 --> 20 --> 27 --> 8 --> 18 --+
|                                                                                                                                                                                                          |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

[ 7, 28, 8, 22, 24, 0, 5, 16, 29, 25, 21, 10, 27, 12, 13, 2, 17, 23, 26, 9, 15, 3, 4, 11, 20, 1, 14, 6, 18, 19 ]

+--> 0 --> 7 --> 16 --> 17 --> 23 --> 11 --> 10 --> 21 --> 3 --> 22 --> 4 --> 24 --> 20 --> 15 --> 2 --> 8 --> 29 --> 19 --> 9 --> 25 --> 1 --> 28 --> 18 --> 26 --> 14 --> 13 --> 12 --> 27 --> 6 --> 5 --+
|                                                                                                                                                                                                          |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

というように、ひとつの輪(円順列？)になる。
このアルゴリズムなんていうのかしら...