Sign in to follow this  

Array processing

This topic is 3795 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all I need an alogrithm to help with what seems to be a relatively easy problem. I have array of n elements, and am required to sum all elements against the other in multiple combinations, so that all possible combinations are exhuasted. So array has 3 elements A, B and C. I need: A+B+C A+B A+C B+C Does anyone know of an algorithm that will help with this. The algorithm has to work with all levels of indices, ie a 4 element array A, B, C, D: A+B+C+D A+B A+C A+D B+C B+D C+D A+B+C A+B+D B+C+D...etc Am sure there will be something out there that can help with this.

Share this post


Link to post
Share on other sites
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)?

Share this post


Link to post
Share on other sites


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)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
Quote:
If it has *functions*, it 99.9% certainly supports recursion.


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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites

This topic is 3795 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this