solve_leetcode/problems/
0064-permutations.rs

1/// ``` txt
2///  Permutations for  1234
3///
4///       4, 3, 2
5///  0 => 0, 0, 0   => 1234
6///  1 => 1, 0, 0   => 2134
7///  2 => 2, 0, 0   => 3214
8///  3 => 3, 0, 0   => 4231
9///  4 => 0, 1, 0   => 1324
10///  5 => 1, 1, 0   => 2314
11///  6 => 2, 1, 0   => 3124
12///  7 => 3, 1, 0   => 4321
13///  8 => 0, 2, 0   => 1432
14///  9 => 1, 2, 0   => 2431
15/// 10 => 2, 2, 0   => 3412
16/// 11 => 3, 2, 0   => 4132
17/// 12 => 0, 0, 1   => 1243
18/// 13 => 1, 0, 1   => 2143
19/// 14 => 2, 0, 1   => 3241
20/// 15 => 3, 0, 1   => 4213
21/// ```
22pub mod hash_factorial {
23    pub fn solve(nums: Vec<i32>) -> Vec<Vec<i32>> {
24        let n = nums.len();
25
26        let count: usize = (1..=n).product();
27
28        let mut results = vec![nums; count];
29
30        for i in 0..count {
31            let result = &mut results[i];
32
33            let mut v = i;
34            for j in (2..=n).rev() {
35                let remainder = v % j;
36
37                if remainder != 0 {
38                    let start = n - j;
39                    result.swap(start, start + remainder);
40                }
41
42                v = (v - remainder) / j;
43            }
44        }
45
46        results
47    }
48}
49
50pub mod flat_map {
51    pub fn solve(nums: Vec<i32>) -> Vec<Vec<i32>> {
52        struct State {
53            choices: Vec<i32>,
54            result: Vec<i32>,
55        }
56
57        let n = nums.len();
58
59        (0..n)
60            .fold(
61                vec![State {
62                    choices: nums,
63                    result: Vec::with_capacity(n),
64                }],
65                |results, _| {
66                    results
67                        .into_iter()
68                        .flat_map(|state| {
69                            let State { choices, result } = state;
70
71                            (0..choices.len())
72                                .map(|i| {
73                                    let mut choices = choices.clone();
74                                    let mut result = result.clone();
75                                    let num = choices.remove(i);
76                                    result.push(num);
77                                    State { choices, result }
78                                })
79                                .collect::<Vec<_>>()
80                        })
81                        .collect()
82                },
83            )
84            .into_iter()
85            .map(|state| state.result)
86            .collect()
87    }
88}
89
90pub mod backtracking {
91    fn backtrack(results: &mut Vec<Vec<i32>>, result: &mut Vec<i32>, choices: Vec<i32>) {
92        if choices.len() == 0 {
93            results.push(result.clone())
94        }
95
96        for (i, choice) in choices.iter().enumerate() {
97            result.push(*choice);
98
99            let mut choices = choices.clone();
100            choices.remove(i);
101
102            backtrack(results, result, choices);
103
104            result.pop();
105        }
106    }
107
108    pub fn solve(nums: Vec<i32>) -> Vec<Vec<i32>> {
109        let mut results = vec![];
110        let mut result = vec![];
111
112        backtrack(&mut results, &mut result, nums);
113
114        results
115    }
116}
117
118#[cfg(test)]
119mod tests {
120    use std::{collections::HashSet, iter::FromIterator};
121
122    #[test]
123    fn problem_0064() {
124        let algorithms = [
125            //
126            super::hash_factorial::solve,
127            super::flat_map::solve,
128            super::backtracking::solve,
129        ];
130        for solve in algorithms {
131            {
132                let permutations = solve(vec![1, 2, 3]);
133
134                let permutations: HashSet<Vec<i32>> = permutations.into_iter().collect();
135
136                let res: HashSet<Vec<i32>> = [
137                    [1, 2, 3],
138                    [1, 3, 2],
139                    [2, 1, 3],
140                    [2, 3, 1],
141                    [3, 1, 2],
142                    [3, 2, 1],
143                ]
144                .iter()
145                .map(|arr| arr.to_vec())
146                .collect();
147
148                assert_eq!(permutations, res);
149            }
150
151            {
152                let permutations = solve(vec![1, 2, 3, 4]);
153
154                let permutations: HashSet<Vec<i32>> = permutations.into_iter().collect();
155
156                let res: HashSet<Vec<i32>> = [
157                    [1, 2, 3, 4],
158                    [1, 2, 4, 3],
159                    [1, 3, 2, 4],
160                    [1, 3, 4, 2],
161                    [1, 4, 2, 3],
162                    [1, 4, 3, 2],
163                    [2, 1, 3, 4],
164                    [2, 1, 4, 3],
165                    [2, 3, 1, 4],
166                    [2, 3, 4, 1],
167                    [2, 4, 1, 3],
168                    [2, 4, 3, 1],
169                    [3, 1, 2, 4],
170                    [3, 1, 4, 2],
171                    [3, 2, 1, 4],
172                    [3, 2, 4, 1],
173                    [3, 4, 1, 2],
174                    [3, 4, 2, 1],
175                    [4, 1, 2, 3],
176                    [4, 1, 3, 2],
177                    [4, 2, 1, 3],
178                    [4, 2, 3, 1],
179                    [4, 3, 1, 2],
180                    [4, 3, 2, 1],
181                ]
182                .iter()
183                .map(|arr| arr.to_vec())
184                .collect();
185
186                assert_eq!(permutations, res);
187            }
188        }
189
190        let mut result = None;
191
192        for solve in algorithms {
193            let res = HashSet::<Vec<i32>>::from_iter(solve(vec![1, 2, 3, 4, 5]));
194
195            match result {
196                Some(ref m) => assert_eq!(&res, m),
197                None => result = Some(res),
198            }
199        }
200    }
201}
solve_leetcode/problems/0064-permutations.rs

solve_leetcode/problems/
0064-permutations.rs
