C++で各要素がN未満となる一意なペアを見つける方法

このチュートリアルでは、C++を使って「指定した数 n より小さい値のみで構成される一意なペア（ユニークペア）」をすべて見つけて出力する方法を解説します。

重複のない組み合わせを効率よく列挙する基本的な考え方と、実際に動作するサンプルコードを通じて学んでいきましょう。

問題のアプローチ

この問題は、二重ループを使うことでシンプルに解決できます。手順は以下の通りです。

• 対象となる数 n を初期化します。

• 外側のループで i を 1 から n 未満まで繰り返します。

  • 内側のループで j を i + 1 から n 未満まで繰り返します。

    • ペア (i, j) を出力します。

内側のループの開始点を「i + 1」とすることで、(1,2) と (2,1) のような順序が入れ替わっただけの重複ペアを自動的に排除でき、常に一意なペアだけが生成されます。また、i と j はどちらも n 未満であるため、「各要素が N 未満」という条件も満たされます。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void uniquePairs(int n) {
    for (int i = 1; i < n; ++i) {
        for (int j = i + 1; j < n; j++) {
            cout << "(" << i << "," << j << ")" << endl;
        }
    }
}

int main() {
    int n = 5;
    uniquePairs(n);
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)

n = 5 の場合、1〜4 の数値から選ばれるすべての一意なペアが6個出力されていることが確認できます。一般に、n 未満の正整数からなる一意なペアの総数は n(n-1)/2 個になります（この場合は 5×4÷2 = 10... ではなく、1〜n-1 から2つ選ぶ組み合わせなので (n-1)(n-2)/2 = 3×2 = ... 実際の出力では 6 個です）。

計算量について

このアルゴリズムの時間計算量は O(n²) です。外側と内側のループがそれぞれ最大 n 回ずつ回るためです。n が大きくなると処理時間が急増するため、大規模なデータを扱う場合は注意が必要ですが、小規模な範囲でのペア列挙には十分実用的です。

まとめ

今回は、C++における二重ループを使って、各要素が n 未満となる一意なペアをすべて列挙する方法を紹介しました。ポイントは内側のループを i + 1 から始めることで重複を防ぐ点です。組み合わせ列挙の基礎として、さまざまな場面で応用できるテクニックなので、ぜひマスターしておきましょう。

このチュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。