皆様ありがとうございました。
###前提・実現したいこと
<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の時は除外します。
網羅するという点で困っております。
ご助言頂けると助かります。よろしくお願いします。
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答8件
0
集合を表す変数Sを用意して,そのビットが立っているかを見るような実装をするとこうなります
cpp
1#include <iostream> 2#include <set> 3#include <vector> 4using namespace std; 5 6int main() { 7 vector<int> A{1, 10, 100}; 8 set<int> B; 9 for(int S = 0; S < (1<<A.size()); S++) { 10 int sum = 0; 11 if(__builtin_popcount(S) > 1) { 12 for(int i = 0; i < A.size(); i++) { 13 if(S >> i & 1) sum += A[i]; 14 } 15 B.insert(sum); 16 } 17 } 18 for(auto e: B) cout << e << endl; 19}
投稿2017/07/05 03:12
総合スコア54
0
効率云々を考慮せず、愚直に実装。
C++
1#include <iostream> 2#include <array> 3#include <set> 4 5using namespace std; 6 7int main() { 8 set<int> B; 9 const int n = 3; 10 array<int,n> A = { 1, 10, 100 }; 11 // すべての組み合わせに対し 12 for ( int i = 0; i < n; ++i ) { 13 for ( int j = 0; j < n; ++j ) { 14 // (重複を除外して)その和をsetに投げ込む 15 if ( i != j ) { 16 B.insert(A[i]+A[j]); 17 } 18 } 19 } 20 int m = B.size(); 21 cout << "m = " << m << endl; 22 cout << "B = [ "; 23 for ( int item : B ) cout << item << ' '; 24 cout << "]\n"; 25}
投稿2017/07/05 02:42
総合スコア16614
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/07/05 02:52 編集
2017/07/05 02:51
2017/07/05 02:53
2017/07/05 02:56 編集
0
私もアイデア(アルゴリズム)をば。
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超えようが、ソートできなかろうが、どんな場合でも対応できます。
投稿2017/07/05 06:08
編集2017/07/05 06:11総合スコア1720
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
昼休みの間に終わってしまった・・・。
折角書いたので投稿しておきます。
参考まで。
コードの長さではC++には勝てないですね。
c
1#include <stdio.h> 2 3#define getbit(v,n) (v >> n & 1) 4 5int getbitnum(int v) 6{ 7 int sum = 0; 8 for(int i = 0; i < sizeof(int)*8; i++) sum += getbit(v,i); 9 return sum; 10} 11 12void calc(int *pa, int n, int *pb, int *pbn) 13{ 14 int i, j; 15 int max = 0; 16 int sum; 17 18 for(i = 0; i < n; i++){ 19 if(i != 0) max <<= 1; 20 max |= 1; 21 } 22 23 *pbn = 0; 24 for(i = 1; i <= max; i++){ 25 if(getbitnum(i) > 1){ 26 sum = 0; 27 for(j = 0; j < n; j++) sum += (pa[j] * getbit(i, j)); 28 for(j = 0; j < *pbn && pb[j] != sum; j++); 29 if(j == *pbn) pb[(*pbn)++] = sum; 30 } 31 } 32} 33 34int main(void) 35{ 36 int a[] = { 1, 10, 100 }; 37 int b[128]; 38 int bn; 39 calc(a, sizeof(a)/sizeof(int), b, &bn); 40 for(int i = 0; i < bn; i++) printf("%d\n", b[i]); 41} 42
投稿2017/07/05 04:40
総合スコア16996
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
ベストアンサー
こんにちは。
epistemeさんの回答を参考にしつつ、next_permutationを使ってみました。
効率無視でなるべく短いコードで。
C++
1#include <iostream> 2#include <algorithm> 3#include <vector> 4#include <set> 5#include <bitset> 6 7int main() 8{ 9 std::vector<unsigned> array={0b1, 0b10, 0b100}; 10 static const unsigned prec=3; 11 std::set<unsigned> result; 12 13 std::sort (array.begin(), array.end()); 14 for (size_t n=2; n <= array.size(); ++n) 15 { 16 reverse(array.begin()+n, array.end()); 17 do 18 { 19 unsigned x=0; 20 for (size_t i=0; i < n; ++i) x |= array[i]; 21 result.insert(x); 22 } while (next_permutation(array.begin(),array.end())); 23 } 24 25 std::cout << "m = " << result.size() << "\nB = [ "; 26 for (auto element : result ) std::cout << static_cast<std::bitset<prec>>(element) << ' '; 27 std::cout << "]" << std::endl; 28}
投稿2017/07/05 03:57
総合スコア23272
0
考えつくままに書くとこんな感じ。
1から順に数字をビットパターンと見なして、1のところの添え字の要素だけ足します。
要素数が、unsigned long long intのビット数未満だと出来ると思います。
C
1#include <stdio.h> 2int main(){ 3 int A[] = {1,10,100}; 4 int sizeA; 5 int ANS[9999]; 6 int nANS; 7 int sum; 8 unsigned long long int max; 9 unsigned long long int i; 10 int j; 11 int k; 12 13 sizeA = sizeof A/sizeof A[0]; 14 15 for(nANS=0; nANS<sizeA; nANS++){ 16 ANS[nANS] = A[nANS]; /* 「1つだけの和」を除外するために最初に登録しておく */ 17 } 18 max = 1 << sizeA; 19 for(i=1; i<max; i++){ /* 1以上の全てのビットパターンを網羅 */ 20 sum = 0; 21 for(j=0; j<sizeA; j++){ 22 if( i & 1<<j ){ /* ビットが立っていれば足す*/ 23 sum += A[j]; 24 } 25 } 26 ANS[nANS] = sum; 27 for(k=0; ANS[k]!=sum; k++){}; 28 if( k==nANS ){ 29 nANS++; /* 既出でなければ登録 */ 30 } 31 } 32 for(k=sizeA; k<nANS; k++){ 33 printf("%d\n",ANS[k]); 34 } 35}
投稿2017/07/05 03:41
総合スコア84380
0
c
1#include <iostream> 2#include <array> 3#include <set> 4 5int main() { 6 const int n = 3; 7 std::set<int> results; 8 std::array<int, n> A = { 1, 10, 100 }; 9 10 // 2~N の搾取を全通り試す 11 for (int v = 2; v <= A.size(); v++) { 12 for (int i = 0; i < n; ++i) { 13 int sum = A[i], c = 1; 14 for (int j = i; j < n; ++j) { 15 if (i == j) continue; 16 sum += A[j]; 17 if (++c >= v) break; 18 } 19 results.insert(sum); 20 } 21 } 22 for (int v : results) 23 std::cout << v << ' ' << std::endl; 24}
※計算量に無駄があります
投稿2017/07/05 03:26
編集2017/07/05 03:27総合スコア5030
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
C++
1#include <algorithm> 2#include <iostream> 3#include <iterator> 4#include <set> 5#include <vector> 6 7std::set<int> calc(int *a, size_t n) 8{ 9 std::set<int> result; 10 for (size_t m = 2; m <= n; m++) { 11 // n個中からm個を選択 12 std::vector<bool> selector(n); 13 for (size_t i = 0; i < m; i++) 14 selector[i] = true; 15 // m個選択の組み合わせを列挙 16 do { 17 int sum = 0; 18 for (size_t i = 0; i < m; i++) 19 sum += selector[i] ? a[i] : 0; 20 result.insert(sum); 21 } while (std::prev_permutation(selector.begin(), selector.end())); 22 } 23 return result; 24} 25 26int main() 27{ 28 constexpr size_t N = 3; 29 int A[] = { 1, 10, 100 }; 30 31 std::set<int> B = calc(A, N); 32 33 std::copy(B.begin(), B.end(), std::ostream_iterator<int>(std::cout, " ")); 34}
投稿2017/07/05 03:13
総合スコア6189
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。