|
Thanks Vern.however, K is a variable ranging 1..N. A bit different to apply.
The "pick K of N" is a pretty easy concept. For this application,
Send RPG400-L mailing list submissions to
rpg400-l@xxxxxxxxxxxx
To subscribe or unsubscribe via the World Wide Web, visit
http://lists.midrange.com/mailman/listinfo/rpg400-l
or, via email, send a message with subject or body 'help' to
rpg400-l-request@xxxxxxxxxxxx
You can reach the person managing the list at
rpg400-l-owner@xxxxxxxxxxxx
When replying, please edit your Subject line so it is more specific
than "Re: Contents of RPG400-L digest..."
*** NOTE: When replying to this digest message, PLEASE remove all text
unrelated to your reply and change the subject line so it is meaningful.
Today's Topics:
1. Re: Combinations & Permutations..... sort of (John Yeung)
2. Re: Combinations & Permutations..... sort of (Raul A Jager W)
3. Re: Combinations & Permutations..... sort of (Paul Raulerson)
4. RE: Combinations & Permutations..... sort of (Roger Harman)
5. RE: Combinations & Permutations..... sort of (Roger Harman)
----------------------------------------------------------------------
message: 1
date: Tue, 30 Sep 2014 11:29:32 -0400
from: John Yeung <gallium.arsenide@xxxxxxxxx>
subject: Re: Combinations & Permutations..... sort of
On Tue, Sep 30, 2014 at 11:21 AM, Roger Harman <roger.harman@xxxxxxxxxxx>
wrote:
Thanks Vern.however, K is a variable ranging 1..N. A bit different to apply.
The "pick K of N" is a pretty easy concept. For this application,
But Vern did account for the variability of K. 1023 *is* the answer
to your question.
Let's break it down:
There are 10 ways to choose 1 from 10.
45 ways to choose 2 from 10.
120 ways to choose 3 from 10.
210 ways to choose 4 from 10.
252 ways to choose 5 from 10.
210 ways to choose 6 from 10.
120 ways to choose 7 from 10.
45 ways to choose 8 from 10.
10 ways to choose 9 from 10.
1 way to choose 10 from 10.
10 + 45 + 120 + 210 + 252 + 210 + 120 + 45 + 10 + 1 = 1023.
Which is exactly what Vern said.
John Y.
------------------------------
message: 2
date: Tue, 30 Sep 2014 11:31:18 -0400
from: Raul A Jager W <raul@xxxxxxxxxx>
subject: Re: Combinations & Permutations..... sort of
This is one of the "NP complete" problems. It is very simple to solve,
but the number of combinations grows exponentialy.
If you can find an efficient solution, you will deserv a "Nobel price"
On 09/29/2014 08:17 PM, Roger Harman wrote:
Put your math hats on......We do not want to apply payments to oldest first and end up with a partial
I'm looking at a means to *attempt* to auto-match payments to invoices.
payment or credit leftover.
amount would be considered a match.
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
Could be invoice 1, or 2, or.... Could be invoices 2 and 5 and 8.....etc.
on the total # of possible matches. Combinations & permutations I
I assume it's going to have to be a brute force approach but I'm stumped
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
-- Este e-mail fue enviado desde el Mail Server del diario ABC Color --
-- Verificado por Anti-Virus Corporativo Symantec --
------------------------------
message: 3
date: Tue, 30 Sep 2014 15:33:29 +0000 (GMT)
from: Paul Raulerson <paul.raulerson@xxxxxxx>
subject: Re: Combinations & Permutations..... sort of
Wonderful fun stuff. :)?
Of course, you realize that the algorithm you choose to do this also
knocks down, usually pretty dramatically, the number of choices and
compares you have to deal with.?
For example, in English, here is roughly the way one of my AR packages
looks at and matches up payments and invoices.?
For payment 9999 in the amount of $999.99 from clientID 9999:
? ?For unpaid or partially paid invoices billed to clientID 9999,
? ? ? Sort by date, showing the oldest invoice first.
? ? ? Find exact match for payment? ?-> If yes, pay it.?
? ? ? ? No exact match
? ? ? ? ? Pay oldest invoice
? ? ? ? ? ?Repeat find of exact match
? ? ? ?
? ? ? All of payment applied?
? ? ? ? ?Yes, is there change left over?
? ? ? ? ? ? ?(varies by program, can range from putting into suspense
account to refund of overpayment to applying the overage to different
balances....)?
? ? ? ? ?No Change
? ? ? ? ? ? ?Apply payment transactions
....
Of course, it gets much more complex if you need to apply payments on
invoices for different interest rates, promotional payments,?
and ?many other issues, but running a select for exact match usually cuts
the run time down quite a bit.?
I realize in your case, you are?looking?got?not have any "change" left
over, so you may need to get more creative, for example, checking for an
exact match on 1/2 the payment - late fee, in cases where you are dealing
with?periodic payments, such as utilities or any consistent period
recurring billing.?
Hope that helps -?
Paul?
? ? ? ? ??
? ?
On Sep 29, 2014, at 11:58 PM, Vernon Hamberg <vhamberg@xxxxxxxxxxxxxxx>
wrote:
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.
------------------------------
message: 4
date: Tue, 30 Sep 2014 08:34:58 -0700
from: Roger Harman <roger.harman@xxxxxxxxxxx>
subject: RE: Combinations & Permutations..... sort of
Doubtful we'll implement Python. But, I do have it on my home machine.
May have to dust it off just to try this.
Thanks John.
Date: Tue, 30 Sep 2014 10:16:59 -0400are the
Subject: Re: Combinations & Permutations..... sort of
From: gallium.arsenide@xxxxxxxxx
To: rpg400-l@xxxxxxxxxxxx
On Tue, Sep 30, 2014 at 12:57 AM, Vernon Hamberg
<vhamberg@xxxxxxxxxxxxxxx> wrote:
So by this, for 10 items, the total combinations is 2**10 - 1 = 1023.
Correct.
To walk through this, you don't want to go backwards - if your items
samplesletters from A - J, you don't want to get anything like B-A or I-D.
Also correct.
I'm wondering if some kind of recursion would help - there are code
mailing listfor generating these things out there.
In most languages, probably recursion is indeed the way to go. Doing
it with loops requires either lots of "accounting" (because you're
basically implementing your own call stack, instead of letting the
compiler and operating system handle it), or perhaps worse yet, some
number of nested loops, which isn't very scalable. (So after you work
things out for n = 10, it's not easy to just say "OK, we'll try n = 12
now".)
However, even easier than recursion is a pre-existing library, if one
is available. ;)
For those who are open to it, Python (available for the i as
iSeriesPython) has support for this in its standard library:
from itertools import combinations
invoices = range(10)
print sum(len(list(combinations(invoices, i))) for i in range(1, 11))
The above code snippet prints 1023.
range(10) evaluates to the list [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]. I
just used it to get a list of 10 items (which I called invoices
above). In the longer expression in the last line, I used range(1,
11) to get the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] because those are
the numbers of items you'll be choosing (the "k" in "n-choose-k").
But mathematically, it would have been equivalent to just use
range(10) there as well (there's exactly 1 way to choose 0 items out
of 10, and also exactly 1 way to choose 10 items out of 10, so it
really doesn't matter which one you leave off).
Python's object-orientedness allows you to tackle Roger's problem more
directly, not just calculate the number of possibilities. Instead of
just a list of ten integers, if "invoices" were instead a list of
actual invoice objects, each defined with an "id" property and an
"amount" property; and "payment" were another object with an "amount"
property, you could do something like
from itertools import combinations
for i in range(1, 11):
for combo in combinations(invoices, i):
if payment.amount = sum(invoice.amount for invoice in combo):
print 'Match found:'
for invoice in combo:
print invoice.id
The above code snippet, assuming invoices and payment are
appropriately defined, finds all matching combinations of invoices,
where each combination has at least 1 and at most 10 invoices. (Note
in this case it's important to actually use range(1, 11) and not
range(10), because you're dealing with real invoices, not just
counting possibilities.)
John
--
This is the RPG programming on the IBM i (AS/400 and iSeries) (RPG400-L)
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.
------------------------------
message: 5
date: Tue, 30 Sep 2014 08:40:24 -0700
from: Roger Harman <roger.harman@xxxxxxxxxxx>
subject: RE: Combinations & Permutations..... sort of
Yep, the requirement to match (allocate) all or nothing throws a wrench
into it. Additionally, there may be a credit (or credits) against an
invoice (or invoices) which needs to be factored in before we start the
matching so we deal with net amounts owed.
To: rpg400-l@xxxxxxxxxxxxknocks down, usually pretty dramatically, the number of choices and
From: paul.raulerson@xxxxxxx
Subject: Re: Combinations & Permutations..... sort of
Date: Tue, 30 Sep 2014 15:33:29 +0000
Wonderful fun stuff. :)
Of course, you realize that the algorithm you choose to do this also
compares you have to deal with.
looks at and matches up payments and invoices.
For example, in English, here is roughly the way one of my AR packages
account to refund of overpayment to applying the overage to different
For payment 9999 in the amount of $999.99 from clientID 9999:
For unpaid or partially paid invoices billed to clientID 9999,
Sort by date, showing the oldest invoice first.
Find exact match for payment? -> If yes, pay it.
No exact match
Pay oldest invoice
Repeat find of exact match
All of payment applied?
Yes, is there change left over?
(varies by program, can range from putting into suspense
balances....)
No Changeinvoices for different interest rates, promotional payments,
Apply payment transactions
....
Of course, it gets much more complex if you need to apply payments on
and many other issues, but running a select for exact match usuallycuts the run time down quite a bit.
over, so you may need to get more creative, for example, checking for an
I realize in your case, you are looking got not have any "change" left
exact match on 1/2 the payment - late fee, in cases where you are dealing
with periodic payments, such as utilities or any consistent period
recurring billing.
wrote:
Hope that helps -
Paul
On Sep 29, 2014, at 11:58 PM, Vernon Hamberg <vhamberg@xxxxxxxxxxxxxxx>
payments to invoices. We do not want to apply payments to oldest first and
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
end up with a partial payment or credit leftover.
> >- say 10.
> > Pick an arbitrary number of invoices for the attempt
> >that total the payment amount would be considered a match.
> > Any combination of 1 or more of these 10 invoices
> > Could be invoice 1, or 2, or.... Could be invoices 2and 5 and 8..... etc.
> >approach but I'm stumped on the total # of possible matches. Combinations &
> > I assume it's going to have to be a brute force
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.
> >welcome.
> > Any suggestions or clarifications would be very
> >iSeries) (RPG400-L) mailing list
> > 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
> > To post a message email: RPG400-L@xxxxxxxxxxxxhttp://lists.midrange.com/mailman/listinfo/rpg400-l
> > To subscribe, unsubscribe, or change list options,
> > visit:
> > or email: RPG400-L-request@xxxxxxxxxxxxarchives
> > Before posting, please take a moment to review the
> > at http://archive.midrange.com/rpg400-l.mailing list
> >
>
--
This is the RPG programming on the IBM i (AS/400 and iSeries) (RPG400-L)
To post a message email: RPG400-L@xxxxxxxxxxxxmailing list
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)
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.
------------------------------
Subject: Digest Footer
--
This is the RPG programming on the IBM i (AS/400 and iSeries) (RPG400-L)
digest 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.
------------------------------
End of RPG400-L Digest, Vol 13, Issue 410
*****************************************
As an Amazon Associate we earn from qualifying purchases.
This mailing list archive is Copyright 1997-2024 by midrange.com and David Gibbs as a compilation work. Use of the archive is restricted to research of a business or technical nature. Any other uses are prohibited. Full details are available on our policy page. If you have questions about this, please contact [javascript protected email address].
Operating expenses for this site are earned using the Amazon Associate program and Google Adsense.
midrange.com
