置換の分類(2)
ChatGPT で以下のように入力しました。
置換を隣接互換の積に分解するプログラムを書いてください
これは正しいプログラムを得ることができました。
def adjacent_transpositions(perm): """ 指定された置換を隣接互換の積に分解します。 :param perm: 置換リスト :return: 隣接互換のリスト """ # 初期の状態として、置換をコピーする perm = perm[:] n = len(perm) transpositions = [] # シンプルなソートアルゴリズムを使って隣接互換を生成 for i in range(n): # 正しい位置に要素を配置 for j in range(1, n - i): if perm[j - 1] > perm[j]: # 隣接する要素を交換する perm[j - 1], perm[j] = perm[j], perm[j - 1] # その交換を隣接互換として記録 transpositions.append((j - 1, j)) return transpositions # 例として置換 [2, 3, 1] を隣接互換の積に分解 perm = [2, 3, 1] result = adjacent_transpositions(perm) print("隣接互換:", result)
続いて以下のように入力しました。
置換を隣接互換の積に分解したときの隣接互換の個数と、その置換の転倒数が等しいかどうかを調べるプログラムを書いてください
すると以下のようになりました。これは隣接互換のリストは作っていないのですがやっていることは上のものと同じです。
def count_inversions(arr): """ 配列内の転倒数を計算します。 :param arr: 入力配列 :return: 転倒数 """ n = len(arr) inversions = 0 # すべてのペアを調べて、逆順にあるものをカウント for i in range(n): for j in range(i + 1, n): if arr[i] > arr[j]: inversions += 1 return inversions def adjacent_transpositions_count(perm): """ 隣接互換によって置換を整列するための操作数を計算します。 :param perm: 置換リスト :return: 隣接互換の個数 """ n = len(perm) transpositions_count = 0 # シンプルなバブルソートで隣接互換の数をカウント for i in range(n): for j in range(1, n - i): if perm[j - 1] > perm[j]: # 隣接する要素を交換 perm[j - 1], perm[j] = perm[j], perm[j - 1] # 交換が発生したのでカウントを増やす transpositions_count += 1 return transpositions_count # 例として置換 [3, 1, 2, 4] を考えます perm = [3, 1, 2, 4] # 転倒数を計算 inversions = count_inversions(perm) # 隣接互換の数を計算 transpositions_count = adjacent_transpositions_count(perm[:]) # コピーを渡す # 結果を表示 print("転倒数:", inversions) print("隣接互換の数:", transpositions_count) print("等しいかどうか:", inversions == transpositions_count)
プログラムの改造
これに assert とコメントを入れます。
def adjacent_transpositions_count(perm): """ 隣接互換によって置換を整列するための操作数を計算します。 :param perm: 置換リスト :return: 隣接互換の個数 """ n = len(perm) transpositions_count = 0 # シンプルなバブルソートで隣接互換の数をカウント # (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]: # (4-開始) inversions_before = count_inversions(perm) # 隣接する要素を交換 perm[j - 1], perm[j] = perm[j], perm[j - 1] # 交換が発生したのでカウントを増やす transpositions_count += 1 # (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 transpositions_count
このプログラムは有限回のループなので終了します。コメントに書いたことをたどると、
- このプログラムで得られる隣接互換の個数は転倒数に等しい
- このプログラムが終了したときの転倒数は 0
ということがわかります。転倒数が 0 のときは恒等置換なので、元の置換は隣接互換の積で表されます。隣接互換は互換なので、元の置換は互換の積で表されます。
次に、互換にこのプログラムを適用するとどうなるかを考えます。そのためにコメントを書き換えたいと思います。これは次回以降やる予定です。
