Occurrence of element in all contiguous partitionings of a set

Question

For a set S={1,2,3}, I perform all possible contiguous partitioning on the set to get {{1},{2},{3}},{{1,2},{3}},{{1},{2,3}},{{1,2,3}}. Lets call each partition a piece. I need to efficiently calculate sum of the following term over all the partitioning.

(sum of all numbers in the piece)*(length of the piece)

Example: If set is A={1,3,6} then the pieces are:

B = {{1},{3},{6}} and value = (1)*1 +(3)*1 +(6)*1 = 10

B = {{1,3},{6}} and value = (1+3)*2+(6)*1 = 14

B = {{1},{3,6}} and value = (1)*1 +(3+6)*2 = 19

B = {{1,3,6}} and value = (1+3+6)*3 = 30

Total sum of values = 10+14+19+30 = 73.

I am not able to think of any better way other than simulating the required procedure. I need only the total sum and no intermediate values or partitioning. How can this be done efficiently?

P.S> This is not a homework question. I am a programming enthusiast curious to learn the theorems or algorithms related to above concept. I think this is more mathematical, so have asked here and not on stackoverflow.

Answer 1

After lots of scribbling on paper and with a friend's help I am here with a solution. Hope it is of some use to the community.

As I mentioned in comment, We had to find the pattern.

Example

A={1,3,6}

B = {{1},{3},{6}} and value = (1)*1 +(3)*1 +(6)*1 = 10

B = {{1,3},{6}} and value = (1+3)*2+(6)*1 = 14

B = {{1},{3,6}} and value = (1)*1 +(3+6)*2 = 19

B = {{1,3,6}} and value = (1+3+6)*3 = 30

Total sum of values = 10+14+19+30 = 73.

Constructing an Equation

Overall if we see, it is 1*(7)+3*(8)+6*(7) = 73.

Where did I get this [7,8,7] from? I counted manually by how much each element gets multiplied to form the result.Irrespective of the elements in set of size 3, the multiplication vector will be [7,8,7].

For various size of sets the multiplication vector is as follows:

1
3 3 
7 8 7 
15 18 18 15
31 38 40 38 31

and so on..

How to find the multiplication vector for any size of input set?

If you notice here, second half of the multiplication vector is the mirror image of the first half. So you need to find the pattern for the first half.

Let us call multiplication vector as count. Let n = size of the given set.

$count[0] = 2^{n}-1$

And for ith element(excluding first, till half of the array)

$count[i] = count[i-1]+ 2^{n-i-1} - 2^{i-1}$

For Programming Enthusiasts

1. Pay attention to Integer overflows.
2. Optimize the exponentiation by using modular arithmetic exponentiation.
3. The subtraction operation in $count[i] = count[i-1]+ 2^{n-i-1} - 2^{i-1}$ should be done using (a-b)%c = (a%c - b%c + c)%c.

Time Complexity

To calculate $(x^y)$ % p time complexity will be $O(logy)$. So for a set of size n the complexity will be O(nlogn)