I tried another solution.
Given a 5-tuple I calculate which 4-tuples obey the constraints, that is, I
combine each 2-tuple from the 5-tuple with each 2 tuple from the 47-tuple,
which is the complement of the corresponding 5-tuple.
The advantage is that most of the calculations are done only once.
As an option one can ignore the 4-tuple, but save its index in c4_52, although
this come with a performance price.
c2_5=: 2 comb 5
c2_47=: 2 comb 47
c4_52=: 4 comb 52
c5_52=: 5 comb 52
$cmpl5=: c5_52 ([, -.~)"1"_ 1 i.52 NB. Complement added to each 5-tuple
2598960 52
$frtpl=:,/c2_5 ,"1"(1 _) 5+c2_47 NB. All 4-tuples, 2 from the 5-tuple
and 2 from the rest
10810 4
$ c4_52 i. frtpl {"1"_ 1 (1000) {. cmpl5 NB. Index in c4_52
1000 10810
ts 'frtpl {"1"_ 1 (1000) {. cmpl5' NB. Full 4-tuple
0.4641848 5.373975e8
0.4641848 * 270725%1000 NB. Estimate for the complete
calculation
125.66643
But
ts 'c4_52 i. frtpl {"1"_ 1 (1000) {. cmpl5' NB. Index in c4_52,
quite slower
2.3893563 6.7528483e8
ts 'frtpl {"1"_ 1 (100000) {. cmpl5' NB. It scales rather well, dependent on
the memory
66.299325 6.8720004e10
(7!:2) 'frtpl {"1"_ 1 (200000) {. cmpl5' NB. This is my max
before I ran out of memory
137439480576
(7!:2) 'c4_52 i. frtpl {"1"_ 1 (200000) {. cmpl5' NB. Index in c4_52,
with even more memory
171798694656
R.E. Boss
-----Original Message-----
From: Programming <[email protected]> On Behalf Of Devon
McCormick
Sent: dinsdag 10 augustus 2021 17:19
To: J-programming forum <[email protected]>
Subject: Re: [Jprogramming] All selected hand possibilities (long)
I'm reducing the 103,776 numbers to a single score for each of the 270,725
combinations. I'm still playing around with exactly how to compute the score
but am simply summing the numbers (indexes into *allHands*) for now.
I'll take a look at your solution later today.
Thanks!
Devon
On Tue, Aug 10, 2021 at 10:41 AM R.E. Boss <[email protected]> wrote:
> I don't know if I understand the question well enough, but do you
> really want the 28,094,757,600 = 103,776*270,725 solutions to your question?
> My solution generates 10,377,600 in 0,41 sec, so it would take 1109
> sec for the complete answer.
>
>
> Here are my thoughts, expressed in J.
> c4_4=: (,.|.)2 comb 4
> c3_48=: 3 comb 48
> c4_52=: 4 comb 52
>
> $/:~"1 ,/^:2 (2{."1 t),"1 "3 c3_48{"1"1 _ (t=.c4_4{"(_ 1)
> 100{.c4_52)-.~ "1 i.52
> 10377600 5
> It scales rather well
>
> ts'/:~"1 ,/^:2 (2{."1 t),"1 "3 c3_48{"1"1 _ (t=.c4_4{"(_ 1)
> 100{.c4_52)-.~ "1 i.52'
> 0.4097461 1.0737812e9
>
> 0.4097461 * 28094757600 % 10377600
> 1109.2851
>
> The idea is you make the 6 variants of (some) all 4 comb 52
> possibilities and remove these 4 numbers from i.52.
> Then you construct all 3 comb 48 from the remaining numbers.
> Then you prepend the two first numbers which were omitted and sort
> each row.
>
> I hope my answers are correct and this helps you further.
>
>
> R.E. Boss
>
> It scales rather well:
> ts'/:~"1 ,/^:2 (2{."1 t),"1 "3 c3_48{"1"1 _ (t=.c4_4{"(_ 1)
> 1000{.c4_52)-.~ "1 i.52'
> 4.3197289 8.5905962e9
>
>
>
> -----Original Message-----
> From: Programming <[email protected]> On Behalf
> Of Devon McCormick
> Sent: maandag 9 augustus 2021 22:15
> To: J-programming forum <[email protected]>
> Subject: Re: [Jprogramming] All selected hand possibilities (long)
>
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
