隣接要素の合計が元の配列と一致する別の順列を求めるC++プログラム

問題概要

n個の要素からなる配列Aがあるとします。関数F(p)は、配列pの隣接する要素同士の合計値を昇順にソートした配列として定義されます。すなわち、F(p) = sort([p1+p2, p2+p3, ..., pn-1+pn]) です。ここで、ある順列Aが与えられたとき、F(A)の結果が元の配列と完全に同じになる「別の」順列を見つけることが課題となります。

具体例

入力が A = [2, 1, 6, 5, 4, 3] の場合を考えてみましょう。このときの出力の一例は [1, 2, 5, 6, 3, 4] です。

まず元の配列について計算すると:

F(A) = sort([2+1, 1+6, 6+5, 5+4, 4+3]) = sort([3, 7, 11, 9, 7]) = [3, 7, 7, 9, 11]

一方、出力の候補 [1, 2, 5, 6, 3, 4] について計算すると:

sort([1+2, 2+5, 5+6, 6+3, 3+4]) = sort([3, 7, 11, 9, 7]) = [3, 7, 7, 9, 11]

両者の結果が一致していることが分かります。なお、条件を満たす答えは複数存在する可能性があります。

解法のアプローチ

この問題の鍵となるのは、配列を逆順にするという非常にシンプルな操作です。配列を反転させると、隣接する要素のペアは同じ組み合わせが逆向きに現れるだけなので、隣接要素の合計値の集合(マルチセット)は一切変わりません。その結果、ソート後のF(A)も必ず元の配列と同一になります。

アルゴリズムの手順

1. 配列Aのサイズnを取得します。
2. i を n-1 から 0 まで減らしながらループし、各要素 A[i] を出力します。

n := size of A
for initialize i := n - 1, when i >= 0, update (decrease i by 1), do:
    print A[i]

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A) {
    int n = A.size();
    for (int i = n - 1; i >= 0; i--)
        cout << A[i] << ", ";
}
int main() {
    vector<int> A = { 2, 1, 6, 5, 4, 3 };
    solve(A);
}

入力

{ 2, 1, 6, 5, 4, 3 }

出力

3, 4, 5, 6, 1, 2,

まとめ

隣接要素の合計をソートした結果が等しくなる別の順列を求める問題では、元の配列を単純に逆順にすればよいことが分かりました。反転しても隣接ペアの合計の集合は不変であるため、時間計算量O(n)という非常に効率的な方法で解答を得ることができます。