如何将数组的每个元素与相同数组的其他元素相加?

Suppose I have an array

假设我有一个数组

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

I want the output to be an array containing the numbers obtained by adding numbers from array a, as well as the elements of array a. i.e.,

我希望输出是一个数组，包含从数组a中添加数字获得的数字，以及数组a中的元素。

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)

How do I do this?

我该怎么做呢?

2 个解决方案

#1

So you want to generate all possible subsets of a set of numbers and list their sum.

所以你想生成一组数字的所有可能子集并列出它们的和。

First, you want to enumerate all the subsets. Since there are 2 ^ N subsets in a set containing N elements, you can simply do this by iterating through the natural numbers from 0 to 1 << (sizeof(arr) / sizeof(arr[0])) and treating the binary representation of the number in the following manner: if a particular bit is set at position k, then the kth element is in the currently generated subset, else it isn't.

首先，要枚举所有子集。因为有2 ^ N子集包含N个元素的集合,您可以简单地通过遍历自然数从0到1 < <(sizeof(arr)/ sizeof(arr[0]))和治疗数的二进制表示以下方式:如果已经设置了一个特定的位位置k,k元素在当前生成的子集,它不是。

Then, you should add all the selected elements together and store the result in the next slot of another array (sized 2 ^ N, obviously).

然后,你应该添加所有选中的元素在一起并将结果存储在另一个数组的下一个槽(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]);
}

#2

I would do it like this:

我会这样做:

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;
    }
}

This algorithm is linear in the size of the result array as each of its elements is computed with constant cost.

该算法在结果数组的大小上是线性的，因为它的每个元素都是以不变的代价计算的。

If you really must exclude the zero and want to malloc the result array, turn the algorithm around so that b is filled from the back with the zero element as the last element.

如果你真的必须排除0并且想要malloc结果数组，那么旋转算法使b从后面填充，0元素作为最后一个元素。

#1