Add list.combinations

3 files changed, 88 insertions, 1 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index d3607ed..66df392 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -7,7 +7,7 @@
 - The `dynamic` module gains the `tuple3`, `tuple4`, `tuple5`, `tuple6`
   functions and their typed equivalents `typed_tuple3`, `typed_tuple4`,
   `typed_tuple5`, `typed_tuple6`.
-- The `list` module gains the `drop_while`, `map_fold`, `take_while`, `reduce`,
+- The `list` module gains the `combinations_by`, `combinations_by_2`, `drop_while`, `map_fold`, `take_while`, `reduce`,
   `chunk`, `sized_chunk`, `last` and `scan` functions.
 - The `iterator` module gains the `index`, `iterate`, `zip`, `scan`, `last`,
   `take_while`, `drop_while`, `chunk`, `sized_chunk`, `intersperse`, `interleave`, `reduce`,
diff --git a/src/gleam/list.gleam b/src/gleam/list.gleam
index 17ee57d..873f5ad 100644
--- a/src/gleam/list.gleam
+++ b/src/gleam/list.gleam
@@ -1452,3 +1452,49 @@ pub fn last(list: List(a)) -> Result(a, Nil) {
   list
   |> reduce(fn(elem, _) { elem })
 }
+
+/// Return unique combinations of elements in the list
+///
+/// ## Examples
+///
+/// ```
+/// > combinations_by([1, 2, 3], 2)
+/// [[1, 2], [1, 3], [2, 3]]
+///
+///  > combinations_by([1, 2, 3, 4], 3)
+///  [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
+/// ```
+///
+pub fn combinations_by(items: List(a), n: Int) -> List(List(a)) {
+  case n {
+    0 -> [[]]
+    _ ->
+      case items {
+        [] -> []
+        [x, ..xs] -> {
+          let first_combinations =
+            map(combinations_by(xs, n - 1), with: fn(com) { [x, ..com] })
+          append(first_combinations, combinations_by(xs, n))
+        }
+      }
+  }
+}
+
+/// Return unique pair combinations of elements in the list
+///
+/// ## Examples
+///
+/// ```
+/// > combinations_by_2([1, 2, 3])
+/// [tuple(1, 2), tuple(1, 3), tuple(2, 3)]
+/// ```
+///
+pub fn combinations_by_2(items: List(a)) -> List(tuple(a, a)) {
+  case items {
+    [] -> []
+    [x, ..xs] -> {
+      let first_combinations = map(xs, with: fn(other) { tuple(x, other) })
+      append(first_combinations, combinations_by_2(xs))
+    }
+  }
+}
diff --git a/test/gleam/list_test.gleam b/test/gleam/list_test.gleam
index 5fe2dd5..294c9f4 100644
--- a/test/gleam/list_test.gleam
+++ b/test/gleam/list_test.gleam
@@ -653,3 +653,44 @@ pub fn last_test() {
   list.last([1, 2, 3, 4, 5])
   |> should.equal(Ok(5))
 }
+
+pub fn combinations_by_test() {
+  list.combinations_by([1, 2, 3], 0)
+  |> should.equal([[]])
+
+  list.combinations_by([1, 2, 3], 1)
+  |> should.equal([[1], [2], [3]])
+
+  list.combinations_by([1, 2, 3], 2)
+  |> should.equal([[1, 2], [1, 3], [2, 3]])
+
+  list.combinations_by([1, 2, 3], 3)
+  |> should.equal([[1, 2, 3]])
+
+  list.combinations_by([1, 2, 3], 4)
+  |> should.equal([])
+
+  list.combinations_by([1, 2, 3, 4], 3)
+  |> should.equal([[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]])
+}
+
+pub fn combinations_by_2_test() {
+  list.combinations_by_2([1])
+  |> should.equal([])
+
+  list.combinations_by_2([1, 2])
+  |> should.equal([tuple(1, 2)])
+
+  list.combinations_by_2([1, 2, 3])
+  |> should.equal([tuple(1, 2), tuple(1, 3), tuple(2, 3)])
+
+  list.combinations_by_2([1, 2, 3, 4])
+  |> should.equal([
+    tuple(1, 2),
+    tuple(1, 3),
+    tuple(1, 4),
+    tuple(2, 3),
+    tuple(2, 4),
+    tuple(3, 4),
+  ])
+}