Sunday, June 17, 2007

Inverting a permutation in 4 words

I discovered a useless but neat hack today. Suppose we wish to compute the inverse of a permutation specified as a sequence of integers, for example { 3 2 0 1 }.

We first turn the sequence { 3 2 0 1 } into an associative structure (a "mapping") which maps each integer to the corresponding element of the sequence. In Factor, this is done by wrapping the sequence in an enum:
{ 3 2 0 1 } <enum>

Now, we convert this enum into an association list, using the generic >alist word, which works on any associative structure:
{ 3 2 0 1 } <enum> >alist

The result is { { 0 3 } { 1 2 } { 2 0 } { 3 1 } }. We take advantage of the key property of association lists -- they're an ordered associative structure but also a sequence -- to sort this association list by value:
{ 3 2 0 1 } <enum> >alist sort-values

The result is { { 2 0 } { 3 1 } { 1 2 } { 0 3 } }.
Finally, we use the generic word keys, which works on any associative structure:
{ 3 2 0 1 } <enum> >alist sort-values keys .

The result is { 2 3 1 0 }.

To compose these permutations, we use map-with:
{ 2 3 1 0 } { 3 2 0 1 } [ swap nth ] map-with

As one would expect, we get { 0 1 2 3 }, the identity permutation.

8 comments:

Robbert van said...

That's a nice solution.

Here is a solution in the Enchlada language

[3;2;0;1] : ~ : 0 < {d} # :
[=3;=2;=0;=1] ~ : 0 < {d} # :
[0=3;1=2;2=0;3=1] : 0 < {d} # :
[3=0;2=1;0=2;1=3] 0 < {d} # :
[0=2;1=3;2=1;3=0] [0=2;1=3;2=1;3=0] {d} # :
[0=2;1=3;2=1;3=0] # :
[=2;=3;=1;=0] :
[2;3;1;0]

