c - 配列の各要素を同じ配列の他の要素に追加する方法は?

Question

配列があるとします

a[3]={1,3,8}  

出力を、配列 a から数値を加算して得られた数値と、配列 aie の要素を含む配列にしたいのですが、

b[0]=1
b[1]=3
b[2]=8
b[3]=4  //(1+3)
b[4]=9  //(1+8)
b[5]=11 //(3+8)
b[6]=12 //(1+3+8) 

どうすればいいですか？

Answer 1

したがって、一連の数値のすべての可能なサブセットを生成し、それらの合計をリストする必要があります。

まず、すべてのサブセットを列挙します。2 ^ N要素を含むセットにはサブセットがあるためN、0 から までの自然数を反復処理1 << (sizeof(arr) / sizeof(arr[0]))し、次の方法で数値の 2 進表現を処理することで簡単にこれを行うことができます: 特定のビットが位置kに設定されている場合、kth 要素は現在生成されているサブセットにあり、そうでない場合はそうではありません。

次に、選択したすべての要素を一緒に追加し、結果を別の配列の次のスロットに格納する必要があります (サイズ2 ^ Nは明らかに )。

#define COUNT(a) (sizeof(a) / sizeof(a[0]))
#include <limits.h> // for CHAR_BIT

unsigned a[3] = { 1, 3, 8 };
unsigned sums[1 << COUNT(a)] = { 0 };

for (unsigned i = 0; i < COUNT(sums); i++) {
    for (unsigned j = 0; j < sizeof(i) * CHAR_BIT; j++) {
        if ((i >> j) & 1) {
            sums[i] += a[j];
        }
    }
}

for (unsigned i = 0; i < COUNT(sums); i++) {
    printf("%d\n", sums[i]);
}

Answer 2

私は次のようにします：

b[0] = 0;  //This is not listed in the question, but should be included in the result IMHO.
for(long i = 0; i < elementsA; i++) {
    long preexistingElements = 1 << i;
    long curElement = a[i];
    for(long j = 0; j < preexistingElements; j++) {
        b[j + preexistingElements] = b[j] + curElement;
    }
}

このアルゴリズムは、結果配列の各要素が一定のコストで計算されるため、結果配列のサイズに比例します。

本当にゼロを除外する必要があり、結果の配列を malloc したい場合は、アルゴリズムを逆にして、最後の要素としてゼロ要素で b を後ろから埋めるようにします。