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

Date: Tue, 30 Sep 2014 10:16:59 -0400
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 are the
letters 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 samples
for 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) 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.