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
