Factor Language Blog

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.