人工知能的代数学(4) - エレファント・ビジュアライザー調査記録

プログラムの改造(2)

前回のプログラムに、互換に適用した場合のコメントを入れます。assert を入れようと思ったのですが、うまくできなかったのでコメントだけです。ChatGPT で assert とコメントを入れることができれば良いのですが、やり方がわからないので自分で入れます。ChatGPT で Python について聞くとかなり詳しく答えてもらえるのでそれを参考にしてやっています。ChatGPT と Python の練習にはなります(AI がやってくれる時代に必要かは疑問)。

def adjacent_transpositions_indices_list(perm):
    """
    隣接互換によって置換を整列したときのリストを返します。

    :param perm: 置換リスト
    :return: 交換したときの (i, j) の組のリスト
    """
    n = len(perm)
    transpositions_count = 0
    indices_list = [] # 交換したときの (i, j) の組のリスト
    # シンプルなバブルソートで隣接互換の数をカウント
    # (1-開始) 転倒数は元の転倒数
    for i in range(n):
        # (2-開始) perm[n-i] から後の転倒数は 0
        for j in range(1, n - i):
            # (3-開始) perm[0] から perm[j-1] までの中で perm[j-1] が最大
            if perm[j - 1] > perm[j]:
                # インデックス x と y を入れ替える互換のときここに来るのは
                # i = 0 のとき j = x + 1 から y の y - x 回
                # i = 1 から y - x - 1 のとき j = y - i の y - x - 1 回
                # 合計 2(y - x) - 1 回
                # (4-開始)
                inversions_before = count_inversions(perm)
                # 隣接する要素を交換
                perm[j - 1], perm[j] = perm[j], perm[j - 1]
                # 交換が発生したのでカウントを増やす
                transpositions_count += 1
                indices_list.append((i, j))
                # (4-終了) 交換によって転倒数は 1 減っている
                assert count_inversions(perm) == inversions_before - 1
            # (3-終了) perm[0] から perm[j] までの中で perm[j] が最大
            assert all(x < perm[j] for x in perm[:j])        
        # (2-終了-1) perm[0] から perm[n-i-1] までの中で perm[n-i-1] が最大
        assert all(x < perm[n-i-1] for x in perm[:n-i-1])        
        # (2-終了-2) perm[n-i-1] から後の転倒数は 0
        assert count_inversions(perm[n-i-1:]) == 0
    # (1-終了) perm[0] から後(全体)の転倒数は 0
    assert count_inversions(perm) == 0
    return indices_list

def adjacent_transpositions_test(n, x, y):
    """
    互換を隣接互換の積で表したときどうなるか調べます。

    :n: 置換の長さ
    :x, y: 交換するインデックス
    """
    perm = [k + 1 for k in range(n)]
    perm[x], perm[y] = perm[y], perm[x]

    # 転倒数を計算
    inversions = count_inversions(perm)

    # 隣接互換の数を計算
    transpositions_list = adjacent_transpositions_indices_list(perm[:])  # コピーを渡す
    transpositions_count = len(transpositions_list)
    # 結果を表示
    print("元の互換:", perm)
    print("転倒数:", inversions)
    print("交換したときの (i, j) の組のリスト:", transpositions_list)
    print("隣接互換の数:", transpositions_count)
    print("等しいかどうか:", inversions == transpositions_count)

# 例
adjacent_transpositions_test(10, 3, 8)
adjacent_transpositions_test(6, 0, 5)

結果 1

元の互換: [1, 2, 3, 9, 5, 6, 7, 8, 4, 10]
転倒数: 9
交換したときの (i, j) の組のリスト: [(0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 7), (2, 6), (3, 5), (4, 4)]
隣接互換の数: 9
等しいかどうか: True

結果 2

元の互換: [6, 2, 3, 4, 5, 1]
転倒数: 9
交換したときの (i, j) の組のリスト: [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 4), (2, 3), (3, 2), (4, 1)]
隣接互換の数: 9
等しいかどうか: True

互換のときの、交換が発生するときの条件を追加しました。結果 2 (最初と最後を交換した互換)の方がわかりやすいと思います。

交換が発生したときのコメントを追加しています。コメントに書いたように、インデックスが $x$ の要素とインデックスが $y$ の要素を交換した互換のとき、交換が発生する回数は $2(y - x) - 1$ 回ということがわかります。よって

互換にこのプログラムを適用すると得られる隣接互換の個数は奇数

となって、互換は奇数個の隣接互換の積で表されます。

隣接互換の積

ここからはコメントは書かず、説明を書くだけとします。

$\sigma$ を $X = \{1, 2, \cdots, n\}$ の置換とします。 $\mu$ を $k$ 個目と $k + 1$ 個目を入れ替える隣接互換とします。これを
$\mu = (1, 2, \cdots, k-1, k+1, k, k+1, \cdots, n)$
と書くことにします。

$\sigma\mu$ を
$\sigma\mu = (\sigma(1), \sigma(2), \cdots, \sigma(k-1), \sigma(k+1), \sigma(k), \sigma(k+2), \cdots, \sigma(n))$
とします(このような順序で置換を合成するとします)。

$\sigma = (\sigma(1), \sigma(2), \cdots, \sigma(k-1), \sigma(k), \sigma(k+1), \sigma(k+2), \cdots, \sigma(n))$
と
$\sigma\mu = (\sigma(1), \sigma(2), \cdots, \sigma(k-1), \sigma(k+1), \sigma(k), \sigma(k+2), \cdots, \sigma(n))$
にこのプログラムを適用するとどうなるかを考えます。