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
