コイントスでランダムな部分集合を生成するC++プログラム

本記事では、コイントス（コイン投げ）の原理を応用して、配列の中からランダムな部分集合を生成するC++プログラムを紹介します。各要素に対してコインを1回ずつ投げるイメージで、「表（1）」が出た要素だけを選んで部分集合を作るというシンプルな手法です。

アルゴリズム

このプログラムの処理の流れは以下のとおりです。

1. 配列に格納する要素を入力として受け取ります。
2. rand() 関数を使って、ランダムな0または1の二値列を生成します。
3. コイントスのように0か1をランダムに決定し、値が「1」だった場合のみ、その位置の配列要素を出力します。

サンプルコード

#include<iostream>
#include<stdlib.h>
using namespace std;
int main() {
    int i, n;
    cout<<"\nEnter the number of elements: ";
    cin>>n;
    int a[n];
    cout<<"\n";
    for(i = 0; i < n; i++) {
        cout<<"Enter "<<i+1<<" element: ";
        cin>>a[i];
    }
    cout<<"\nThe random subset of the given set is: \n\t { ";
        for(i = 0; i < n; i++) {
            if(rand()%2 == 1)
                cout<<a[i]<<" ";
        }
    cout<<"}";
    return 0;
}

実行結果

Enter the number of elements: 7
Enter 1 element: 7
Enter 2 element: 6
Enter 3 element: 5
Enter 4 element: 4
Enter 5 element: 3
Enter 6 element: 2
Enter 7 element: 1
The random subset of the given set is:
{ 7 6 3 }

プログラムの解説

このプログラムの核心は rand() % 2 の部分です。rand() は擬似乱数を生成する関数であり、その値を2で割った余りを取ることで、必ず 0 または 1 のどちらかが得られます。これはちょうどコインを投げて「裏（0）」か「表（1）」が出る動きに相当します。

各要素についてこの判定を行い、結果が「1（表）」であればその要素を部分集合に含めます。上記の実行例では、7つの要素 {7, 6, 5, 4, 3, 2, 1} のうち、{7, 6, 3} の3つが選ばれています。

なお、実行するたびに乱数の並びが変わらない場合は、srand(time(NULL)) を呼び出して乱数のシードを初期化すると、毎回異なる部分集合が得られるようになります。また、より現代的なC++では <random> ヘッダーの mt19937 や uniform_int_distribution を使うことで、品質の高い乱数を簡単に扱えます。