C++でラテン方格（ラテン方陣）を生成する方法を解説

ラテン方格（ラテン方陣）とは、特別なパターンを持つ行列のことです。まずはいくつかの例を見ながら、そのパターンを確認していきましょう。

1 2
2 1

1 2 3
3 1 2
2 3 1

1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1

上記の例のように、ラテン方格はさまざまなサイズで生成されます。しかし、これらの行列のパターンを注意深く観察すると、前の行の最後の数字が、次の行の最初の要素として現れるという規則性があることがわかります。

これこそがラテン方格に隠されたパターンです。この記事では、入力として与えられた n に対して、このような行列を生成するプログラムを作成します。

アルゴリズム

• 任意の数値で n を初期化します。
• first_half_end という変数を n + 1 の値で初期化します。
• 1 から n まで（両端を含む）繰り返すループを作成します。
  • first_half_end の値を first_half_start という変数に代入します。
  • first_half_start が n に達するまでループし、変数の値を出力します。
  • 次に、1 から first_half_end - 1 まで繰り返すループを作成し、各値を出力します。
  • first_half_end の値を 1 減らします。
  • 次の行へ移動します。

C++での実装

以下は、上記のアルゴリズムを C++ で実装したコードです。

#include <bits/stdc++.h>

using namespace std;

void generateLatinSquare(int n) {
    int first_half_end = n + 1;

    for (int i = 1; i <= n; i++) {
        int first_half_start = first_half_end;
        while (first_half_start <= n) {
            cout << first_half_start << " ";
            first_half_start++;
        }

        for (int second_half_start = 1; second_half_start < first_half_end; second_half_start++) {
            cout << second_half_start << " ";
        }
        first_half_end--;
        cout << endl;
    }
    cout << endl;
}

int main(void) {
    generateLatinSquare(2);
    generateLatinSquare(3);
    generateLatinSquare(4);
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

1 2
2 1

1 2 3
3 1 2
2 3 1

1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1

このように、各行が前の行の末尾の数字から始まる規則的な行列が正しく生成されていることが確認できます。時間計算量は O(n²)、空間計算量は O(1) であり、非常に効率的なアルゴリズムです。