{ 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> >alistThe 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-valuesThe 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-withAs one would expect, we get
{ 0 1 2 3 }, the identity permutation.
8 comments:
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.
Correct me if I'm wrong, but I'm counting 7 words.
Anonymous: the body of the definition is 4 words: <enum> >alist sort-values keys
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.
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.
Very interesting comment Boyko, thanks.
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.
I saw this pattern in the Python cookbook a number of times.
Post a Comment