任意の部分集合のGCDが元の集合に含まれる配列の生成アルゴリズム【C++実装例】

今回は少し変わったアルゴリズムの問題を紹介します。N個の要素からなる集合が与えられたとき、「その配列の任意の部分集合を取り出した際のGCD（最大公約数）が、必ず元の集合の要素のいずれかに一致する」という性質を持つ配列を生成します。さらに、生成する配列の長さはGCDの集合の長さの3倍を超えてはならないという制約も課せられています。

例えば、{2, 4, 6, 12} という4つの数値が与えられた場合、答えの一つは {2, 2, 4, 2, 6, 2, 12} となります。この配列からどのような部分集合を選んでも、そのGCDは必ず {2, 4, 6, 12} の中に存在することが確認できます。

解法のアプローチ

この問題を解くには、まず与えられたリストをソートします。次に、配列全体のGCDが与えられた集合の最小要素と一致しているかどうかを判定します。一致している場合は、各要素の手前にGCDを挿入していくことで目的の配列を作成できます。一致しない場合は、条件を満たす配列は生成できません。

この方法が有効な理由は、各要素の直前に配列全体のGCDを配置することで、任意の部分集合のGCDが必ず元の集合の要素になるようにできるからです。また、生成される配列の長さは 2n − 1（nは元の集合のサイズ）となるため、3倍以内という制約も自然に満たされます。

アルゴリズム

generateArray(arr, n)

Begin
   answer := 空の配列
   gcd := 配列 arr 全体のGCD
   if gcd が arr の最小要素と等しい then
      for arr 内の各要素 e について
         answer に gcd を追加
         answer に e を追加
      done
      answer を表示
   else
      配列は生成できない
   end if
End

C++による実装例

#include<iostream>
#include<vector>
#include<set>
using namespace std;
int gcd(int a, int b) {
   if (a == 0)
      return b;
   return gcd(b % a, a);
}
int getGCDofArray(vector<int> arr) {
   int result = arr[0];
   for (int i = 1; i < arr.size(); i++)
      result = gcd(arr[i], result);
   return result;
}
void generateArray(vector<int> arr) {
   vector<int> answer;
   int GCD_of_array = getGCDofArray(arr);
   if(GCD_of_array == arr[0]) { //GCDが最小要素と一致する場合
      answer.push_back(arr[0]);
      for(int i = 1; i < arr.size(); i++) { //各要素の前に最小値を挿入
         answer.push_back(arr[0]);
         answer.push_back(arr[i]);
      }
      for (int i = 0; i < answer.size(); i++)
      cout << answer[i] << " ";
   }
   else
   cout << "No array can be build";
}
int main() {
   int n = 4;
   int data[]= {2, 4, 6, 12};
   set<int> GCD(data, data + n);
   vector<int> arr;
   set<int>::iterator it;
   for(it = GCD.begin(); it!= GCD.end(); ++it)
      arr.push_back(*it);
   generateArray(arr);
}

出力結果

2 2 4 2 6 2 12

このように、set を使うことで重複のないソート済みの要素列を簡単に取得でき、計算量も O(n log n) 程度に抑えられます。GCDの計算部分はユークリッドの互除法を再帰的に用いており、非常に効率的です。