Yesterday I wrote about how you could use the
tr utility to find the dual of a modal logic expression. Today I’ll show how you could use
tr to work with permutations.
This post is a hack, and that’s the fun of it.
In the logic post we were using
tr to swap characters. More generally,
tr can permute characters. As mentioned before, it’s key that replacements are conceptually simultaneous. Otherwise none of this would work.
Here’s a homework problem from Abstract Algebra by Dummit and Foote.
Let σ be the permutation
1 → 3, 2 → 4, 3 → 5, 4 → 2, 5 → 1
and let τ be the permutation
1 → 5, 2 → 3, 3 →2, 4 → 4, 5 → 1.
Find the cycle decompositions of each of the following permutations: σ, τ, σ², στ, τσ, and τ²σ.
We won’t do all the parts of this problem, because that would be tedious. But we’ll do σ and στ.
A decomposition of a permutation factors the permutation into smaller permutations if possible. The algorithm to decompose a permutation starts by picking any element and finding how it cycles. Then it picks another element not in that cycle and finds its cycle. This repeats until we run out of elements. The original permutation is then equal to the product of these cyclic permutations.
We might as well start with 1. Let’s see why. In the problem above, σ sends the digits 12345 to the digits 34521.
echo 1 | tr 12345 34521
This prints 3. No surprise: 1 goes to 3.
Now where does 3 go?
echo 1 | tr 12345 34521 | tr 12345 34521
This says 5. And where does 5 go?
echo 1 | tr 12345 34521 | tr 12345 34521 | tr 12345 34521
It goes back to 1. So our first cycle is
(1 3 5)
Now let’s pick a number not in this cycle, say 2.
echo 2 | tr 12345 34521
So 2 goes to 4, and there’s no place left for 4 to go except back to 2. This means σ has the decomposition
(1 3 5)(2 4)
Now let’s do στ. This means do τ then do σ. At least that’s how I’m reading it, like function composition; some folks use the opposite convention.
Composing permutations corresponds to piping one
tr command into another. So we could see where 1 goes under στ as follows.
echo 1 | tr 1235 5321 | tr 12345 34521
This returns 1, so 1 is a fixed point. So our decomposition starts with
OK, so what about 2? We could find out with
echo 2 | tr 1235 5321 | tr 12345 34521 | | tr 1235 5321 | tr 12345 34521
but our commands are getting kinda long, and could get longer still.
Another approach would be to compute στ by seeing what it does to all numbers, not must one at a time.
echo 12345 | tr 1235 5321 | tr 12345 34521
returns 15423. So we could see where 2 goes using
echo 2 | tr 12345 15423
which tells us 2 goes to 5. We could see where 5 goes by adding another copy of our pipe to
tr on the end, or by changing
echo 2 to
echo 5. In any case 5 goes to 3, and 3 goes to 4.
So στ has the decomposition
(1)(2 5 3 4).
The next homework problem in Dummit and Foote ask for the decomposition of a permutation of size 15:
1 → 13, 2 → 2, 3 → 15, …
Our trick for using
tr won’t work without some modification because
tr 123… 13215…
would send 1 to 1, 2 to 3, 3 to 2, etc. However, we could do the problem by representing our numbers in hexadecimal.
tr 123… D2F…
In fact, the full permutation sends the numbers 1 through F to D2FEA6C341795B8.
Let’s define a shell alias to make things easier:
alias t='tr 123456789ABCDEF D2FEA6C341795B8'
Now we can find the cycle of 1 with the following commands.
echo 1 | t echo 1 | t | t echo 1 | t | t | t echo 1 | t | t | t | t
which tells us 1 is part of the cycle
(1 D 5 A)
Similarly we can find that 2 is a fixed point and 3 belongs to the cycle
(3 F 8)
and the final decomposition is
(1 D 5 A)(2)(3 F 8)(4 E B 7 C 9 4)
2 thoughts on “Permutations at the command line”
Looking forward to the next post, where you consider an expression like “tr xyz zxy” to be the Bash equivalent of writing down a permutation, and then you create an operation, called “multiply”, that takes two such expressions and outputs a single such expression corresponding to the product. :–)
(Me, I’d have to resort to Perl to do it, but there are people out there who could do it all in Bash.)
Heh. This use of tr reminds me of a 1982 effort some freshman classmates and I made to implement an Enigma emulator as a shell script (ideally, a giant 1-liner), where we initially tried using tr to implement the wheels and plugboard. The effort failed (mainly due to its being a huge time suck), but we learned lots in the attempt.
These days you “can” (perhaps not “should”) install an Enigma emulator as a character device: https://github.com/rafael-santiago/dev-enigma