Pythonで1回のスワップだけで配列をソートできるかどうかを判定する方法

整数要素を含む配列が与えられたとします。この配列に対して、スワップ(要素の入れ替え)操作をたった1回だけ実行できるという条件のもとで、配列の値を非減少順(昇順)に並べ替えることができるかどうかを調べる必要があります。可能であれば「Can be done(実行可能)」、不可能であれば「Can't be done(実行不可能)」と答えます。

例えば、入力が input_list = [7, 8, 12, 10, 11, 9] の場合、出力は「Can be done」となります。これは、10 と 9 を入れ替えることで [7, 8, 9, 10, 11, 12] という昇順の配列にできるためです。

解決のためのアプローチ

この問題は、元の配列とソート済みの配列を比較することで効率的に判定できます。以下の手順に従います。

• temp_list として input_list のコピーを作成します。
• temp_list をソートします。
• swap_count を 0 に初期化します。
• i を 0 から input_list のサイズまで繰り返します。
  • input_list[i] が temp_list[i] と異なる場合、swap_count を 1 増やします。
• swap_count が 0 または 2 の場合は True を返し、それ以外の場合は False を返します。

ここでのポイントは、元の配列とソート済みの配列を比較したときに、値が異なる位置がちょうど2つだけであれば、その2つの要素を入れ替えることでソート済みの状態にできるという点です。また、swap_count が 0 の場合は、すでに配列がソート済みであることを意味するため、スワップは不要となります。

実装例

以下のコードを見ると、理解がより深まるでしょう。

from copy import deepcopy

def solve(input_list):
    temp_list = deepcopy(input_list)
    temp_list.sort()
    swap_count = 0
    for i in range(len(input_list)):
        if input_list[i] != temp_list[i]:
            swap_count += 1
    if swap_count == 0 or swap_count == 2:
        print("Can be done")
    else:
        print("Can't be done")

input_list = [7, 8, 12, 10, 11, 9]
solve(input_list)

入力

[7, 8, 12, 10, 11, 9]

出力

Can be done