配列の要素間の和を全パターン求めるプログラムを作成したい。

Question

皆様ありがとうございました。

###前提・実現したいこと
<CもしくはC++>
配列の要素間の和を全パターン求めるプログラムを作成したい。

【例】
/-------------------------------------------------/
要素n=3つの配列の中身がA=[a=1,b=10,c=100]とする。
和のパターンは
B=[11,101,110,111]のm=4種類となる。
※B=[a+b, a+c, b+c, a+b+c]
/-------------------------------------------------/

nとA(配列)が与えられたときにmとB(配列)が得られるようにしたいです。
要素数が1の時は除外します。

網羅するという点で困っております。
ご助言頂けると助かります。よろしくお願いします。

Answer 1

集合を表す変数Sを用意して，そのビットが立っているかを見るような実装をするとこうなります

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

int main() {
    vector<int> A{1, 10, 100};
    set<int> B;
    for(int S = 0; S < (1<<A.size()); S++) {
        int sum = 0;
        if(__builtin_popcount(S) > 1) {
            for(int i = 0; i < A.size(); i++) {
                if(S >> i & 1) sum += A[i];
            }
            B.insert(sum);
        }
    }
    for(auto e: B) cout << e << endl;
}

Answer 2

効率云々を考慮せず、愚直に実装。

#include <iostream>
#include <array>
#include <set>

using namespace std;

int main() {
  set<int> B;
  const int n = 3;
  array<int,n> A = { 1, 10, 100 };
  // すべての組み合わせに対し
  for ( int i = 0; i < n; ++i ) {
    for ( int j = 0; j < n; ++j ) {
      // (重複を除外して)その和をsetに投げ込む
      if ( i != j ) {
        B.insert(A[i]+A[j]);
      }
    }
  }
  int m = B.size();
  cout << "m = " << m << endl;
  cout << "B = [ ";
  for ( int item : B ) cout << item << ' ';
  cout << "]\n";
}

Comments

[maisumakun]

これだと、111が取れませんね

[mattn]

n_k さん向けのコメント: 以下の様にするとループ回数が減らせます。

for ( int i = 0; i < n - 1; ++i ) {
for ( int j = i + 1; j < n; ++j ) {
B.insert(A[i]+A[j]);
}
}

たしかに 111 取れないすね

[n_k]

ありがとうございます、すいません、質問が悪かったようなので質問を修正させていただきます。

[mattn]

今の問題だと配列が5個あった場合に、2個, 3個, 4個, 5個 の総当たりが必要ですね。

[episteme]

あ、要素数２～n での総和なのか...組み合わせ列挙のトコをいじらんならんですね。
# 要素数 1は除外? 問題をきっちり定義しておくれ。

Answer 3

私もアイデア(アルゴリズム)をば。

1項だけの場合、像I(1)は空集合。

n+1項(n>1)の場合の像I(n+1)は、n項の場合の像I(n)、n項からなる原像A(n)、n+1項目の要素a(n+1)を用いて、
I(n+1) = I(n) ∪ {n+i | r∈I(n)} ∪ {n+a | a∈A(n)}
と表される。

日本語で書くなら、再帰呼び出しを使えば書けますよ、ということ(実は再帰使わなくても可能)。これならメモリが許す限り、要素数が64bit超えようが、ソートできなかろうが、どんな場合でも対応できます。

Answer 4

昼休みの間に終わってしまった・・・。
折角書いたので投稿しておきます。
参考まで。
コードの長さではC++には勝てないですね。

#include <stdio.h>

#define getbit(v,n) (v >> n & 1)

int getbitnum(int v)
{
    int sum = 0;
    for(int i = 0; i < sizeof(int)*8; i++) sum += getbit(v,i);
    return sum;
}

void calc(int *pa, int n, int *pb, int *pbn)
{
    int i, j;
    int max = 0;
    int sum;
    
    for(i = 0; i < n; i++){
        if(i != 0) max <<= 1;
        max |= 1;
    }

    *pbn = 0;
    for(i = 1; i <= max; i++){
        if(getbitnum(i) > 1){
            sum = 0;
            for(j = 0; j < n; j++) sum += (pa[j] * getbit(i, j));
            for(j = 0; j < *pbn && pb[j] != sum; j++);
            if(j == *pbn) pb[(*pbn)++] = sum;
        }
    }
}

