We're answering two questions:
- How does the Steinhaus-Johnson-Trotter algorithm works?
- And how to implement it in Rust
The language doesn't matter. I've only choosen Rust, because I'm currently on my Rust arc.
The algorithm can be implemented by recursion, or by iteration. I'm covering the iterative approach, because - for me - it's easier to reason about it.
Let's dive in
Primer
Short primer what a permutation of a set is:
Assume we have the set (1, 2, 3). The permutation of this would be all the possible positional combinations of the members.
For example:
P1 -> 1 2 3
P2 -> 1 3 2
P3 -> 3 1 2
P4 -> 3 2 1
P5 -> 2 3 1
P6 -> 2 1 3
Side note: The factorial of the size of the set represents the maximum permutation:
len(permutate(1, 2, 3)) == factorial(len((1, 2, 3)))
SJT explained
In SJT, integers are bound to "directions", where they can point to the left or right.
At initialization, all integers are pointing to the left, like that:
<1 <2 <3
And under certain conditions (described down below), they can reverse the direction:
3> <2 <1
Those integers are defined as "mobile integers".
Definition: Mobile Integer
A mobile integer is ...
- able to swap positions with its adjacent integer
- not pointing to an edge
- greater than the integer it points to
An edge is defined as the "end" of a set:
Edge
v
| <1 <2 <3 |
^
Edge
And given this constellation:
<2 <1 3>
There are no mobile integers, since:
- "2" points to an edge (Rule 2)
- "1" is not greater than the integer it points to (Rule 3)
- "3" points also to an edge
Basic algorithm
- Find largest mobile integer (k)
- Swap the position of (k) with the integer, it points to
- Reverse the direction of all integers that are greater than (k)
Exit rule: If there are no mobile integers, the algorithm is done
Example (Step by Step)
The following example is split into each permutation step. P<number> indicates the current permutation.
And (Step n) corresponds to the steps from the paragraph Basic algorithm.
Init <1 <2 <3 // initialize the direction of all integers, so they're pointing to the left
P1 <1 <2 <3 // (Step 1) find the highest mobile integer, which is "3"
P2 <1 <3 <2 // (Step 2) swap positions
<1 <3 <2 // (Step 3) since there's no integer larger than (k), we skip this step
<1 <3 <2 // (Step 1) again; "3" is the largest mobile integer
P3 <3 <1 <2 // (Step 2) swap again
<3 <1 <2 // (Step 3) no greater integer than (k), we skip it again
<3 <1 <2 // (Step 1) "3" isn't mobile, since it points to an edge. So we take "2"
P4 <3 <2 <1 // (Step 2) swap "2" with "1"
3> <2 <1 // (Step 3) "3" is larger than (k), so we reverse the direction of "3"
3> <2 <1 // (Step 1) since (Rule 3) of the definition, only "3" complies with the definition
P5 <2 3> <1 // (Step 2) "3" pointed to the right, so it swaps positions with "2"
<2 3> <1 // (Step 3) there's no integer larger than (k)
<2 3> <1 // (Step 1) "3" is the largest mobile integer again.
// Since "2" points to an edge, and "1" points to an larger integer
P6 <2 <1 3> // (Step 2) swap "3" with "1"
<2 <1 3> // (Step 3) there's no larger integer than (k), so we skip again
<2 <1 3> // (Step 1) there's no mobile integer anymore, because
// "2" & "3" are pointing to an edge; "1" points to an larger number
End // And without any mobile integers, the algorithm is terminated
Credits to cut-the-knot.org which helped me a lot, to understand the algorithm.
Implementation
We're walking through the full implementation step by step. You can view the complete implementation.
It is important to mention, that the following function is meant to generate permutations for vector indexing.
$ foo = ["A", "B", "C"]
$ apply_permutation_on_index(foo)
[["A", "B", "C"], ["A", "C", "B"], ["C", "A", "B"], ...]
Thats the reason why the function only takes one parameter, and assumes 0..n.
So adapt it to your personal needs.
Function Signature
1 fn permutation(n: usize) -> Vec<Vec<usize>> {
For example you want the permutations of (0, 1, 2):
With n you declare the size of the set. If you provide 3, it will generate (0, 1, 2).
Regarding the return type, it depends on your use case. So you might want a different return type for your project.
Side note: I'm sticking to the word "set" to be consistent - although the structure in Rust is a vector.
In this walkthrough, we declare that n = 3.
Initialization
2 let mut perm: Vec<usize> = (0..n).collect(); // generating the "set"
3 let mut direction: Vec<i32> = vec![-1; n]; // initialize a vector with -1, which represents
// the direction of the values in `perm`
4 let mut result: Vec<Vec<usize>> = Vec::new(); // the permutated values will be stored here
5
6 let factorial = (1..=n).product(); // calculating the max possible permutation steps,
// so we can use it as an upper bound for the loop
7
8 result.push(perm.clone()); // storing the first permutation
At line 3 we created a structure, that looks like this: [-1, -1, -1].
The negative sign indicates, that the mobile integer is pointing to the left.
If there's no sign, then the mobile integer points to the right.
Loop: Inner Loop
10 for _ in 0..factorial {
11 let mut mobile_index = None;
12
13 for i in 0..n {
14 if (direction[i] == -1 && i > 0 && perm[i] > perm[i - 1])
15 || (direction[i] == 1 && i < n - 1 && perm[i] > perm[i + 1])
16 {
17 if mobile_index.is_none() || perm[i] > perm[mobile_index.unwrap()] {
18 mobile_index = Some(i);
19 }
20 }
21 }
At line 10 we're looping 5 times: for _ in 0..6.
But why only five times? Since the maximum permutation step is 3! == 6?
Because we already saved the first permutation at line 8.
At line 11 our mobile_index represents (k), as described in the paragraph Basic algorithm.
The inner loop at line 13 resolves into for i in 0..3, which corresponds to our "set" of 0, 1, 2
At line 14 & 15 we have a few conditions. To make this easier, we look into the first iteration,
where i = 0:
// i = 0; n = 3
if (direction[i] == -1 // IF the direction of `i` points to the left
&& i > 0 // AND `i` is greater than 0 (our leftmost edge)
&& perm[i] > perm[i - 1]) // AND the current mobile integer of our "set" is greater than the left one
|| (direction[i] == 1 // OR the direction of `i` points to the right
&& i < n - 1 // AND `i` is smaller than the maximum integer in the "set"
// Side note: Since `0..n` is non-inclusive, we have to subtract by one,
// to get the correct integer in the loop
&& perm[i] > perm[i + 1]) // AND the current mobile integer is greater than the right one
Since the condition will short-circuit to false, because 0 > 0 == false, it will skip the inner if block, and continue further.
Basically, this if block evaluates the rules from the paragraph Basic algorithm, and searches for a mobile integer.
Let's proceed with the inner if block. Where we assume i = 1:
// i = 1
if mobile_index.is_none() // IF mobile_index contains no value
|| perm[i] > perm[mobile_index.unwrap()] { // OR the current mobile integer is
// greater than last mobile integer
mobile_index = Some(i); // Store the current mobile integer
Since mobile_index contains no value, we store 1 in it. The next iteration will be i = 2, and it will overwrite the mobile_index value.
Which now proceeds further ahead.
Loop: Swaps
23 let mobile_index = match mobile_index {
24 Some(index) => index,
25 None => break,
26 };
27
28 let new_index = (mobile_index as isize + direction[mobile_index] as isize) as usize;
29 perm.swap(mobile_index, new_index);
30 direction.swap(mobile_index, new_index);
At line 23 - 26 we got the exit condition, as described in Basic algorithm.
When there's no mobile index, it breaks the outer loop and returns the result.
At line 28, the code can be broken down to: new_index = mobile_index + direction[mobile_index].
If we assume mobile_index = 2, the variable results into: new_index = 2 + -1 -> new_index = 1.
After that, in line 29 & 30, we perform the swaps:
// pre swap:
// perm = [0, 1, 2]
// direction = [-1, -1, -1]
perm.swap(2, 1);
direction.swap(2, 1);
// post swap:
// perm = [0, 2, 1]
// direction = [-1, -1, -1]
The perm and direction structures are tied together, so we have to modify both.
Loop: Reverse Direction
32 let moved_value = perm[new_index];
33
34 for i in 0..n {
35 if perm[i] > moved_value {
36 direction[i] *= -1;
37 }
38 }
39 result.push(perm.clone());
In this section, we have to evaluate, if there are any directions to reverse.
At line 32 we store the current position of the mobile integer (k). Following with a comparison,
if there's any integer higher than (k), we reverse the direction of the affected integers.
Finally, we append the current permutation to our result vector. And if the exit condition is met, if will return the final value.
Note on this Implementation
This implementation is not optimized, since there are a few clone() scattered around, and might
degrade performance.
And I somehow have the gut feeling, that this can be solved without an additional direction vector.
But this may be a task for a different day.
Complete Implementation
1 fn permutation(n: usize) -> Vec<Vec<usize>> {
2 let mut perm: Vec<usize> = (0..n).collect();
3 let mut direction: Vec<i32> = vec![-1; n];
4 let mut result: Vec<Vec<usize>> = Vec::new();
5
6 let factorial = (1..=n).product();
7
8 result.push(perm.clone());
9
10 for _ in 0..factorial {
11 let mut mobile_index = None;
12
13 for i in 0..n {
14 if (direction[i] == -1 && i > 0 && perm[i] > perm[i - 1])
15 || (direction[i] == 1 && i < n - 1 && perm[i] > perm[i + 1])
16 {
17 if mobile_index.is_none() || perm[i] > perm[mobile_index.unwrap()] {
18 mobile_index = Some(i);
19 }
20 }
21 }
22
23 let mobile_index = match mobile_index {
24 Some(index) => index,
25 None => break,
26 };
27
28 let new_index = (mobile_index as isize + direction[mobile_index] as isize) as usize;
29 perm.swap(mobile_index, new_index);
30 direction.swap(mobile_index, new_index);
31
32 let moved_value = perm[new_index];
33
34 for i in 0..n {
35 if perm[i] > moved_value {
36 direction[i] *= -1;
37 }
38 }
39 result.push(perm.clone());
40 }
41 result
42 }