Add list.permutations

3 files changed, 48 insertions, 0 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index cd5516a..36ef33d 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -7,6 +7,7 @@
 - The `result` module gains the `lazy_or` and `lazy_unwrap` functions.
 - The `bool` module gains the `nand`, `nor`, `exclusive_nor`, and `exclusive_or` functions.
 - The `bit_builder` module gains the `from_string_builder` function.
+- The `list` modules gains the `permutations` function.
 
 ## v0.12.0 - 2020-11-04
 
diff --git a/src/gleam/list.gleam b/src/gleam/list.gleam
index 1af34e8..44d1510 100644
--- a/src/gleam/list.gleam
+++ b/src/gleam/list.gleam
@@ -1052,3 +1052,27 @@ pub fn partition(
 ) -> tuple(List(a), List(a)) {
   do_partition(list, categorise, [], [])
 }
+
+/// Return all the permutations of a list
+/// All values must be unique
+///
+/// ## Examples
+///
+///    > permutations([1, 2])
+///    [[1, 2], [2, 1]]
+///
+pub fn permutations(l: List(a)) -> List(List(a)) {
+  case l {
+    [] -> [[]]
+    _ ->
+      map(
+        l,
+        fn(x) {
+          filter(l, fn(y) { y != x })
+          |> permutations
+          |> map(append([x], _))
+        },
+      )
+      |> flatten
+  }
+}
diff --git a/test/gleam/list_test.gleam b/test/gleam/list_test.gleam
index ff94c3b..d9a4285 100644
--- a/test/gleam/list_test.gleam
+++ b/test/gleam/list_test.gleam
@@ -481,3 +481,26 @@ pub fn partition_test() {
   |> list.partition(int.is_odd)
   |> should.equal(tuple([1, 3, 5, 7], [2, 4, 6]))
 }
+
+pub fn permutations_test() {
+  [1, 2]
+  |> list.permutations
+  |> should.equal([[1, 2], [2, 1]])
+
+  let expected = [
+    [1, 2, 3],
+    [1, 3, 2],
+    [2, 1, 3],
+    [2, 3, 1],
+    [3, 1, 2],
+    [3, 2, 1],
+  ]
+
+  [1, 2, 3]
+  |> list.permutations
+  |> should.equal(expected)
+
+  ["a", "b"]
+  |> list.permutations
+  |> should.equal([["a", "b"], ["b", "a"]])
+}