int main(void)
{
    int a[] = { 1, 10, 100 };
    int b[128];
    int bn;
    calc(a, sizeof(a)/sizeof(int), b, &bn);
    for(int i = 0; i < bn; i++) printf("%d\n", b[i]);
}

Answer 5

こんにちは。

epistemeさんの回答を参考にしつつ、next_permutationを使ってみました。
効率無視でなるべく短いコードで。

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <bitset>

int main()
{
    std::vector<unsigned> array={0b1, 0b10, 0b100};
    static const unsigned prec=3;
    std::set<unsigned> result;

    std::sort (array.begin(), array.end());
    for (size_t n=2; n <= array.size(); ++n)
    {
        reverse(array.begin()+n, array.end());
        do
        {
            unsigned x=0;
            for (size_t i=0; i < n; ++i) x |= array[i];
            result.insert(x);        
        } while (next_permutation(array.begin(),array.end()));
    }
    
    std::cout << "m = " << result.size() << "\nB = [ ";
    for (auto element : result ) std::cout << static_cast<std::bitset<prec>>(element) << ' ';
    std::cout << "]" << std::endl;
}

Comments

[yohhoy]

bitwise-orで良いの？と思わなくもないですが、正解は質問者のみぞ知る...

Answer 6

考えつくままに書くとこんな感じ。
1から順に数字をビットパターンと見なして、1のところの添え字の要素だけ足します。
要素数が、unsigned long long intのビット数未満だと出来ると思います。

#include <stdio.h>
int main(){
    int A[] = {1,10,100};
    int sizeA;
    int ANS[9999];
    int nANS;
    int sum;
    unsigned long long int max;
    unsigned long long int i;
    int j;
    int k;

    sizeA = sizeof A/sizeof A[0];

    for(nANS=0; nANS<sizeA; nANS++){
        ANS[nANS] = A[nANS]; /* 「1つだけの和」を除外するために最初に登録しておく */
    }
    max = 1 << sizeA;
    for(i=1; i<max; i++){ /* 1以上の全てのビットパターンを網羅 */
        sum = 0;
        for(j=0; j<sizeA; j++){
            if( i & 1<<j ){ /* ビットが立っていれば足す*/
                sum += A[j];
            }
        }
        ANS[nANS] = sum;
        for(k=0; ANS[k]!=sum; k++){};
        if( k==nANS ){
            nANS++; /* 既出でなければ登録 */
        }
    }
    for(k=sizeA; k<nANS; k++){
        printf("%d\n",ANS[k]);
    }
}

Comments

[otn]

みんなC++ですね。C++はリファレンス見ないと書けない。

Answer 7

#include <iostream>
#include <array>
#include <set>

int main() {
  const int n = 3;
  std::set<int> results;
  std::array<int, n> A = { 1, 10, 100 };

  // 2～N の搾取を全通り試す
  for (int v = 2; v <= A.size(); v++) {
    for (int i = 0; i < n; ++i) {
      int sum = A[i], c = 1;
      for (int j = i; j < n; ++j) {
        if (i == j) continue;
        sum += A[j];
        if (++c >= v) break;
      }
      results.insert(sum);
    }
  }
  for (int v : results)
    std::cout << v << ' ' << std::endl;
}

※計算量に無駄があります

Answer 8

#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
#include <vector>

std::set<int> calc(int *a, size_t n)
{
  std::set<int> result;
  for (size_t m = 2; m <= n; m++) {
    // n個中からm個を選択
    std::vector<bool> selector(n);
    for (size_t i = 0; i < m; i++)
      selector[i] = true;
    // m個選択の組み合わせを列挙
    do {
      int sum = 0;
      for (size_t i = 0; i < m; i++)
        sum += selector[i] ? a[i] : 0;
      result.insert(sum);
    } while (std::prev_permutation(selector.begin(), selector.end()));
  }
  return result;
}

int main()
{
  constexpr size_t N = 3;
  int A[] = { 1, 10, 100 };
    
  std::set<int> B = calc(A, N);

  std::copy(B.begin(), B.end(), std::ostream_iterator<int>(std::cout, " "));
}