Hmm...
So, several things here.
One is that now when I look at the results I get, the two index lists
I generated are not equivalent:
someNdx -: someIndex
0
I have an inkling of why, but there's some other things worth mentioning here.
The most important of those things is that 103776 is the number of
values in the result corresponding to your description:
I want to find all hands possible using any two cards from a given row of *HCs
*but excluding those with either of the other two cards from the same row.
For example:
208005{HCs
15 22 33 44
row208005=: ({&15 22 33 44 L:0)@(I. ; (i.4)-.I.)"1 (2 comb 4) e."1~ i.4
row208005
+-----+-----+
|15 22|33 44|
+-----+-----+
|15 33|22 44|
+-----+-----+
|15 44|22 33|
+-----+-----+
|22 33|15 44|
+-----+-----+
|22 44|15 33|
+-----+-----+
|33 44|15 22|
+-----+-----+
c =: 5 comb 52
selhands =: 4 : 0
'in ex' =. y
(] #~ (# in) = (ex +/@:e."1 ]) -~ in +/@:e."1 ]) x
)
jasSel=:,/c&selhands"1 row208005
$jasSel
103776 5
But, also, thinking about this, my expressions were too complex.
Here's a simpler approach:
allHands=: 5 comb 52
HCs=: 4 comb 52
sNdx=: I.2=+/"1 +./(208005{HCs)=/allHands
And my result here contains the same combinations as the approach
suggested by pascal jasmin (though the ordering is different):
jasSel -:&(/:~) sNdx{allHands
1
And, comparing this to my previous suggestions:
HCmask=: (2 comb 4) e."1~ i.4
someNdx=: I.+./HCmask*/ .=+./"1(208005{HCs)=/allHands
someIndex=: 10{.I.+./4=HCmask+/ .=+./"1(208005{HCs)=/allHands
sNdx-:someNdx
1
sNdx-:someIndex
0
...
So, I had a goof in my initial suggestions. But I had a working
implementation also. Sadly, I also goofed up and said that those were
equivalent. I should have tested a bit more. Sorry about that.
And, that said, this approach is reasonably quick:
selthem=: ] {~ [: I. 2 = [: +/"1 [: +./ =/
timespacex '(208005{HCs) selthem allHands'
0.061196 8.38881e7
jasSel -:&(/:~) (208005 { HCs) selthem allHands
1
However, I have goofed up already in this thread, and it's possible
that I goofed up here and somehow overlooked my mistake as I was
copying things from my J session into this message. If you cannot
reproduce any of my results here, please let me know.
Thanks,
--
Raul
On Mon, Aug 9, 2021 at 4:15 PM Devon McCormick <[email protected]> wrote:
>
> Thanks for the responses.
>
> Raul, it looks like the expressions you posted are missing the exclusions
> part of the problem which we can see if substitute the values from my
> original example to replace ({.HCs):
> $I.+./HCmask*/ .=+./"1(a.{~15 22 33 44)=/allHands
> 103776
>
> Pascal's version looks like it is giving a result like we would expect:
> $tst1=. allHands selhands (15 22{a.);33 44{a.
> 17296
> ]rcix=. (]{~[:5&?#) tst1
> 1515605 651644 2267264 157894 933164
> a. i. rcix{allHands
> 15 22 29 36 41
> 15 22 26 37 47
> 4 11 15 22 50
> 15 18 22 32 43
> 15 22 26 38 43
>
> I modified "selhands" to return the indexes into "allHands" rather than the
> explicit results as this is more easily turned into a score.
> selhands=: 4 : 0
> 'in ex' =. y
> I. ((# in) = (ex +/@:e."1 ]) -~ in +/@:e."1 ]) x
> )
>
> I like the elegance of the expression; however, the performance does not
> appear to be better:
> ixs=. i.100 NB. Do only 100 cases
> 6!:2 'tst100=. (<allHands) selhands&.><"1 (<"1 ixs{,/inclIx{"1/HCs),.<"1
> ixs{,/exclIx{"1/HCs'
> 49.7256
> #,/inclIx{"1/HCs NB. How many altogether?
> 1624350
> 49.7256*100%~1624350 NB. Scale time up by total #%100 ->
> estimate of total time
> 807718
> 0 60 60 #: 49.7256*100%~1624350 NB. Estimated total time in h m s
> 224 21 57.7836
>
> Thanks again to both of you for looking at this.
>
> The sizes of the arguments make it easy to max out the 64GB RAM I have on
> my desktop machine and I have discovered that I can run no more than about
> three processes in parallel on the version I proposed earlier but this may
> be enough for a one-time invocation.
>
> Cheers,
>
> Devon
>
> On Mon, Aug 9, 2021 at 11:14 AM 'Pascal Jasmin' via Programming <
> [email protected]> wrote:
>
> > is this 10x faster than your original? selhands uses arbitrary length
> > include/exclude list where all of include, and any of exclude condition.
> >
> > c =. 5 comb 52
> >
> > selhands =: 4 : 0
> >
> > 'in ex' =. y
> >
> > (] #~ (# in) = (ex +/@:e."1 ]) -~ in +/@:e."1 ]) x
> >
> > )
> >
> > timex' c selhands 15 22 ; 33 44'
> >
> > 1.17982
> >
> >
> >
> >
> >
> > On Sunday, August 8, 2021, 04:42:30 p.m. EDT, Devon McCormick <
> > [email protected]> wrote:
> >
> >
> >
> >
> >
> > Hi,
> >
> > I'm stuck on getting decent performance for the following problem.
> > Say we have a list of all 5-card hands from a deck of 52 cards:
> > load '~addons/stats/base/combinatorial.ijs'
> > $allHands=. 5 comb 52
> > 2598960 5
> >
> > We also have a list of all 4-card combinations:
> > $HCs=. 4 comb 52
> > 270725 4
> >
> > I want to find all hands possible using any two cards from a given row of
> > *HCs
> > *but excluding those with either of the other two cards from the same row.
> >
> > For example, for this randomly-chosen row of *HCs*, which hands include the
> > first two but exclude the second two?
> > (]{~[:?#) HCs
> > 15 22 33 44
> > (#,+/) include=. 2=+/"1 allHands e."1 ] *15 22*
> > 2598960 19600
> > (#,+/) exclude=. 0=+/"1 allHands e."1 ] *33 44*
> > 2598960 480200
> >
> > So there are 17,296 hands we want:
> > +/include*.exclude
> > 17296
> >
> > Check five at random to verify that these look correct:
> > ]rcix=. (]{~[:5&?#) I. include*.exclude
> > 1002358 1165504 2176134 1960355 56685
> > rcix{allHands
> > 4 15 22 37 39
> > 5 15 22 34 45
> > 15 18 20 22 39
> > 12 15 22 27 39
> > 0 4 6 15 22
> >
> > These look good because all include (15,22) but exclude any of (33,44).
> >
> > However, this is only one possibility for this single row of *HCs* but we
> > have six variations for this row based on choosing all possible pairs of
> > indexes into the row of *HCs* to include,
> > |:inclIx=. 2 comb 4
> > 0 0 0 1 1 2
> > 1 2 3 2 3 3
> >
> > And six corresponding pairs to exclude (indexes into the row of *HCs*):
> > |:exclIx=. (i.4)-."1 ] 2 comb 4
> > 2 1 1 0 0 0
> > 3 3 2 3 2 1
> >
> > In the above example, we did the one of the six corresponding to *inclIx
> > *of
> > (0,1) and *exclIx *of (2,3). Is there a way to do all six sets for each
> > row of *HCs* compared to each row of *allHands*?
> >
> > We might start by reducing the sizes of our arrays by making them character
> > instead of integer:
> > allHands=. allHands{a. [ HCs=. HCs{a.
> >
> > However, we quickly see that we run out of memory for the expression we
> > would like to write:
> > include=. 2=+/"1 allHands e."1 / inclIx{"1 / HCs
> > |out of memory
> > | include=.2=+/"1 allHands e."1/inclIx{"1/HCs
> >
> > A little arithmetic shows us the extent of the problem:
> > (],*/) #&>(,/inclIx{"1/HCs);<allHands
> > 1624350 2598960 4221620676000
> > 10^.1624350*2598960
> > 12.6255
> >
> > So we have a 4-trillion-element intermediate result which is a bit much.
> >
> > Our immediate thought might be to do this in pieces by selecting successive
> > portions of the right-hand part (*HCs*) of this expression. We would like
> > to work on integral pieces for neatness, so we look at the prime factors of
> > the size of *HCs* and select the product of a couple of them to be the
> > "chunk size":
> > q:#HCs
> > 5 5 7 7 13 17
> > ixs=. (ctr*chsz)+i.chsz [ ctr=. 0 [ chsz=. */5 5
> >
> > [The expression for the next chunk would be
> > ixs=. (ctr*chsz)+i.chsz [ ctr=. >:ctr
> > and so on.]
> >
> > Timing how long one piece takes and scoring the results by simply adding up
> > their indexes into *allHands*, we get this:
> > 6!:2 'sel=. (2=+/"1 allHands e."1 / inclIx{"1 / ixs{HCs) *. 0=+/"1
> > allHands e."1 / exclIx{"1 / ixs{HCs'
> > 11.5105
> > scores=. 0$~#HCs NB. Initialize scores vector
> > 6!:2 'theseScores=. +/&>I.&.><"1 |:+./"1 ] 0 2 1|:sel'
> > 0.687056
> > 6!:2 'scores=. (theseScores) ixs}scores'
> > 6.4e_6
> > +/11.5105 0.687056 6.4e_6 NB. Total time per chunk
> > 12.1976
> > 12.1976*(#ixs)%~#HCs NB. Total estimated time
> > 132088
> > 0 60 60#:12.1976*(#ixs)%~#HCs NB. Estimated time: h m s
> > 36 41 27.8104
> >
> > So we should be able to do it this way in about 36 hours. Can someone
> > think of a faster method to accomplish this? The memory requirements seem
> > modest enough that I should be able to run five to ten processes
> > simultaneously on this to reduce the overall time but is there a way to
> > speed up the basic selection?
> >
> > Thanks,
> >
> > Devon
> >
> >
> > --
> >
> > Devon McCormick, CFA
> >
> > Quantitative Consultant
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> >
>
>
> --
>
> Devon McCormick, CFA
>
> Quantitative Consultant
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
