Note that topswops form a graph between permutations.
So given topswops, we could define a routine which represents the
entire graph for permutations of length n:
swopvec=: 3 : 0
paths=. A."1&.> (! (<@swops@A. >:)&i. ])&> y
vec=. i.#paths
pairs=. ; 2 <\&.> paths
;{:@[`({.@[)`]}&.>/pairs,<vec
)
swopvec 1
0
swopvec 2
0 0
swopvec 3
0 1 0 5 2 0
swopvec 4
0 1 2 3 4 5 0 1 14 15 20 21 6 19 0 21 5 11 14 8 12 2 6 0
The result is a list of length n! representing a dag containing (n-1)!
trees. Each index into this list corresponds to the permutation index
(from A.) representing that permutation and the value indexed is the
next permutation in the sequence.
As an aside, monadic A. contains two kinds of functionality. The
first part normalizes non-permutations to attempt to make them
permutations. Here's an example of how that part works:
(([ ,~ -.~) 1 i.@+ >./) 1 2 4
0 3 1 2 4
In other words, it prefixes the argument list with any missing values.
Note that if all these missing values are smaller in value than
anything in the argument list they will have Anyways, once the
permutation has been normalized, we can compute the permutation index.
One way of doing that is like this:
({.@ /:@ /:\. +/ .* !@ <:@ #\.) 0 3 1 2 4
12
The left part of the inner product finds, for each element in the
argument the number of values to the right of the current value which
are smaller than it.
{.@ /:@ /:\. 0 3 1 2 4
0 2 0 0 0
The right part of the inner product finds the factorial of the number
of values to the right of the current value:
!@ <:@ #\. 0 3 1 2 4
24 6 2 1 1
And, or course, inner product just multiplies and adds, and the result
is a unique index into a list of all permutations of length n
(Clearly there are more efficient ways of doing this, but hopefully
this illustrates the concepts.)
Anyways, the swopvec values have some interesting properties (too many
to list here).
FYI,
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
