Created
January 14, 2022 16:40
-
-
Save jess-sol/6c589bd0c80c9b241dd8d2f5c5308157 to your computer and use it in GitHub Desktop.
Use Johnson-Trotter algorithm to compute all permutations of the digits of a number in Rust
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #[derive(Clone, Debug)] | |
| enum Direction { Left, Right } | |
| #[derive(Clone, Debug)] | |
| struct DirectionalDigit(Direction, usize); | |
| impl std::fmt::Display for DirectionalDigit { | |
| fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { | |
| match self.0 { | |
| Direction::Left => write!(f, "<{}", self.1), | |
| Direction::Right => write!(f, "{}>", self.1), | |
| } | |
| } | |
| } | |
| fn compute_permutations_of_digits(mut n: usize) -> Vec<usize> { | |
| // Turn num into array of digits | |
| let mut nums = Vec::with_capacity(n); | |
| while n > 0 { | |
| nums.push(DirectionalDigit(Direction::Left, n % 10)); | |
| n /= 10; | |
| } | |
| nums.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap()); | |
| // Calculate permutations based on Johnson-Trotter algorithm | |
| let mut perms = vec![]; | |
| loop { | |
| // Turn back into number | |
| let mut num = 0usize; | |
| for n in nums.iter().rev() { | |
| num = num * 10 + n.1; | |
| } | |
| // Save into perms | |
| perms.push(num); | |
| // Find largest mobile digit | |
| let mut found_mobile_digit = false; | |
| let mut largest_mobile_digit = DirectionalDigit(Direction::Left, 0); | |
| let mut largest_mobile_digit_index = 0; | |
| for (i, window) in nums[..].windows(2).enumerate() { | |
| if let [n1, n2] = window { | |
| if let DirectionalDigit(Direction::Right, ref n) = n1 { | |
| if n2.1 < *n && (!found_mobile_digit || *n > largest_mobile_digit.1) { | |
| found_mobile_digit = true; | |
| largest_mobile_digit_index = i; | |
| largest_mobile_digit = n1.clone(); | |
| } | |
| } | |
| if let DirectionalDigit(Direction::Left, ref n) = n2 { | |
| if n1.1 < *n && (!found_mobile_digit || *n > largest_mobile_digit.1) { | |
| found_mobile_digit = true; | |
| largest_mobile_digit_index = i + 1; | |
| largest_mobile_digit = n2.clone(); | |
| } | |
| } | |
| } else { | |
| unreachable!(); | |
| } | |
| } | |
| if !found_mobile_digit { | |
| break; | |
| } | |
| // Make swap | |
| match largest_mobile_digit { | |
| DirectionalDigit(Direction::Left, _) => { | |
| nums.swap(largest_mobile_digit_index, largest_mobile_digit_index - 1); | |
| } | |
| DirectionalDigit(Direction::Right, _) => { | |
| nums.swap(largest_mobile_digit_index, largest_mobile_digit_index + 1); | |
| } | |
| } | |
| // Flip direction of all numbers larger than the mobile digit | |
| for n in nums.iter_mut() { | |
| if n.1 > largest_mobile_digit.1 { | |
| n.0 = match n.0 { | |
| Direction::Left => Direction::Right, | |
| Direction::Right => Direction::Left, | |
| }; | |
| } | |
| } | |
| } | |
| perms | |
| } | |
| fn main() { | |
| println!("Permutations of 123: {:?}", compute_permutations_of_digits(123)); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment