Merge branch 'master' of kobert:/var/repos/babel

1 files changed, 45 insertions, 0 deletions

diff --git a/src/permutations.rs b/src/permutations.rs
new file mode 100644
index 0000000..7b8e4d3
--- /dev/null
+++ b/src/permutations.rs
@@ -0,0 +1,45 @@
+use permutohedron::{Heap, LexicalPermutation};
+
+pub trait PermutationGenerator {
+    fn permutations(n: u32) -> Vec<Vec<u32>>;
+}
+
+pub struct HeapsPermutations;
+
+impl PermutationGenerator for HeapsPermutations {
+    fn permutations(n: u32) -> Vec<Vec<u32>> {
+        Heap::<'_, Vec<u32>, _>::new(&mut (1..=n).collect()).collect()
+    }
+}
+
+pub struct LexicalPermutations {
+    state: Vec<u32>,
+    is_ended: bool,
+}
+
+impl Iterator for LexicalPermutations {
+    type Item = Vec<u32>;
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.is_ended {
+            None
+        } else {
+            self.is_ended = self.state.next_permutation();
+            Some(self.state.clone())
+        }
+    }
+}
+
+impl LexicalPermutations {
+    fn new(n: u32) -> Self {
+        Self {
+            state: (1..=n).collect(),
+            is_ended: false
+        }
+    }
+}
+
+impl PermutationGenerator for LexicalPermutations {
+    fn permutations(n: u32) -> Vec<Vec<u32>> {
+        Self::new(n).collect()
+    }
+}