`I should probably have gone straight to Knuth, but here's what I`

`managed with`

`Fredman's account of the algorithm. The tacit version is surprisingly`

`easy!!!`

`Note that this algorithm does not in general produce the same`

`subsequence as`

`the Wikipedia alternative, but it is of equal length, and is a bit`

`quicker.`

`Also, the subsquence's indices are not available, so it is deficient`

`compared`

`to longascseq etc; the latter are /: -like while lisf and taclisf`

`(below) are`

not.

## Advertising

NB. Fredman/Knuth algorithm as in NB. https://dx.doi.org/10.1016%2F0012-365X%2875%2990103-X lisf =: 3 : 0 x =. y if. 2>#x do. x return. end. T =. {.x for_xj. }.x do. if. xj > {:T do. T =. T, xj else. m =. T I. xj NB. if. xj < m { T do. Slight impairment with this test T =. xj m } T NB. end. end. end. T ) NB. see how to do tacit amend/append xi in T NB. 10 ([ I.~ } ]`(,~)@.(>{:) ) 7 9 11 NB. 10 <: 11, so insert NB. 7 9 10 NB. 20 ([ I.~ } ]`(,~)@.(>{:) ) 7 9 11 NB. 20 > 11, so append NB. 7 9 11 20 doxj =: ([ I.~ } ]`(,~)@.(>{:) ) NB. amend T (rha) with xj (lha) taclisf =: doxj / @ |. NB. closed form on array q =: ?.~ 1000000 timer'(#; 10&{.) longascseq1 q' +-+----+------------------------------------------------+ |8|1971|647 1210 1309 1399 1450 1688 1993 2006 2349 2729| +-+----+------------------------------------------------+ timer'(#; 10&{.) lisf q' +-----+----+------------------------+ |4.238|1971|0 2 4 7 9 12 13 20 28 37| +-----+----+------------------------+ timer'(#; 10&{.) taclisf q' +-----+----+------------------------+ |4.742|1971|0 2 4 7 9 12 13 20 28 37| +-----+----+------------------------+ Space requirements are similar for all 3, at ~ 8.4 Mb, with lisf <~ taclisf <~ longascseq1 , in this case. Mike Please note that I've snipped earlier history (below) from this correspondence. On 15/09/2016 09:28, Erling Hellenäs wrote:

The Knuth reference can be downloaded here:http://www.mediafire.com/download/3btahsyzax4w7xp/Vol%2C3+SortingAndSearching-Donald+Knuth.pdfYoungs tableau is on page 47. /Erling On 2016-09-14 23:27, 'Mike Day' via Programming wrote:I suspect it's pretty near optimal. The wikipedia article points atFredman's paper:http://www.sciencedirect.com/science/article/pii/0012365X7590103Xanalysing an algorithm of Knuth's. He shows that it performs betterthann log2(n) - n log2 log2 (n) + O(n) rather than the O(n logn) cited for the function we've been looking at. I might have a play at tacit for the algorithm already discussed. Mike On 14/09/2016 14:57, Erling Hellenäs wrote:Any ideas about how you could make a substantially faster tacitsolution to this problem or how you could make this solutionsubstantially faster? /Erling

[ sorry, but I've snipped the rest - Mike] --- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm