Exercises marked with (*) require further reading/search beyond the suggested texts.
2. Sort the following genome using Bergeron's method:
+6 -1 -2 -7 -4 -8 -9 +5 +3
Answer:
The program in this link applies Algorithm 1 from Bergeron's sorting method shown in class. It sorts a permutations into one that has only positive values. To compile it a C# compiler is needed, e.g., Visual Studio, Mono (for Linux environments), and so on.
Below are the results for the above permutation, generated by the program:
After framing: 0 6 -1 -2 -7 -4 -8 -9 5 3 10
Score of current permutation: 6
Oriented pairs:
(0, -1), (6, -7), (-2, 3), (-4, 5), (-4, 3), (-9, 10),
Oriented pair used: (0, -1)
Permutation generated:
0 1 -6 -2 -7 -4 -8 -9 5 3 10
Score of this permutation: 6
Oriented pairs:
(1, -2), (-6, 5), (-2, 3), (-4, 5), (-4, 3), (-9, 10),
Oriented pair used: (6, -7)
Permutation generated:
0 6 7 2 1 -4 -8 -9 5 3 10
Score of this permutation: 4
Oriented pairs:
(7, -8), (-4, 5), (-4, 3), (-9, 10),
Oriented pair used: (-2, 3)
Permutation generated:
0 6 -1 -5 9 8 4 7 2 3 10
Score of this permutation: 4
Oriented pairs:
(0, -1), (6, -5), (-1, 2), (-5, 4),
Oriented pair used: (-4, 5)
Permutation generated:
0 6 -1 -2 -7 9 8 4 5 3 10
Score of this permutation: 4
Oriented pairs:
(0, -1), (6, -7), (-2, 3), (-7, 8),
Oriented pair used: (-4, 3)
Permutation generated:
0 6 -1 -2 -7 -4 -3 -5 9 8 10
Score of this permutation: 4
Oriented pairs:
(0, -1), (6, -7), (6, -5), (-7, 8),
Oriented pair used: (-9, 10)
Permutation generated:
0 6 -1 -2 -7 -4 -8 -3 -5 9 10
Score of this permutation: 4
Oriented pairs:
(0, -1), (6, -7), (6, -5), (-8, 9),
Permutation Selected:
0 1 -6 -2 -7 -4 -8 -9 5 3 10
------------
Score of current permutation: 6
Oriented pairs:
(1, -2), (-6, 5), (-2, 3), (-4, 5), (-4, 3), (-9, 10),
Oriented pair used: (1, -2)
Permutation generated:
0 1 2 6 -7 -4 -8 -9 5 3 10
Score of this permutation: 4
Oriented pairs:
(6, -7), (-4, 5), (-4, 3), (-9, 10),
Oriented pair used: (-6, 5)
Permutation generated:
0 1 -6 -5 9 8 4 7 2 3 10
Score of this permutation: 2
Oriented pairs:
(-6, 7), (-5, 4),
Oriented pair used: (-2, 3)
Permutation generated:
0 1 -6 -5 9 8 4 7 2 3 10
Score of this permutation: 2
Oriented pairs:
(-6, 7), (-5, 4),
Oriented pair used: (-4, 5)
Permutation generated:
0 1 -6 -2 -7 9 8 4 5 3 10
Score of this permutation: 4
Oriented pairs:
(1, -2), (-6, 5), (-2, 3), (-7, 8),
Oriented pair used: (-4, 3)
Permutation generated:
0 1 -6 -2 -7 -4 -3 -5 9 8 10
Score of this permutation: 2
Oriented pairs:
(1, -2), (-7, 8),
Oriented pair used: (-9, 10)
Permutation generated:
0 1 -6 -2 -7 -4 -8 -3 -5 9 10
Score of this permutation: 2
Oriented pairs:
(1, -2), (-8, 9),
Permutation Selected:
0 1 2 6 -7 -4 -8 -9 5 3 10
------------
Score of current permutation: 4
Oriented pairs:
(6, -7), (-4, 5), (-4, 3), (-9, 10),
Oriented pair used: (6, -7)
Permutation generated:
0 1 2 6 7 -4 -8 -9 5 3 10
Score of this permutation: 4
Oriented pairs:
(7, -8), (-4, 5), (-4, 3), (-9, 10),
Oriented pair used: (-4, 5)
Permutation generated:
0 1 2 6 -7 9 8 4 5 3 10
Score of this permutation: 2
Oriented pairs:
(6, -7), (-7, 8),
Oriented pair used: (-4, 3)
Permutation generated:
0 1 2 6 -7 -4 -3 -5 9 8 10
Score of this permutation: 4
Oriented pairs:
(2, -3), (6, -7), (6, -5), (-7, 8),
Oriented pair used: (-9, 10)
Permutation generated:
0 1 2 6 -7 -4 -8 -3 -5 9 10
Score of this permutation: 4
Oriented pairs:
(2, -3), (6, -7), (6, -5), (-8, 9),
Permutation Selected:
0 1 2 6 7 -4 -8 -9 5 3 10
------------
Score of current permutation: 4
Oriented pairs:
(7, -8), (-4, 5), (-4, 3), (-9, 10),
Oriented pair used: (7, -8)
Permutation generated:
0 1 2 6 7 8 4 -9 5 3 10
Score of this permutation: 2
Oriented pairs:
(8, -9), (-9, 10),
Oriented pair used: (-4, 5)
Permutation generated:
0 1 2 6 7 9 8 4 5 3 10
Score of this permutation: 0
Oriented pairs:
Oriented pair used: (-4, 3)
Permutation generated:
0 1 2 6 7 -4 -3 -5 9 8 10
Score of this permutation: 2
Oriented pairs:
(2, -3), (6, -5),
Oriented pair used: (-9, 10)
Permutation generated:
0 1 2 6 7 -4 -8 -3 -5 9 10
Score of this permutation: 4
Oriented pairs:
(2, -3), (6, -5), (7, -8), (-8, 9),
Permutation Selected:
0 1 2 6 7 -4 -8 -3 -5 9 10
------------
Score of current permutation: 4
Oriented pairs:
(2, -3), (6, -5), (7, -8), (-8, 9),
Oriented pair used: (2, -3)
Permutation generated:
0 1 2 3 8 4 -7 -6 -5 9 10
Score of this permutation: 2
Oriented pairs:
(8, -7), (4, -5),
Oriented pair used: (6, -5)
Permutation generated:
0 1 2 3 8 4 -7 -6 -5 9 10
Score of this permutation: 2
Oriented pairs:
(8, -7), (4, -5),
Oriented pair used: (7, -8)
Permutation generated:
0 1 2 6 7 8 4 -3 -5 9 10
Score of this permutation: 4
Oriented pairs:
(2, -3), (6, -5), (4, -3), (4, -5),
Oriented pair used: (-8, 9)
Permutation generated:
0 1 2 6 7 -4 5 3 8 9 10
Score of this permutation: 2
Oriented pairs:
(-4, 5), (-4, 3),
Permutation Selected:
0 1 2 6 7 8 4 -3 -5 9 10
------------
Score of current permutation: 4
Oriented pairs:
Oriented pairs:
(2, -3), (6, -5), (4, -3), (4, -5),
Oriented pair used: (2, -3)
Permutation generated:
0 1 2 3 -4 -8 -7 -6 -5 9 10
Score of this permutation: 2
Oriented pairs:
(3, -4), (-8, 9),
Oriented pair used: (6, -5)
Permutation generated:
0 1 2 3 -4 -8 -7 -6 -5 9 10
Score of this permutation: 2
Oriented pairs:
(3, -4), (-8, 9),
Oriented pair used: (4, -3)
Permutation generated:
0 1 2 6 7 8 -4 -3 -5 9 10
Score of this permutation: 2
Oriented pairs:
(2, -3), (6, -5),
Oriented pair used: (4, -5)
Permutation generated:
0 1 2 6 7 8 4 5 3 9 10
Score of this permutation: 0
Oriented pairs:
Permutation Selected:
0 1 2 3 -4 -8 -7 -6 -5 9 10
------------
Score of current permutation: 2
Oriented pairs:
(3, -4), (-8, 9),
Oriented pair used: (3, -4)
Permutation generated:
0 1 2 3 4 -8 -7 -6 -5 9 10
Score of this permutation: 2
Oriented pairs:
(4, -5), (-8, 9),
Oriented pair used: (-8, 9)
Permutation generated:
0 1 2 3 -4 5 6 7 8 9 10
Score of this permutation: 2
Oriented pairs:
(3, -4), (-4, 5),
Permutation Selected:
0 1 2 3 4 -8 -7 -6 -5 9 10
------------
Score of current permutation: 2
Oriented pairs:
(4, -5), (-8, 9),
Oriented pair used: (4, -5)
Permutation generated:
0 1 2 3 4 5 6 7 8 9 10
Score of this permutation: 0
Oriented pairs:
Oriented pair used: (-8, 9)
Permutation generated:
0 1 2 3 4 5 6 7 8 9 10
Score of this permutation: 0
Oriented pairs:
Permutation Selected:
0 1 2 3 4 5 6 7 8 9 10
------------
Final result:
0 1 2 3 4 5 6 7 8 9 10
Number of operations: 8
© 2015 Joao Meidanis