C++ 全組み合わせの足し算の算出とその組みの数

Question

####C++の質問です。
入力で整数n、n個の数字が与えられた時、その数字の足し算の組み合わせを算出するプログラムを作りたいです。数字を１つもつかわなくてもよいという条件です。
例えば、 3つの数字{1,3,5}が与えられた時、{0,1,3,4,5,6,8,9]の８通り　というのを求めたいです。

using namespace std;
int main(void){

    int n;
    cin >> n;
    int i;
    int a[n+1];
    set<int> B;
    
    a[0] = 0;
    for(i=1;i<n+1;i++){
        cin >> a[i];
    }
    
    for(int S = 0; S < (1<<(n+1)); S++) {
        int sum = 0;
        if(__builtin_popcount(S) > 0) {
            for(int i = 0; i < n+1; i++) {
                if(S >> i & 1) sum += a[i];
            }
            
            B.insert(sum);
        }
    }
    std::cout <<B.size()<<std::endl; 
    for(auto e: B) std::cout<<e<<std::endl;
    return 0;
}

自力で作ったのがこちらになります。（ネットで調べながら）
こちらaの要素数が小さければ正確な値を出力できますが、要素数が大きくなるとタイムアウトエラーが発生してしまいます。
プログラミング初心者ですので、ご丁寧に教えていただけたら幸いです。

Comments

[Zuishin]

メモ

https://teratail.com/questions/218057#reply-320073
半年前の質問が今日解決しました。回答は読んでないと思います。

[Bearded-Ockham]

「n個の数字」-最大で何個ですか?

[SHOMI]

タイムアウトエラー？競技プログラミングでしょうか。そうであるなら問題文へのリンクを貼っていただけますか。

[hheytakuc]

n個の数字は最大で100、その合計は100と予め決まっております。情報漏れてすみません。

問題文のリンク貼るのがNGみたいなので、paizaとだけしか言えないです。

[Zuishin]

だろうと思いました。リンクだけではありません。問題の解説を聞くのも不正です。Paiza のスキルチェックは入社試験代わりに使われます。

[hheytakuc]

すぐに削除します。申し訳ないです。

Answer 1

結論から言うと、計算量のオーダーを下げるアルゴリズムは存在しません。例えばn個の数字が1,2,4,8,...であれば、その和は0から2^n-1までのすべての数で、単純計算でn*2(n-1)回程度の可算が必要です。

しかし、計算量を減らす工夫はできます。
まず、入力された数字を小さい順大きい順に並べ替えます。
そして、最初に集合S = {0}を考えます。
一番小さい大きい数字が7で、それが2つあるとき、Sに対して、Sの各要素に7を1回足した集合Tと、7を2回足した集合Uを考えます。そして、Sの要素にTとUの要素を追加します。**このとき、TにSの要素とUの要素を追加して、Sと置き換えます。**この時点でSは{0,7,14}となります。あとは入力された各異なる数に対して同様に考えます。

4/26追記：数学の理論としては先の通りなのですが、集合の実装として、2分木を用いている場合、小さい順に追加していくと、木の生成が不均一となる、という致命的な欠陥に気がつきましたので、該当箇所を修正しました。

Comments

[hheytakuc]

回答ありがとうございます。
アルゴリズムのご説明ありがとうございます
考えてみます。

[swordone]

別に小さい順に並べる必要はないような。

[jimbe]

java だとこんな感じですね. ({1,3,5}の場合)

Set<Integer> a = new HashSet<>();
a.add(0);
for(int v : new int[]{1,3,5}) {
Set<Integer> b = new HashSet<>();
for(int s : a) b.add(s+v);
a.addAll(b);
}
for(int v : a) System.out.println(v);

どなたか c++ に訳して頂けると ><

[jimbe]

