Combinations

Combinations

Post by bwo » Wed, 01 Mar 2006 23:19:07


I am desperate for an algorithm which creates
boolean representations of combinations. A trivial
example would be:

3 COMB 4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
2 COMB 4
0 0 1 1
0 1 0 1
1 0 1 0
1 1 0 0
1 0 0 1
0 1 1 0

The wrinkle is that it has to be iterative to some degree,
because my application is actually looking at something
more like 35 COMB 42 and 35 ! 42 would result in a
26978328 by 42 boolean, which if tried in a single whack
would give a limit error. I tried to be clever and use recursion,
but that blew the stack out of the water at some point.

Any guidance would help clear several alligators out of
my swamp. Thanks.

bwo at aplborealis dot com

(No J solutions, please)
 
 
 

Combinations

Post by AA2e72 » Thu, 02 Mar 2006 00:25:03

A few years ago, an ex-colleague was working on the UK lottery; he
generated all the combinations in record time, writing them to a file. As
far as I recall, his inspiration for the COMB code came from:

Introduction to Algorithms by
Thomas H. Cormen, Stein Clifford, Charles E. Leiserson, Robert L. Rivest
ISBN:0262531968

Converting to Boolean (using the minimum number of bits)is
straightforward:

((1+{ceiling}2{log}n)/2)

where n is an integer. Or you could just use 11 []dr n (APL+Win)

 
 
 

Combinations

Post by bwo » Thu, 02 Mar 2006 03:02:18

Clarification: The boolean result is superfluous to
my needs, since I would use it to select integers
anyway. So 35 COMBS 42 would geterate 35
integers in the range 1-42. Since my application
iterates heavily, I would actually prefer COMBS
to return a single vector. But of course it has to
not repeat the result of a previous call. One
direction I'm persuing is using an expression like:
(7 #rho 7) #encode i
where <i> increments from 0 to 35 ! 42. That would
give me a unique result for eliminating 7 numbers from
#iota 42, but I can't figure out how to resolve the result
of the expression above to 7 meaningful (i.e. different)
integers in the 1-42 range.

Once again, grateful for any wisdom.
Brian
 
 
 

Combinations

Post by Dick Bowma » Thu, 02 Mar 2006 16:58:53


@j33g2000cwa.googlegroups.com:


I don't think I understand the question, but what's the difference between
what you want and 35?42.
 
 
 

Combinations

Post by AA2e72 » Thu, 02 Mar 2006 19:55:52

This might help:
35!42 will yield 26,978,328 combinations, as you say.
The first will be: +\35/1
The last will be: {high minus}35{take}+\42/1
Consider the binary patterns:
First: 42 {take}35/1 or decimal 4,398,046,510,976
Last : {high minus} 42{take} 35/1 or decimal 34,359,738,367

Your 26,978,328 combination are in range 4,398,046,510,976 (Min) to
34,359,738,367 (Max); however, not every increment yields a valid
combination.

Min & Max are elements of your results vector
Result{comes from} Min,Max
:while Min<Max {comes from}Max-1
:if 35=+/(42/2)encode}Max
Result{comes from} Result,Max
:endif
:endwhile

You have all the combinations, in decimal, say n. To get the actual
combination, do this:

(((42/2){encode} n) {times} (+\42/1)){without} 0

to get the binary pattern of the combination, to this:

(((42/2){encode} n)

You will find that there is no workspace big enough to return the result.
So:

1. Write the results to a file or database as it increments. If you write
the data away, you can process the loop with all decrements of up to 100
or up to 1000 or up to ? (depends on your workspace size)instead of 1 as
shown in the code.
2. Contrive a multiple/step between the Min and Max that will fit the
workspace (e.g. 1000 combinations at a time ?).

Problem solved?
 
 
 

Combinations

Post by microap » Thu, 02 Mar 2006 20:19:34


I'm a bit puzzled by your limit error. A 26978328 by 42 boolean should
be representable even in a 32-bit APL, provided the APL uses 1 bit per
boolean. It's around 141MB, and the total number of elements is well
within the 2*31 limit for total number of elements. Perhaps you get
the limit error on an intermediate result?

Anyway, here's one solution (I'll try pasting in Unicode from APLX - I
hope this will be readable):

COMB B;O
[1] O?
[2] R(B?)BB
[3] R?(+/R)=A)/[0]R
?
Line [2] would be very much more efficient if you use Quad-DR to create
the binary pattern rather than Encode, but I wanted to give a generic
APL solution.

Line [3] simply selects those rows which have the correct number of
bits set to 1.

If the intermediate results are too big for your APL interpreter to
handle, you can easily split it up by using a partial series for the
iota on line [2].

Richard Nabavi
MicroAPL
 
 
 

Combinations

Post by microap » Thu, 02 Mar 2006 20:41:44

Correction: Line 2 should of course have read:

R(B?)2*B

(That's what comes of hand-optimising without testing!)

Richard
 
 
 

Combinations

Post by RAV » Fri, 03 Mar 2006 00:02:52


> ? >

Just as a FYI, in APL+Win at least (which does use 1 bit booleans), the
maximum number of elements in an array seems limited to 214,748,352, so
an attempt to create a 26978328 by 42 boolean array signals a LIMIT ERROR.
*** Free account sponsored by SecureIX.com ***
*** Encrypt your Internet usage with a free VPN account from http://www.yqcomputer.com/ ***
 
 
 

Combinations

Post by Randy MacD » Sat, 04 Mar 2006 00:36:53

"AA2e72E" < XXXX@XXXXX.COM > wrote in




Why

+/x/1

instead of

{iota}x

--
-----------------------------------------------------------------------
|\/| Randy A MacDonald | you can't pay for it,
|/\| XXXX@XXXXX.COM | even if you want to.
BSc(Math) UNBF'83 Sapere Aude | APL: If you can say it, it's done..
Natural Born APL'er | Demo website: http://www.yqcomputer.com/
----------------------------------------------------(INTP)----{ gnat }-
 
 
 

Combinations

Post by bwo » Sat, 04 Mar 2006 10:11:11


[snip]

Yes, once I switched <min> and <max>.
Thanks
 
 
 

Combinations

Post by AA2e72 » Sat, 04 Mar 2006 17:38:49

OK; you have something to work on.
I have been looking at this and I believe there is a not only quicker
solution but also one that will allow you to request the combinations in
"groups". This will resolve any WS Full issues.
For instance,(your case) 35!42 has 36 groups, 4!15 has 78 groups which can
be sub-divided into 234 groups etc. A group is loosely a set of
combinations where the first n numbers are the same (the smaller n is the
smaller the number of groups, etc.).
I'll let you know if I can code this notion.
 
 
 

Combinations

Post by AA2e72 » Tue, 07 Mar 2006 19:54:45

I am sure you meant +\x/1 and not +/x/1.

+\x/1 is index-origin independent whereas {iota}x is not.
 
 
 

Combinations

Post by Tracke » Wed, 08 Mar 2006 02:21:57


But, +\x/1 is 6 to 16 times slower than #iota x, depending on the value of x.
 
 
 

Combinations

Post by AA2e72 » Wed, 08 Mar 2006 03:37:29

The OP did not specify what []io was; hence an io independent solution is
appropriate.

Besides, 16 times a few milliseconds is still milliseconds: the trade-off
is code that does not crash and produces the same result regardless of
[]io.
 
 
 

Combinations

Post by Tracke » Wed, 08 Mar 2006 04:07:08


IF you execute a code fragment once, you are correct, a few milliseconds does not matter. If however you execute it repetitively over and over, it can matter. It is good to know how efficient an algorithm executes. I like to write code []IO independent. And in fact, the following is still 4 times faster in APL+Win and produces the same result, both are []IO independent.

(~#IO)+#IOTA N VS +\N/1