fix list.permutation on lists with non unique item values (#358)

3 files changed, 113 insertions, 24 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 842c85d..dd0029f 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -2,13 +2,15 @@
 
 ## v0.24.1 - unreleased
 
+- Fixed a bug where `list.permutations` would not correctly permutate lists
+  with non-unique item values.
 - For `regexp.compile` unicode character properties are now used when
   resolving `\B`, `\b`, `\D`, `\d`, `\S`, `\s`, `\W`, and `\w` on target
   Erlang.
 - `list.sort` is now tail recursive and will no longer exceed the stack size
   on large inputs on target JavaScript.
-- `list.sort` is now a "stable" sort, meaning equal elements are sorted in
-  the same order that they appear in the input.
+- `list.sort` is now a "stable" sort, meaning elements which are equal in
+  regards to the given comparison function will keep their previous order.
 - Added functions `function.apply1` through `function.apply3` which help
   working with functions in pipelines.
 - Fixed a bug where `regex.scan` would not work correctly on utf8.
diff --git a/src/gleam/list.gleam b/src/gleam/list.gleam
index 268642d..9a875d0 100644
--- a/src/gleam/list.gleam
+++ b/src/gleam/list.gleam
@@ -1443,18 +1443,34 @@ pub fn partition(
 /// [[1, 2], [2, 1]]
 /// ```
 ///
+/// Notice, that this function is not tail recursive:
+///
+/// The execution limits on permutations are iterations rather than stack size;
+/// for a permutation with `10` items a non tail recursive algorithm will at
+/// worst built up a stack size of `10` before it goes back to `1` eventually,
+/// while a permutation of say `5_000` items will not compute, in reasonable
+/// time, despite not exceeding stack size.
+///
 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], _))
-        },
-      )
+      l
+      |> index_map(fn(i_idx, i) {
+        l
+        |> index_fold(
+          [],
+          fn(acc, j, j_idx) {
+            case i_idx == j_idx {
+              True -> acc
+              False -> [j, ..acc]
+            }
+          },
+        )
+        |> reverse
+        |> permutations
+        |> map(fn(permutation) { [i, ..permutation] })
+      })
       |> flatten
   }
 }
diff --git a/test/gleam/list_test.gleam b/test/gleam/list_test.gleam
index ec95af4..83cf60d 100644
--- a/test/gleam/list_test.gleam
+++ b/test/gleam/list_test.gleam
@@ -848,33 +848,104 @@ pub fn permutations_test() {
   |> list.permutations
   |> should.equal([[1, 2], [2, 1]])
 
-  let expected = [
+  [1, 2, 3]
+  |> list.permutations
+  |> should.equal([
     [1, 2, 3],
     [1, 3, 2],
     [2, 1, 3],
     [2, 3, 1],
     [3, 1, 2],
     [3, 2, 1],
-  ]
+  ])
 
-  [1, 2, 3]
+  [1, 2, 3, 4]
   |> list.permutations
-  |> should.equal(expected)
+  |> should.equal([
+    [1, 2, 3, 4],
+    [1, 2, 4, 3],
+    [1, 3, 2, 4],
+    [1, 3, 4, 2],
+    [1, 4, 2, 3],
+    [1, 4, 3, 2],
+    [2, 1, 3, 4],
+    [2, 1, 4, 3],
+    [2, 3, 1, 4],
+    [2, 3, 4, 1],
+    [2, 4, 1, 3],
+    [2, 4, 3, 1],
+    [3, 1, 2, 4],
+    [3, 1, 4, 2],
+    [3, 2, 1, 4],
+    [3, 2, 4, 1],
+    [3, 4, 1, 2],
+    [3, 4, 2, 1],
+    [4, 1, 2, 3],
+    [4, 1, 3, 2],
+    [4, 2, 1, 3],
+    [4, 2, 3, 1],
+    [4, 3, 1, 2],
+    [4, 3, 2, 1],
+  ])
 
   ["a", "b"]
   |> list.permutations
   |> should.equal([["a", "b"], ["b", "a"]])
 
-  // TCO test
-  case recursion_test_cycles > 2 {
-    // Permutation count:
-    // 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 = 40_320
-    // 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 = 362_800
-    True ->
-      [1, 2, 3, 4, 5, 6, 7, 8, 9]
-      |> list.permutations
-    False -> [[]]
-  }
+  [1, 1]
+  |> list.permutations
+  |> should.equal([[1, 1], [1, 1]])
+
+  [1, 1, 1]
+  |> list.permutations
+  |> should.equal([
+    [1, 1, 1],
+    [1, 1, 1],
+    [1, 1, 1],
+    [1, 1, 1],
+    [1, 1, 1],
+    [1, 1, 1],
+  ])
+
+  [1, 2, 2]
+  |> list.permutations
+  |> should.equal([
+    [1, 2, 2],
+    [1, 2, 2],
+    [2, 1, 2],
+    [2, 2, 1],
+    [2, 1, 2],
+    [2, 2, 1],
+  ])
+
+  ["a", "a", "a", "a"]
+  |> list.permutations
+  |> should.equal([
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+    ["a", "a", "a", "a"],
+  ])
 }
 
 pub fn window_test() {