行と列の入れ替えに関する問題その2 - ヤマカサのプログラミング勉強日記

行列の列の入れ替えと行の入れ替えて得られる行列について

yamakasa3.hatenablog.com

上記の記事の行列の操作によって得られる行列の要素が元の行列の要素の位置と一致する期待値を考えていたんですが、良く分かりませんでした。

$1$	$2$	$\cdots$	$n$
$n+1$	$n+2$	$\cdots$	$2n$
$\vdots$	$\vdots$	$\ddots$	$\vdots$
$n(n-1) + 1$	$n(n-1) +2$	$\cdots$	$n^2$

$1$ 次元配列の場合

$1$ 次元配列の場合、最大値を $n$ とすると、配列 $a$ は

$a = [ 1, 2, \cdots , n]$

となり、この配列の順列は、 $n!$ 通りあります。また、元の位置に存在する番号の合計は $n!$ となるので、求める期待値は $E$ は

$E = \dfrac{n!}{n!} = 1$

となります。

また、ある要素が元の位置に存在する確率は、 $\dfrac{1}{n}$ であり、全体で $n$ 個の数字が存在するので、期待値の線形性から、

$E = n \times \dfrac{1}{n} = 1$

となります。

行列の場合

先程の記事にあるとおり、行の入れ替えと列の入れ替えによって得られる行列は、 $(n!)^2$ 通りあります。

操作によって得られる行列の要素が元の位置にあるものの個数を求めるコード

public class Test {
    static int [][]A;
    static int n;
    static int cnt = 0;
    static int [][]row;
    static int [][]col;
    public static void main(String[] args) {
        n = 3;
        A = new int[n][n];

        row = new int[n][n];
        col = new int[n][n];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                row[i - 1][j - 1] = i + n * (j - 1);
                col[i - 1][j - 1] = j + n * (i - 1);
            }
        }

        int cnt = 1;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                A[i][j] = cnt;
                cnt ++;
            }
        }

        int l = factorial(n);
        int [][]ary = new  int[l][n];

        int []a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = i;
        }
        perm(0, a, new boolean [n + 1], ary);

        int sum = 0;
        for(int i = 0; i < l; i++) {
            swapR(ary[i]);
            copyCol();
            for(int j = 0; j < l; j++) {
                swapC(ary[j]);
                sum += count(A);
                //disp(A);
            }
        }
        System.out.println(sum);


    }
    static void copyCol() {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                col[i][j] = A[i][j];
            }
        }
    }

    static void swapR(int []a) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j  <n; j++) {
                A[j][i] = row[a[i] - 1][j];
            }
        }
    }

    static void swapC(int []a) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j  < n; j++) {
                A[i][j] = col[a[i] - 1][j];
            }
        }
    }

    static  int factorial(int n) {
        if(n == 1) {
            return n;
        }else {
            return n * factorial(n - 1);
        }
    }
    static void disp(int [][]A) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                System.out.print(A[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    static int count(int [][]A) {
        int cnt = 0;
        int k = 1;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(A[i][j] == k) {
                    cnt ++;
                }
                k ++;
            }
        }
        return cnt;
    }
    static void perm(int n, int[] a, boolean[] flag, int[][] ary) {
        if(n == a.length) {
            for(int i = 0; i < ary[0].length; i++) {
                ary[cnt][i] = a[i];
            }
            cnt ++;
            return;
        }
        for(int i = 1; i <= a.length; i++) {
            if(flag[i]) continue;
            a[n] = i;
            flag[i] = true;
            perm(n + 1, a, flag, ary);
            flag[i] = false;
        }
    }
}