At Play with J: Giddyap
Vector 20:3, page 117
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 117
Giddyap¶
The OED doesn’t have a giddyap entry; the Concise Oxford Dictionary has a giddap entry; Webster 3 has an entry for giddap, giddyap, giddyup. I think it must be a children’s word; I don’t think I’ve ever heard it used by an adult.1 When I was 70 or so years younger I know that when I pretended I was riding a horse – which was surprisingly often – I swung my imaginary whip on my imaginary horse as I pranced about, shouting giddyap with every stroke of the whip. I find it to be a suitable title because the article deals with a problem concerning horseraces, and also treats of the speeding up of programs that solved the proposed problem. The answer to the problem turned out to be an old friend of mine.
I don’t recall now where it was that I found the problem, but when I ran across it, it sounded as if it might a suitable challenge for the J Forum. In any event, on September 25 I sent this message to the J Forum:
N horses enter a race. Given the possibility of ties, how many
different finishes to the horse race exist? Write a program
that shows all the possibilities.
By way of example: here is the solution by brute force for N=3.
There are 13 solutions. horses are named a, b and c. The
expression {{b,c},a} denotes a finish in which b and c tie for
first and a comes in next.
{a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, b, a}, {c, a,
b}, {a,{b,c}}, {{b,c},a}, {b,{a,c}},
{{a,c},b},{{c,{a,b}},{{a,b},c},{{a,b,c}}
Methods for finding how many different Finishes¶
There were over two dozen responses over the next two weeks. The first response misunderstood the problem, and assumed that a race with three horses was the only one to consider. Since I had already given the solution of this one, it was clear that more had to be done than to submit the number 13. The answers to the first question, the number of solutions, were various. The brute force way is good only for the first few number of horses – the answer for eight horses is already 545,835. The nicest early entry used a table of Stirling subset numbers and factorials to give the number of different finishes effectively:
] fc=:!i.9
1 1 2 6 24 120 720 5040 40320
] s8=:subsets 8
1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0
0 1 3 1 0 0 0 0 0
0 1 7 6 1 0 0 0 0
0 1 15 25 10 1 0 0 0
0 1 31 90 65 15 1 0 0
0 1 63 301 350 140 21 1 0
0 1 127 966 1701 1050 266 28 1
s8 +/ . * fc
1 1 3 13 75 541 4683 47293 545835
Here’s another way that uses curtailed binomial lists and the list of terms so far found:
1 +/ . * 1
1
1 2 +/ . * 1 1
3
1 3 3 +/ . * 1 1 3
13
1 4 6 4 +/ . * 1 1 3 13
75
1 5 10 10 5 +/ . * 1 1 3 13 75
541
Which can be done either iteratively or recursively.
Still another way to get the number of different finishes uses the Weighted Taylor coefficient adverb t: defined in the J Dictionary as:
The result of u t: k is (!k)*u t. k. In other words, the coefficients produced by t: are the Taylor coefficients weighted by the factorial. As a consequence, the coefficients produced by it when applied to functions of the exponential family show simple patterns. For this reason it is sometimes called the exponential generating function.
The exponential generating function for the our numbers is \((1/(2-\mathrm{e}^{n}))\) so we can write a function fn using it, modified by the Weighted Taylor adverb:
All of these methods are discussed in Sloane’s On-Line Encyclopedia of Integer Sequences, sequence 670.
Methods for representing all the possible Finishes¶
The method I used for representing all 13 of the finishes for a three-horse race was informal. Various methods were used in the J solutions. This is one of the J solutions for a three-horse race:
+-----+-----+-----+-----+-----+-----+----+----+----+----+----+----+---+
|a b c|a c b|b a c|b c a|c a b|c b a|a bc|bc a|ab c|c ab|b ac|ac b|abc|
+-----+-----+-----+-----+-----+-----+----+----+----+----+----+----+---+
Results using boxed arrays, like this, were relatively slow. Faster results were obtained using a list of post positions to show the finish, with the finish order of the horse in post position k given as the value of item k of the result. Here is how the finishes of a three-horse race are displayed using this method:
0 0 0 abc
0 1 1 a bc
1 0 0 bc a
0 0 1 ab c
0 1 0 ac b
1 0 1 b ca
1 1 0 c ab
0 1 2 a b c
0 2 1 a c b
1 0 2 b a c
1 2 0 c a b
2 0 1 b c a
2 1 0 c b a
I’ve appended to the right of each finish the order of finish of three horses a, b and c, having post positions 0, 1 and 2, respectively. Horses tied in a finish are shown by abutting letters – for example, a bc shows horse a in first place and horses b and c tied for second place.
The function to produce the finishes in this order is fin3, by Roger Hui:
rankings=: ,"1 0~@i. , /:"1@=@i.@>:
ext =: [: ,/ _1&,. {"2 1 rankings@#@~.@{.
fin3 =: ([: ; >./"1 <@ext/. ])@$:@<: ` (i.@(1&,)) @. (1&>:)
Here is his explanation:
To generate the finishes for n, fin3 first partitions the finishes for n-1 by the maximum ranks. Then for each partition with maximum rank m and each finish v therein, (_1,v) is indexed into the matrix ,"1 0~i.1+m (tieing the new competitor with each possible rank) and into the matrix /:"1=i.2+m (slotting the new competitor into each possible position ("no ties")).
Therefore, if c is a vector of the number of finishes with maximum ranks i.#c, the corresponding counts for 1+#c are: (c*1+i.#c) are the number of finishes for ranks i.#c coming from ties, and c*2+i.#c are the number of finishes for ranks 1+i.#c coming from non-ties. For example, for n=2:
each finish indexed into
max rank finishes ties nonties
0 0 0 0 0 1 0
0 1
1 0 1 0 1 0 1 2 0
1 0 0 1 1 0 2 1
0 1 2
There is 1 finish for max rank 0 and 2 finishes for max rank 1.
The new counts are for n=3 are:
And for n=4:
The following functions encode the algorithm:
ntie1=: 0: ,~ ] * 1&+@i.@#
ntie0=: 0: , ] * 2&+@i.@#
nfin2=: (ntie1 + ntie0)@$:@<: ` ((,1x)"0) @. (1&>:)
nfin2 1
1
nfin2 2
1 2
nfin2 3
1 6 6
nfin2 4
1 14 36 24
[end of Hui’s explanation].
In a race where there are no ties the order of finish is a permutation. Notice that the bottom six results give the permutation table of order 3. In the rankings function you see /:1@=@i. This is the “magical matrix” described in my last column (Vector 20.2, October 2003), and it is used in precisely the same way: to produce a table of permutations.
The results of the function nfin2 above give the number of finishes of n horses having k as the maximum rank. If we form a triangle from these results:
and ravel it,
we get a list that is sequence 19538 in (http://www.research.att.com/~njas/sequences/). It is described as “the number of ways n labelled objects can be distributed into k nonempty parcels”. I wanted to obtain a different triangle, one showing the number of finishes having each leading digit. An easy way to do this is to look at the first column of the table of order n, as found by fin3. Thus if one transposes table fin3 n, takes its head item, applies tally modified by the key adverb and reflexive to tally one would get the number of instances of each leading digit, in order.
This says that the digits 0, 1 and 2 occur 6, 5 and 2 times as leading digits, respectively, in the table of order 3. You can verify this by inspecting the table above. Here are the results for tables of order 1 through 7:
1
2 1
6 5 2
26 25 18 6
150 149 134 84 24
1082 1081 1050 870 480 120
9366 9365 9302 8700 6600 3240 720
I’ve submitted this triangle to Sloane’s Online Encyclopedia.
I’ve come across the sequence given by the row sums of the triangle above, namely
in several different contexts. In 1977 I found that it enumerates the number of different left arguments for APL’s dyad transpose2. In 2000 it enumerated the number of distinct basic lists, I called Blists, which mathematicians call preferential arrangements3. And now, here they come galloping again to enumerate horserace finishes!
1 It was shortly after writing this that I attended a Choral Christmas Spectacular at San Francisco’s Davies Symphony Hall with my granddaughter and wife, and heard 3000 adults singing the second stanza of a song called “Sleigh Ride”, which goes:
Giddyyap, giddyyap, giddyyap, let’s go. Let’s look at the show.
We’re riding in a wonderland of snow.
Giddyyap, giddyyap, giddyyap, it’s grand just holding your hand.
We’re gliding along with a song of a winter fairyland.
Notice the fourth variant in spelling of the key word
2 Eugene McDonnell, “How Shall I Transpose Thee? Let Me Count the Ways”, APL Quote Quad 8.1, September 1977.
3 Eugene McDonnell, “Blists in OLEIS”, Vector 17.1, July 2000.