I was actually treating Q as a real number. The solution is in line with that of Lochbaum [Q=:-pi _3.1415927 N=:7 (+/,#) Q* 2-~/\/: ~0, 1,~ 0 ?@#~ <:N _3.1415927 7
R.E. Boss > -----Original Message----- > From: [email protected] [mailto:programming- > [email protected]] On Behalf Of Dan Bron > Sent: zaterdag 9 mei 2015 0:56 > To: [email protected] > Subject: Re: [Jprogramming] Random distribution > > Or course! (He says with the benefit of hindsight and a clear explanation.) > > Yes, what I'm looking for is an efficient, analytic, closed form function which > takes i, N, Q and produces i { comb . > > I am certain it exists. I almost wish it were gray December again so I could > justify staying inside tomorrow and playing with the idea. (But instead I'm > gonna take a mini road trip with friends to some idyllic little town upstate and > picnic by a lake.) > > Thanks for all your help today! I really appreciate it. > > REB: don't think I've overlooked your solution, either. Now that I know rnd is > round I'm going to start exploring it. > > Please excuse typos; sent from a phone. > > > On May 8, 2015, at 4:09 PM, Marshall Lochbaum > <[email protected]> wrote: > > > > This algorithm is worth writing a bit more about, I guess. > > > > I'll set N=3 and Q=7 for all the examples. First, consider > > N (_1 , /:~@:? , ])&<: Q > > _1 1 2 6 > > consisting of a _1, then (N-1) strictly increasing integers in the set > > [0,Q-1), then (Q-1). Since all the numbers in the middle are greater > > than _1 but less than (Q-1), the whole list is strictly increasing, i.e. > > each element is strictly greater than the one before it. > > > > To get our final answer, we just apply (2 -~/\ ]) to the result. There > > were (N+1) numbers before, so there are now N numbers. Since the > numbers > > were strictly increasing, each of the differences must be at least 1. To > > find the sum of the numbers, consider what ([: +/ 2 -~/\ ]) does to a > > list: > > a b c d e > > (2 -~/\ ]) > > a-~b b-~c c-~d d-~e > > (+/) > > a-~b+b-~c+c-~d+d-~e > > = > > a-~(b-b)+(c-c)+(d-d)+e > > = > > e-a > > > > So the sum of the numbers is the difference of the first and last > > numbers of the random increasing list earlier. But those numbers are > > just _1 and (Q-1), and their difference is Q. > > > > As an aside, J knows this fact in some sense. Consider the inverse > > +/\ b. _1 > > (- |.!.0) :.(+/\) > > It happens that (- |.!.0) is equivalent to (2 -~/\ 0&,), which is > > equivalent to ({. , 2 -~/\ ]). This manipulation is a bit confusing but > > doesn't really change anything. Now using the definition of the inverse, > > a -: +/\ (- |.!.0) a > > a -: +/\ ({. , 2 -~/\ ]) a > > a -: +/\ ({.a) , 2 -~/\ a > > a -: ({.a) + 0 , +/\ 2 -~/\ a > > We want to isolate (+/ 2 -~/\ a), which is the last element of the sum > > This algorithm is worth writing a bit more about, I guess. > > > > I'll set N=3 and Q=7 for all the examples. First, consider > > N (_1 , /:~@:? , ])&<: Q > > _1 1 2 6 > > consisting of a _1, then (N-1) strictly increasing integers in the set > > [0,Q-1), then (Q-1). Since all the numbers in the middle are greater > > than _1 but less than (Q-1), the whole list is strictly increasing, i.e. > > each element is strictly greater than the one before it. > > > > To get our final answer, we just apply (2 -~/\ ]) to the result. There > > were (N+1) numbers before, so there are now N numbers. Since the > numbers > > were strictly increasing, each of the differences must be at least 1. To > > find the sum of the numbers, consider what ([: +/ 2 -~/\ ]) does to a > > list: > > a b c d e > > (2 -~/\ ]) > > a-~b b-~c c-~d d-~e > > (+/) > > a-~b+b-~c+c-~d+d-~e > > = > > a-~(b-b)+(c-c)+(d-d)+e > > = > > e-a > > > > So the sum of the numbers is the difference of the first and last > > numbers of the random increasing list earlier. But those numbers are > > just _1 and (Q-1), and their difference is Q. > > > > As an aside, J knows this fact in some sense. Consider the inverse > > +/\ b. _1 > > (- |.!.0) :.(+/\) > > It happens that (- |.!.0) is equivalent to (2 -~/\ 0&,), which is > > equivalent to ({. , 2 -~/\ ]). This manipulation is a bit confusing but > > doesn't really change anything. Now using the definition of the inverse, > > a -: +/\ (- |.!.0) a > > a -: +/\ ({. , 2 -~/\ ]) a > > a -: +/\ ({.a) , 2 -~/\ a > > a -: ({.a) + 0 , +/\ 2 -~/\ a > > We want to isolate (+/ 2 -~/\ a), which is the last element of the sum > > scan. Taking the tail of both sides, > > ({: a) -: {: ({.a) + 0 , +/\ 2 -~/\ a > > ({: a) -: ({.a) + {: +/\ 2 -~/\ a > > (({:a) - ({.a)) -: {: +/\ 2 -~/\ a > > (({:-{.) a) -: +/ 2 -~/\ a > > > > > > I'm not quite sure what you mean by inverting the enumeration function. > > (Note: the sorting isn't necessary for comb even though it is for (?), > > so the solution can be reduced to (N (] (2 -~/\ _1 , ,~)"_1 comb)&<: Q)) > > The part that's applied with rank _1 takes a combination and Q and > > produces the appropriate composition of Q. So given the i'th element of > > ((N-1) comb (Q-1)) it's easy to produce the i'th composition: > > N (] (2 -~/\ _1 , ,~) i{comb)&<: Q > > I suppose if you have a memory-efficient way to produce (i{comb) then > > this gives you an efficient way to get the i'th composition. > > > > Marshall > > > >> On Fri, May 08, 2015 at 03:30:29PM -0400, Dan Bron wrote: > >> Marshall wrote: > >>> V =: N (2 -~/\ _1 , /:~@:? , ])&<: Q > >> > >> BINGO. Thank you! > >> > >> So you're creating an ordered list of <:N unique numbers less than <:Q, > >> bookended with _1 and <:Q, and taking the *gaps between these > numbers* as > >> the vector V. > >> > >> I have a vague intution of why the sum of any such bookended vector of > gaps > >> must necessarily be identically equal to N, but can you spell it out for > >> me? > >> > >>> require 'stats/base' > >>> 3 (] (2 -~/\ _1 , /:~@] , [)"_1 comb)&<: 7 > >> > >> Also, you wanna take a whack at inverting your enumeration function > here? > >> That is, given an index i, produce the corresponding row from the table > >> 3 (] (2 -~/\ _1 , /:~@] , [)"_1 comb)&<: 7 . > >> > >> -Dan > >> > >> > >> ---------------------------------------------------------------------- > >> For information about J forums see > http://www.jsoftware.com/forums.htm > > ---------------------------------------------------------------------- > > For information about J forums see > http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
