Array processing

What language are you using? And what representation do you want for the result? A list of sums? A single, huge sum of sums? An array of sums? And since this is probably homework, do you have a partial solution to build on (don't want to make your homework for you)?

HINT- each element in the array should be represented as a bit in an n digit binary number and you can walk all the sum combinations by walking the binary numbers upto (2^n)-1 (starting at either 0 if its valid or 1)

Hi Guys

No this is not homework...although it is work related.

The language is PL/SQL with PL/SQL tables. Not after a solution, just an existing algorithm that I can then implement.

Good idea about representing each element as a binary number, unfortunately Oracle doesn't provide this facility.

garyfletcher -
I didn't have much time to fully analyze your problem, but if you are using C++ I would investigate the prev_permutation and next_permutation predicate options. While those will only provide a single collection of permutations they could likely be used together to create a logical and clear solution for your problem.

Jeremy (grill8)

Quote:

Original post by garyfletcher Hi Guys No this is not homework...although it is work related. The language is PL/SQL with PL/SQL tables. Not after a solution, just an existing algorithm that I can then implement. Good idea about representing each element as a binary number, unfortunately Oracle doesn't provide this facility.

In any subset that you want to sum up, each element either is contained in the subset, or is not contained in it.

Thus, for each element, there are subsets that contain the element, and subsets that do not. The set of subsets consists of (all subsets that do not contain the element), and (for each subset in the previous, that subset unioned with the element).

Therefore, we can describe things recursively. To get all the subset sums of elements i through n, first get (recursively) all subset sums of elements i+1 through n, and then duplicate that list, adding element i to all sums in the duplicate. Be careful with the base case of your recursion: you need to include the empty subset for this to work right.

Afterwards you can (per your original requirements) throw out the empty subset, as well as all the ones consisting of a single element.

Cheers Zahlman, recusrion isn't really a PL/SQL facility (as far as I know), never read it in any books anyhow.

In the end I initially created a sub-set of the duplicates on a cetain level:

ab
ac
ad
ae..etc

Then used this as the basis for further processing.

From above had an outer loop (A, B, C, D, E), then if this was the initial time I was trying to make coimbinations in this outerloop, then make the relevant doubles.

If we already have the base then use this to make all other combinations:

abc
abd
abe...etc

When all of the outer loop is exhausted (inner loop = final one of outer loop(E)) then move on to next outer loop....B.

Do Same...make the base (doubles)

Bc
bd
be

Then the inner loop:

bcd
bce
bcde
bde
be...etc

Then c.....

You get the picture.

Seems to work fine. Although am sure there are more efficient algorithms.

Quote:

Original post by garyfletcher Cheers Zahlman, recusrion isn't really a PL/SQL facility (as far as I know), never read it in any books anyhow.

If it has *functions*, it 99.9% certainly supports recursion.

Quote:

In the end... Seems to work fine.

I strongly doubt it (to the extent that I can even understand what you're describing). The problem with nested-loop approaches to this sort of thing is that you need a varying number of nested loops. You can verify your results by checking for duplicates and by counting the results (see if you can figure out for yourself how many there should be).

Quote:

If it has *functions*, it 99.9% certainly supports recursion.

Since it supports arrays, recursive algorithm can be translated into stack based.

Zahlman.

Sorry you don't understand, my explination wasn't that great.

But, it does work, and without recursion.

The hard part is doing a combination like abde (ie. missing an array element), so that is why I had to have base combinations as explained. Then use these to drivr "down" deeper into the array.

If you're interested will send out the algorithm, with better explination?