Pythonで辞書式順序で最大の有効なシーケンスを構築するプログラム

問題の概要

ある数 n が与えられたとき、以下のすべての条件を満たすシーケンス(数列)を見つけることを考えます。

• 数値 1 はシーケンス内にちょうど1回出現する。
• 2 から n までの各数値は、それぞれ2回ずつ出現する。
• 2 以上 n 以下の各数値 i について、その2つの出現位置の距離はちょうど i である。

ここで、シーケンス上の2つの要素 a[i] と a[j] の距離は |j − i| として定義されます。求めるのは、これらの条件を満たすシーケンスの中で辞書式順序で最大のものです。

例えば、入力が n = 4 の場合、出力は次のようになります。

[4, 2, 3, 2, 4, 3, 1]

この結果を確認してみましょう。4はインデックス0と4に現れ、距離は4。3はインデックス2と5に現れ、距離は3。2はインデックス1と3に現れ、距離は2。1は1回だけ出現しています。すべての条件を満たしており、かつ辞書式順序で最大の並びになっています。

解法のアプローチ:バックトラッキング

この問題はバックトラッキング(探索の巻き戻し)を用いて解くことができます。基本的な戦略は次の通りです。

• 大きい数から順に配置を試すことで、辞書式順序で最大の解を優先的に見つけられる。
• 各位置について、残っている候補の数値を大きい順に試し、条件を満たすなら仮置きする。
• 再帰的に探索を進め、行き詰まった場合は配置を元に戻して(バックトラックして)別の候補を試す。

アルゴリズムの手順

1. 関数 backtrack(elems, res, start=0) を定義します。elems は未配置の数値のリスト、res は結果を格納する配列、start は現在注目している位置です。
2. elems が空になったら、すべての数値を配置できたので True を返します。
3. start が res の範囲外なら失敗として False を返します。
4. res[start] がすでに埋まっている場合(−1 以外の場合)は、次の位置へ進みます。
5. elems 内の各候補 num について(大きい順に並んでいるため先頭から試す):
   • num が 1 のとき距離 dist = 0、それ以外は dist = num とします。
   • start + dist が配列の範囲内で、かつ res[start + dist] が空いているなら、両方の位置に num を配置し、elems から num を取り除きます。
   • 再帰呼び出しが成功すれば True を返し、失敗した場合は配置を元に戻して次の候補を試します。

メイン処理

• elems:n から 1 まで降順に並べたリストを作成します(大きい数を優先的に試すため)。
• res:長さ n×2−1 の配列を −1 で初期化します(合計要素数は 1 + 2×(n−1) = 2n−1 個)。
• backtrack(elems, res) を実行し、完成した res を返します。

Pythonでの実装例

以下に実際のコードを示します。

def backtrack(elems, res, start=0):
    if len(elems) <= 0:
        return True

    if start >= len(res):
        return False

    if res[start] != -1:
        return backtrack(elems, res, start + 1)

    for i in range(len(elems)):
        num = elems[i]
        dist = 0 if num == 1 else num

        if (start + dist) < len(res) and res[start + dist] == -1:
            res[start] = num
            res[start + dist] = num
            elems.pop(i)

            if not backtrack(elems, res, start):
                # 失敗した場合は状態を元に戻す(バックトラック)
                res[start] = -1
                res[start + dist] = -1
                elems.insert(i, num)
                continue
            else:
                return True


def solve(n):
    elems = [i for i in range(n, 0, -1)]   # n から 1 へ降順
    res = [-1 for _ in range(n * 2 - 1)]   # 長さ 2n-1 の配列を -1 で初期化
    backtrack(elems, res)
    return res


n = 4
print(solve(n))

実行結果

入力

4

出力

[4, 2, 3, 2, 4, 3, 1]

計算量について

このバックトラッキング手法は、最悪の場合には指数的な時間計算量となります。しかし、大きい数値から優先的に試すことで、多くの場合 early success(早期に解が見つかる)ため、実用的なサイズの n であれば十分高速に動作します。より大きな n に対しては、貪欲法やヒューリスティクスを組み合わせた最適化も検討できます。