C++ を書いてみたら(合っているかは兎も角)動いたので回答にしました.
大変失礼致しました(_ _;

Answer 2

majiponi さんの回答にコメントで java を書きましたが, やってみようと見様見真似で書いてみました.
これでも一応(もうン十年前!?)C++の本は読んだのですが, やはり全然ダメですね.
一応paiza.ioで{1,3,5}は確認しましたが... B.insert のループは set_union とかいう関数が使えるのでしょうか.

#include <iostream>
#include <set>
using namespace std;
int main(void){
  int n,a;
  cin >> n;
  set<int> B,T;
  B.insert(0);
  for(int i=0;i<n;i++) {
    cin >> a;
    T.clear();
    for(auto e:B) T.insert(e+a);
    for(auto t:T) B.insert(t);
  }
  std::cout<<B.size()<<std::endl;
  for(auto e:B) std::cout<<e<<std::endl;
}

Comments

[hheytakuc]

jimbeさん回答ありがとうございます。
このコードであればnが大きい場合に対応していました。

すぐに問題に取り掛かるのではなく、アルゴリズムなど基礎的なところを固めていこうと思いました。

[jimbe]

これがどんなアルゴリズムのお話になるのか分かりませんが, ご質問の仕様と majiponi さんの集合のお話(集合自体の理論は分からないのですが^^;)と kazuma-a さんの「…途中…までの和を利用して、残りだけを変えれば…」というお話から思いついた"結果オーライ"なコードです.
ですので, 可能であればどんな入力があったのか(何個の数字で結果が何個で何秒だったのか等でも)教えて頂けないでしょうか.

[Zuishin]

Paiza スキルチェックのカンニングのようです。

[jimbe]

Paiza の影響が公的にどれほどあるのか知りませんが, これが本当にスキル「チェック」であれば,
> アルゴリズムなど基礎的なところを固めていこうと思いました
ということですから, きっかけにはなったということになるでしょうか.

[Zuishin]

この結果を参考に企業が人材を登用します。
S ランクの問題を解けた人は S ランクの人材を募集している企業に応募できます。
つまり、試験のカンニングです。

[Zuishin]

問題にチャレンジする際には次のようなメッセージがその都度大きく表示され、「同意する」を押さないと開始できません。

> 問題を開始する前に以下の規約をご確認ください
> ・問題及び提出コード、ヒントをブログやSNS等に掲載しない
> ・回答やヒントを教えてもらったり他人のコードを利用しない
> ・複数アカウントで事前に問題を見るなどの不正行為をしない

[Zuishin]

ここに問題と解答を書くことにより、その問題はこの回答を見ることのできる人すべてにとってカンニングできるものとなり、問題としての機能を失います。これは Paiza の財産を侵す行為と言えます。

[Zuishin]

以上のような問題がありますが、これは質問者個人の「固めていこうと思いました」という意識を得ることで解消されるものでしょうか？
またその意識は、これらに匹敵する価値のあるものでしょうか？

[jimbe]

> ・回答やヒントを教えてもらったり他人のコードを利用しない

思いきり該当しているということですね.
この回答の削除を依頼してみます.

Answer 3

そのコードは無駄が多いです。

S が 0 以外の時は、__builtin_popcount(S) は常に正です。
for (int S = 1; で始めれば、__builtin_popcount(S) は不要です。
それより、S = 0 から始めれば、a[0] = 0; は不要で、int a[n] で済みます。

これらを踏まえて書き直すと、

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	set<int> b;
	int m = 1 << n;
	for (int s = 0; s < m; s++) {
		int sum = 0;
		for (int i = 0; i < n; i++)
			if (s >> i & 1) sum + a[i];
		b.insert(sum);
	}
	cout << "size = " << b.size() << '\n';
	for (int e: b) cout << ' ' << e;
	cout << '\n';
}

さらに無駄なのは毎回 n個のビットが 1かどうかチェックし、
a[i] を足していることです。途中のビットまでの和を利用して、
残りだけを変えれば、足し算の回数を減らせます。

再帰呼出しでバックトラックの手法を使うということです。

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int n;
vector<int> a;
set<int> b;

void proc(int i, int sum)
{
	if (i == n) b.insert(sum);
	else proc(i + 1, sum), proc(i + 1, sum += a[i]);
}

int main()
{
	cin >> n;
	a.resize(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	proc(0, 0);
	cout << "size = " << b.size() << '\n';
	for (int e: b) cout << ' ' << e;
	cout << '\n';
}

Comments

[hheytakuc]

丁寧な回答ありがとうございます。
無駄が多いこと、ご指摘ありがとうございます。

コードを直しても、やはりタイムオーバーとなってしまいます。
環境の問題でしょうか？

[kazuma-s]

直したコードとタイムオーバーになったデータを示してくれないと何も言えません。

[Zuishin]

コードをほとんど読まず、再帰とバックトラックだけに反応して書くので考慮済みかもしれませんが、k 番目までの要素の和には複数の枝が存在するので、その先には重複した枝が伸びます。幅優先探索して枝刈りする必要があると思います。

ただこれ、Paiza スキルチェックじゃないかって気がするんですよねえ。

[kazuma-s]

そうですね。{1, 2, 3, 4, 5} という入力に対して、最初の 3個で {1, 2} で和が 3 の場合と {3}だけで和が 3の場合の両方に対して、残りの {4, 5} の組み合わせを計算してしまうのは無駄ですね。

Answer 4

アルゴリズムの基本的な考え方はmajiponiさんと同じですが、ビット演算を使えば高速化できそうです。ただし、総和が63以下であることが保証できれば、ですが。64以上になるのであれば少し工夫が必要です。
C++は全く書いたことがないので結構書き方は適当ですが…

using namespace std;
int main(void){

    int n;
    cin >> n;
    int i;
    int a;
    int max;
    long long int x;
    set<int> B;
    x=1;
    max = 0;
    for(i=0;i<n;i++){
        cin >> a;
        x = x | (x << a);
        max += a;
    }

    for(int S = 0; S <= max; S++) {
        if(x & (1 << S)) {
            B.insert(S);
        }
    }
    std::cout <<B.size()<<std::endl; 
    for(auto e: B) std::cout<<e<<std::endl;
    return 0;
}

Javaの方がなじみあるのでJavaで書いてみますね。
BigInteger使うと簡単なんだろうけど、C++に標準の多倍長整数型がないようなので、配列で頑張った
最後だけめんどくさかったのでBitSetに変換して出力

import java.util.*;

public class Main {
    public static void main(String[] args) {
        try (Scanner s = new Scanner(System.in)) {
            int n = s.nextInt();
            int sum = 0;
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = s.nextInt();
                sum += a[i];
            }
            long[] bit = new long[(sum >> 6) + 1];
            bit[0] = 1;
            sum = 0;
    
            for (int i = 0; i < n; i++) {
                int shiftCell = a[i] >> 6;
                int shiftBit = a[i] & 0x3f;
                for (int j = (sum >> 6); j >= 0; j--) {
                    if (shiftBit != 0) {
                        long upper = bit[j] >>> (64 - shiftBit);
                        if (upper != 0) {
                            bit[j + shiftCell + 1] |= upper;
                        }
                    }
                    bit[j + shiftCell] |= bit[j] << shiftBit;
                }
                sum += a[i];
            }
            System.out.println(BitSet.valueOf(bit));
        }
    }
}

Answer 5

数字のリストに0を追加しています。

    a[0] = 0;

おそらく「数字を１つもつかわなくてもよい」という条件を満たすために追加しているのだと思いますが、下のループで__builtin_popcount(S) > 0のチェックをなくせば、必要ありません。

    for(int S = 0; S < (1<<(n+1)); S++) {
        int sum = 0;
        if(__builtin_popcount(S) > 0) {

このループでSが0とは、数字が一つも選択されていない場合を指しており、__builtin_popcount(S) > 0のチェックがなければ、自動的に数字を一つも使わない場合を計算できます。

数字のリストから0を省くことで、ループの回数を半分にできます。それで十分かはわかりませんが。

---

表示しなければならない数が多いと計算より表示の方が時間がかかりますが、きっとうまくテストケースを作っているのでしょう。