皆様ありがとうございました。
前提・実現したいこと
<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の時は除外します。
網羅するという点で困っております。
ご助言頂けると助かります。よろしくお願いします。
-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
+4
集合を表す変数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;
}
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
checkベストアンサー
+2
こんにちは。
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;
}
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+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";
}
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+2
#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, " "));
}
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+2
#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;
}
※計算量に無駄があります
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+2
考えつくままに書くとこんな感じ。
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]);
}
}
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+2
昼休みの間に終わってしまった・・・。
折角書いたので投稿しておきます。
参考まで。
コードの長さでは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]);
}
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+2
私もアイデア(アルゴリズム)をば。
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超えようが、ソートできなかろうが、どんな場合でも対応できます。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう!
- ただいまの回答率 90.35%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる