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)

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)

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)

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

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

@j33g2000cwa.googlegroups.com:

I don't think I understand the question, but what's the difference between

what you want and 35?42.

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?

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?

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

Correction: Line 2 should of course have read:

R(B?)2*B

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

Richard

R(B?)2*B

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

Richard

> ? >

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/ ***

"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 }-

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 }-

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.

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.

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

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

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

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.

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.

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

2. Selection Criteria for Combination Box in DataSheet View

4. Sort number and letter combinations in a form in datasheet view

5. Can I select a combination of controls to sort records?

6. Rollback changes made to "1 to Many" records being edited in a mainform / subform combination.

8. Problems with select statement that is a combination of select and a variable

9. How to use combination of parameters in Access

10. Lookup Columns in ADP/SQL Server 2005 combination

11. Compare two form fields, prevent duplicate combination

12. Synchronized Combination Boxes with main and sub form.

13. Avoid duplicate combinations

14. combination of Keys like CTRL + W