Raul, I see I misunderstood your results. I was doing each of the six possibilities of each set of four independently, then adding them up. Now I see that my 17296 = your 103776%6.
It looks like your solution may be quite fast, able to calculate for the entire set in a little over two hours as opposed to the 36 hours I was estimating earlier. Thanks for the excellent solution! On Mon, Aug 9, 2021 at 5:59 PM Raul Miller <[email protected]> wrote: > 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 > -- Devon McCormick, CFA Quantitative Consultant ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
