Write each of the functions described below. On the due date, I'll provide lots of new test cases and have you give me the output of your functions for each.
As always, I highly recommend that, where helpful, you write helper functions not described below. This is often necessary if you wish to keep your functions as short and simple as possible. I wrote myself 11 helper functions not described below.
When we permute a sequence of objects, we change their order. For instance, a permutation of "abc" is "cba"; another is "bac".
Consider the permutation that takes "abc" and returns "cba". The position that was occupied by "a" is now occupied by "c". The position that was occupied by "b" is still occupied by "b". (That is, "b" is fixed.) The position that was occupied by "c" is now occupied by "a". So we might specify the permutation in this way:
"a" → "c", "b" → "b", "c" → "a"
Read this as: "a maps to c, b maps to b and c maps to a".
Here's a compact way to represent the permutation that takes "abc" to "cba":
(ac)(b)
We read from left to right; and inside each set of parentheses, we read from left to right. Thus we begin with "(ac)", and in that we go from "a" to "c". What does "(ac)" tell us? Since "c" follows "a", it tells us that "a" maps to "c"; and since "c" is the last letter, we wrap back around to the start and say that "c" maps to "a". Of course, then, "(b)" means that "b" maps to itself.
Note that, if a letter maps to itself, we typically don't include it. So the above permutation is typically given as just "(ac)", not "(ac)(b)".
Another example: "(acb)(de)" tells us that "a" maps to "c", "c" maps to "b", "b" maps to "a", "d" maps to "e" and "e" maps to "d".
Now let's have an example where we apply a permutation specified in this way. Let's say we begin with the sequence "abcdefg" and apply the permutation given by "(aeg)(bd)(cf)". We should get:
"edfbgca"
Take a moment to verify that this is correct. If you can't do it by hand, you won't be able to write code to do it.
Write me a function named apply_perm that takes a sequence of letters (like the "abc" and "abcdefg" from the examples above) and a permutation specified with the parentheses notation described above (like the "(aeg)(bd)(cf)" of the last example) and returns the result of that permutation applied to that sequence.
We will us assume for the moment that the permutation contains no more than one occurrence of any letter. Later we'll drop that assumption.
Let's agree to represent the permutation that leaves everything where it is as simply "()". (That's the identity permutation.) You may assume that in a permutation specified in the way described above, no letter appears more than once.
Dictionaries do seem like the obvious way to store and to apply a permutation. For instance, the dictionary {'a':'b', 'b':'c', 'c':'a'} tells us that 'a' maps to 'b', 'b' maps to 'c' and 'c' maps to 'a'.
Test Cases:
>>> apply_perm('', '()')
''
>>> apply_perm('abc', '()')
'abc'
>>> apply_perm('abc', '(ca)')
'cba'
>>> apply_perm('abc', '(abc)')
'bca'
>>> apply_perm('abcdefg', '(ac)(bef)(gd)')
'ceagfbd'
>>> apply_perm('abcdefg', '(aeg)(bd)(cf)')
'edfbgca'
>>> apply_perm('abcdefghijklmnop', '(adfg)(imnop)(kl)')
'dbcfegahmjlknopi'
Let's consider permutations that contain multiple occurrences of a letter. An example is "(abc)(cb)". Note that "c" occurs both in the first and second chunk. (Let's agree to call a sequence of letters flanked by parentheses a chunk.)
How do we interpret a permutation with multiple occurrences of a letter? I'll take "(abc)(cb)" as my example.
We read from left to right; and we begin with the leftmost chunk, which in this case is "abc". So chunk one tells us that "a" maps to "b".
Now move to the second chuck, the "(cb)" chunk, and look for a "b". It's there, and it maps "b" to "c".
So we have "a" mapped to "b" and then "b" mapped to "c". This is the same as if we simply mapped "a" to "c". The middleman "b" is dropped.
Now let's do "b". "(abc)" maps "b" to "c" and then "cb" maps that "c" to "b". So, when the middleman is dropped, "b" maps to "b".
Finally, "(abc)" maps "c" to "a"; and since "a" is not in "cb", "c" remains mapped to "a".
In sum (where as before the arrow means "maps to"): "a" → "c", "b" → "b", "c" → "a".
If you peek back at the previous function's description, you'll find that "(abc)(cb)" does precisely what "(ac)" did! They are thus equivalent permutations; they produce the same rearrangement. As should be clear, we now allow letters to occur in multiple chunks.
Write a function named eq_perms that takes a pair of permutations and determines whether that pair are equivalent.
Test Cases:
>>> eq_perms('()', '()')
True
>>> eq_perms('()', '()')
True
>>> eq_perms('(a)', '()')
True
>>> eq_perms('(a)', '(b)')
True
>>> eq_perms('()', '(ab)')
False
>>> eq_perms('()', '(ab)(ab)')
True
>>> eq_perms('(ab)(ba)', '()')
True
>>> eq_perms('(ab)', '(ba)')
True
>>> eq_perms('(abc)', '(acb)')
False
>>> eq_perms('(abc)(ca)', '(ca)(abc)')
False
>>> eq_perms('(adbc)(bd)', '(bd)(adbc)')
False
>>> eq_perms('(ac)(bd)(cafeg)(hamec)(cad)', '(ameghdbcf)')
True
>>> eq_perms('(df)(adg)(gadef)(hc)(cia)', '(dg)(fchiae)')
True
Two permutations are inverses of one another is one "undoes" what the other does. More precisely, two permutations are inverses if when we apply one to a sequence and then the other to that rearrangement, the sequence ends in the same order as it began.
So, for instance, the permutations "(acb)" and "(cab)" are inverses of one another. For if we apply the "(acb)" to the sequence "abc", we get "cab"; and if we apply "(cab)" to that, we get "abc", which is where we began.
Write me a function named inverse_perms that takes a pair of permutations and returns True if they are inverses of one another and False if they are not.
Test Cases:
>>> inverse_perms('()', '()')
True
>>> inverse_perms('(a)', '()')
True
>>> inverse_perms('(a)', '(b)')
True
>>> inverse_perms('(ab)', '()')
False
>>> inverse_perms('(ab)', '(ba)')
True
>>> inverse_perms('(abc)', '(abc)')
False
>>> inverse_perms('(abc)', '(bac)')
True
>>> inverse_perms('(cdeg)(abdef)', '(ecg)(fdba)')
True
>>> inverse_perms('(adfg)(bac)(iec)', '(dabceigf)')
True
>>> inverse_perms('(dagf)(bac)(iec)', '(idfagbce)')
False
Let's say we take a sequence and permute it. And then take the result and permute it that same way again. And then take the result and permute it that same way again. Etc. We will, if we continue lone enough, eventually arrive back at the original arrangement. (You might take a moment to think about why that has to be true.)
For instance, if we apply the permutation "(ab)" to the sequence "abc", we get "bac". And if we then apply "(ab)" to "bac", we get "abc". That's where we began!
Notice that in this case we had to apply the permutation "(ab)" twice to arrive back at the original arrangement.
Here's another example. The sequence is "abcdefg" and the permutation is "(abd)(cf)(bdfg)". Here's the sequence that gets us back to the original arrangement:
dfgaecb
acbdegf
dgfaebc
abcdefg
So in this case we had to apply the permutation "(abd)(cf)(bdfg)" four times to arrive back at the original arrangement.
Let's say that the number of times we must apply a permutation to get back to the original arrangement is the cycle length of that permutation.
Write a function named cycle_length that takes a permutation and returns how many times the permutation must be applied to a sequence to bring it back to its original arrangement. Note that I do not need to specify the sequence, for it can be any sequences that contains at least the letters in the permutation.
Test Cases:
>>> cycle_length('()')
1
>>> cycle_length('(ab)')
2
>>> cycle_length('(abc)')
3
>>> cycle_length('(ab)(ab)')
1
>>> cycle_length('(abd)(cf)(bdfg)')
4
>>> cycle_length('(spam)(and)(egs)')
8
We saw above that the permutations "(abc)(cb)" and "(ac)" are equivalent; that is, they rearrange a sequence in precisely the same way. Note too that the second, unlike the first, contains no more than one occurrence of any letter.
In general, every permutation that contains more than one occurrence of a letter is equivalent to one that does not contain multiples occurrences of any letter.
Write a function named compress_perm that takes a permutation and produces an equivalent permutation without repetition.
There are various forms that such an equivalent permutation might make, for there are always ways to rewrite a permutation. For instance, "(abc)(de)" is equivalent to each of these permutations (and others too): "(de)(abc)", "(cab)(de)", "(ed)(cab)". On quiz day, any of the correct answers will be accepted.
Test Cases:
>>> compress_perm('()')
'()'
>>> compress_perm('(a)')
'()'
>>> compress_perm('(a)(b)')
'()'
>>> compress_perm('(ab)')
'(ab)'
>>> compress_perm('(ab)(ab)')
'()'
>>> compress_perm('(abc)(bac)')
'()'
>>> compress_perm('(abc)(caf)(gd)(deh)')
'(ab)(cf)(gehd)'
>>> compress_perm('(bac)(dagbe)(iacdge)')
'(ciad)(beg)'