RE: Combinations & Permutations..... sort of

Thanks Vern.

The "pick K of N" is a pretty easy concept. For this application, however, K is a variable ranging 1..N. A bit different to apply. Permutations imply order and a permutation of 1&2 is different than 2&1 but they are equivalent in my exercise.

I wasn't working overtime yesterday but my brain sure was - at 3am, I had a thought about how to architect this which I hope to try today or tomorrow.

I can't recall the best data type for looping/subscripting - packed, binary, or ??? Any thoughts there?

I appreciate all the examples and suggestions.

Date: Mon, 29 Sep 2014 23:57:50 -0500
From: vhamberg@xxxxxxxxxxxxxxx
To: rpg400-l@xxxxxxxxxxxx
Subject: Re: Combinations & Permutations..... sort of

Hey Roger - it's been a long time since my math major days!

So Google is my friend - combinations are unordered sets from a larger
set - sounds like that's what you want. A number of combinations of n
items taken k at a time is n! / (k! * (n-k)!)

For the non-math folks, n! is n-factorial, or the product of all number
from 1 to n - 1 * 2 * 3 * ... n-1 * n - so 2! is 1 * 2 = 2
So if n = 2 and k = 1, 2C1 = (2*1)/(1*1) = 2 (a trivial case)

The sum of combination so n items taken k at a time, where k ranges from
0 to n, is 2**n - as one article says, the binomial theorem shows this -
and Pascal's triangle is an easy way to see it -

1 = 1
1+1 = 2
1+2+1 = 4 = 2C0 + 2C1 + 2C2
1+3+3+1 = 8
1+4+6+4+1 = 16

If you take out the one with 0, you have 2**n - 1
etc.

So by this, for 10 items, the total combinations is 2**10 - 1 = 1023.

To walk through this, you don't want to go backwards - if your items are
the letters from A - J, you don't want to get anything like B-A or I-D.

Does that help some? It should certainly make the job shorter!! Your
total is more along the lines of 2**22 - probably some zero-ish things
ignored.

I'm wondering if some kind of recursion would help - there are code
samples for generating these things out there.

Vern

On 9/29/2014 8:02 PM, Roger Harman wrote:

After some more thinking, I believe I've figured out the total.

For 10 items, there are 4,037,913 possible combinations.

Calculated as:
for x01 = 1 to 1
Total += 1
for x02 = 1 to 2
Total += 1
<and so on>
for x10 = 1 to 10
Total += 1
endfor
endfor
endfor

Smaller sample size is definitely in order.

From: roger.harman@xxxxxxxxxxx
To: rpg400-l@xxxxxxxxxxxx
Subject: Combinations & Permutations..... sort of
Date: Mon, 29 Sep 2014 17:17:55 -0700

Put your math hats on......

I'm looking at a means to *attempt* to auto-match payments to invoices. We do not want to apply payments to oldest first and end up with a partial payment or credit leftover.

Pick an arbitrary number of invoices for the attempt - say 10.

Any combination of 1 or more of these 10 invoices that total the payment amount would be considered a match.
Could be invoice 1, or 2, or.... Could be invoices 2 and 5 and 8..... etc.

I assume it's going to have to be a brute force approach but I'm stumped on the total # of possible matches. Combinations & permutations I understand (3 out of 10, etc) but this "1 or 2 or (1 and 2) or (2 and 5 and 8)" is giving me a mind block. I do know it's a big number and I'll likely cut back the sampling size.

Any suggestions or clarifications would be very welcome.

Thanks.



Roger Harman


COMMON Certified Application
Developer – ILE RPG on IBM i on Power





--
This is the RPG programming on the IBM i (AS/400 and iSeries) (RPG400-L) mailing list
To post a message email: RPG400-L@xxxxxxxxxxxx
To subscribe, unsubscribe, or change list options,
visit: http://lists.midrange.com/mailman/listinfo/rpg400-l
or email: RPG400-L-request@xxxxxxxxxxxx
Before posting, please take a moment to review the archives
at http://archive.midrange.com/rpg400-l.

--
This is the RPG programming on the IBM i (AS/400 and iSeries) (RPG400-L) mailing list
To post a message email: RPG400-L@xxxxxxxxxxxx
To subscribe, unsubscribe, or change list options,
visit: http://lists.midrange.com/mailman/listinfo/rpg400-l
or email: RPG400-L-request@xxxxxxxxxxxx
Before posting, please take a moment to review the archives
at http://archive.midrange.com/rpg400-l.