or [3;2;0;1] {invp=invp:~:0{d}#:}

Enchilada unites arrays and maps, that's why it is so short.

Anonymous said...

Correct me if I'm wrong, but I'm counting 7 words.

Slava Pestov said...

Anonymous: the body of the definition is 4 words: <enum> >alist sort-values keys

Boyko Bantchev said...

What is being discussed here is a standard operation, called ‘grade up’ in APL, J, and K, and as such its properties are well known, including it being applied to find the inverse of a permutation. (In APL, with its exotic alphabet, it is denoted by a sign called ‘delta-stile’ or ‘pine’: U+0x234b, depicted ⍋.)

If applied to a vector, grade up yields a permutation vector of its indices, showing how to permute the elements of the vector in order to sort them. There is also a related ‘sort with respect to’ operation, denoted the same way as grade up but applied dyadically. In fact, both the monad and the dyad generalize the usual sort operation as known from most languages.

Let me show how this works in J, where the grade up operator is denoted /: . Consider:

/: 'quota'
4 2 0 3 1

or

/: 2 4 1 3 0
4 2 0 3 1

The result 4 2 0 3 1 in both examples reads: “in order to obtain a sorted sequence, take the 4th, 2nd, 0th, 3rd, and 1st elements, in that order”.

Of course, as illustrated by the latter example, if the original vector itself is a permutation of 0..n-1, then the grading vector is the inverse of that permutation, i.e. /: is its own inverse:

/: 4 2 0 3 1
2 4 1 3 0

/:/: 2 4 1 3 0
2 4 1 3 0

More generally, /:/: yields a vector showing where to place each item of a sequence so that it becomes sorted:

/:/: 'quota'
2 4 1 3 0

The above reads: “in order to sort 'quota', put its 1st, 2nd, etc. items at positions 2, 4, etc. correspondingly”.

Call 2 4 1 3 0, obtained above, the sorting vector for 'quota'. Then the dyadic form of /: can be applied to get a sorted version of 'quota':

'quota' /: 2 4 1 3 0
aoqtu

Also, of course:

2 4 1 3 0 /: 2 4 1 3 0
0 1 2 3 4

In fact, the sorting vector 2 4 1 3 0 (or any index permutation vector) can be used to sort any other sequence of the same length, thus effectively applying the ordering relation of one sequence for sorting another. E.g.:

'abcde' /: 2 4 1 3 0
ecadb

(reading: “put 'a', 'b', 'c', 'd', 'e' at positions 2, 4, 1, 3, 0 correspondingly”.)

Even more generally, the elements of a list can be permuted to an order specified by another one. In the above example, instead of the sorting vector of 'quota', we could have used the string itself:

'abcde' /: 'quota'
ecadb

And in particular, in order to sort 'quota':

'quota' /: 'quota'
aoqtu

J has a short form for a dyadic application with the same arguments (which is in efect a monad: a particular case of the corresponding dyad). The last example is written more concisely:

/:~ 'quota'
aoqtu

The latter, or, say,

/:~ 2 4 1 3 0
0 1 2 3 4

exemplify but the simplest form of a sorting operation. However, the monadic and dyadic /: are each much more than that.

I hope to have shown that the ‘grade up’ and ‘sort with respect to’ operations are of general utility, only one facet of which is finding the inverse of a permutation.

Boyko Bantchev said...

What is being discussed here is a standard operation, called ‘grade up’ in APL, J, and K, and as such its properties are well known, including it being applied to find the inverse of a permutation. (In APL, with its exotic alphabet, it is denoted by a sign called ‘delta-stile’ or ‘pine’: U+0x234b, depicted ⍋.)

If applied to a vector, grade up yields a permutation vector of its indices, showing how to permute the elements of the vector in order to sort them. There is also a related ‘sort with respect to’ operation, denoted the same way as grade up but applied dyadically. In fact, both the monad and the dyad generalize the usual sort operation as known from most languages.

Let me show how this works in J, where the grade up operator is denoted /: . Consider:

/: 'quota'
4 2 0 3 1

or

/: 2 4 1 3 0
4 2 0 3 1

The result 4 2 0 3 1 in both examples reads: “in order to obtain a sorted sequence, take the 4th, 2nd, 0th, 3rd, and 1st elements, in that order”.

Of course, as illustrated by the latter example, if the original vector itself is a permutation of 0..n-1, then the grading vector is the inverse of that permutation, i.e. /: is its own inverse:

/: 4 2 0 3 1
2 4 1 3 0

/:/: 2 4 1 3 0
2 4 1 3 0

More generally, /:/: yields a vector showing where to place each item of a sequence so that it becomes sorted:

/:/: 'quota'
2 4 1 3 0

The above reads: “in order to sort 'quota', put its 1st, 2nd, etc. items at positions 2, 4, etc. correspondingly”.

Call 2 4 1 3 0, obtained above, the sorting vector for 'quota'. Then the dyadic form of /: can be applied to get a sorted version of 'quota':

'quota' /: 2 4 1 3 0
aoqtu

Also, of course:

2 4 1 3 0 /: 2 4 1 3 0
0 1 2 3 4

In fact, the sorting vector 2 4 1 3 0 (or any index permutation vector) can be used to sort any other sequence of the same length, thus effectively applying the ordering relation of one sequence for sorting another. E.g.:

'abcde' /: 2 4 1 3 0
ecadb

(reading: “put 'a', 'b', 'c', 'd', 'e' at positions 2, 4, 1, 3, 0 correspondingly”.)

Even more generally, the elements of a list can be permuted to an order specified by another one. In the above example, instead of the sorting vector of 'quota', we could have used the string itself:

'abcde' /: 'quota'
ecadb

And in particular, in order to sort 'quota':

'quota' /: 'quota'
aoqtu

J has a short form for a dyadic application with the same arguments (which is in efect a monad: a particular case of the corresponding dyad). The last example is written more concisely:

/:~ 'quota'
aoqtu

The latter, or, say,

/:~ 2 4 1 3 0
0 1 2 3 4

exemplify but the simplest form of a sorting operation. However, we have seen that the monadic and dyadic /: are each much more than that.

I hope to have shown that the ‘grade up’ and ‘sort with respect to’ operations are of general utility, only one facet of which is finding the inverse of a permutation.

Slava Pestov said...

Very interesting comment Boyko, thanks.

Boyko Bantchev said...

Thank you, Slava. By the way, for the sake of completeness, I should have added in my comment that, as implemented in APL etc., ‘grade up’ is a stable sorting operation, e.g.
⍋ 'Mississippi'
0 1 4 7 10 8 9 2 3 5 6
Sorry for posting twice – I thought I had not done it right the first time.

Anonymous said...

I saw this pattern in the Python cookbook a number of times.