fork download 
  1. defmodule Combinatorics do
  2.  
  3.   # === product ===
  4.  
  5.   @doc ~S"""
  6.   Cartesian Product of 2 Enumerables.
  7.   (At least 2nd Enumerable should be finite)
  8.  
  9.   ## Examples
  10.  
  11.     iex> Combinatorics.product([1, 2, 3], 1..3) |> Enum.to_list
  12.     [{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}]
  13.  
  14.     iex> Stream.iterate(1, &(&1+1)) |> Combinatorics.product(1..3) |> Enum.take(10)
  15.     [{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}, {4, 1}]
  16.   """
  17.   def product(enum1, enum2) do
  18.     product([enum1, enum2])
  19.   end
  20.  
  21.   @doc ~S"""
  22.   Cartesian Product of multi Enumerables.
  23.   (At least last Enumerable should be finite)
  24.  
  25.   ## Examples
  26.  
  27.     iex> Combinatorics.product([1..2, 3..4, 5..6]) |> Enum.to_list
  28.     [{1, 3, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6}, {2, 3, 5}, {2, 3, 6}, {2, 4, 5}, {2, 4, 6}]
  29.  
  30.     iex> Combinatorics.product([Stream.iterate(1, &(&1+1)), 1..3]) |> Enum.take(10)
  31.     [{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}, {4, 1}]
  32.   """
  33.   def product([]), do: []
  34.   def product([it|[]]), do: Stream.map(it, &{&1})
  35.   def product(its) when is_list(its) do
  36.     do_product(its, [[]]) |> Stream.map(&List.to_tuple(:lists.reverse(&1)))
  37.   end
  38.  
  39.   defp do_product([], vals), do: vals
  40.   defp do_product([x|xs], vals) do
  41.     do_product(xs, Stream.flat_map(vals, fn vs -> Stream.map(x, &[&1|vs]) end))
  42.   end
  43.  
  44.   # === combinations ===
  45.  
  46.   @doc ~S"""
  47.   Combinations - n-length tuples, in sorted order, no repeated elements.
  48.  
  49.   ## Examples
  50.  
  51.     iex> Combinatorics.combinations(1..4, 2) |> Enum.to_list
  52.     [{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}]
  53.  
  54.     iex> Combinatorics.combinations(1..4, 3) |> Enum.to_list
  55.     [{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}]
  56.   """
  57.   def combinations(_enum, 0), do: []
  58.   def combinations(enum, 1), do: Stream.map(enum, &{&1})
  59.   def combinations(enum, n) when is_integer(n) and n > 1 do
  60.     case next(enum) do
  61.       {:next, v, fun} -> &do_combinations({[fun], [v], :next, n - 1}, &1, &2)
  62.       _  -> []
  63.     end
  64.   end
  65.  
  66.   defp do_combinations(_, {:halt, term}, _fun), do: {:halted, term}
  67.   defp do_combinations(v, {:suspend, term}, fun) do
  68.     {:suspended, term, &do_combinations(v, &1, fun)}
  69.   end
  70.   defp do_combinations({[], _, _, _}, {:cont, term}, _), do: {:done, term}
  71.   defp do_combinations({fs, vals, _, 0}, {:cont, term}, fun) do
  72.     do_combinations({fs, vals, :back, 1}, fun.(List.to_tuple(:lists.reverse(vals)), term), fun)
  73.   end
  74.   defp do_combinations({funs = [f|fs], vals = [_|vs], :next, n}, acc = {:cont, _}, fun) do
  75.     case next(f) do
  76.       {:next, v, next_f} -> do_combinations({[next_f|funs], [v|vals], :next, n - 1}, acc, fun)
  77.       _ -> do_combinations({fs, vs, :back, n + 2}, acc, fun)
  78.     end
  79.   end
  80.   defp do_combinations({[f|fs], [_|vs], :back, n}, acc = {:cont, _}, fun) do
  81.     case next(f) do
  82.       {:next, v, next_f} -> do_combinations({[next_f|fs], [v|vs], :next, n - 1}, acc, fun)
  83.       _ -> do_combinations({fs, vs, :back, n + 1}, acc, fun)
  84.     end
  85.   end
  86.  
  87.   # === permutations ===
  88.  
  89.   @doc ~S"""
  90.   Permutations - full-length tuples, all possible orderings, no repeated elements.
  91.   Notice: parameter `enum` can be a List or a Range.
  92.  
  93.   ## Examples
  94.  
  95.     iex> Combinatorics.permutations([1, 2, 3]) |> Enum.to_list
  96.     [{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}]
  97.  
  98.     iex> Combinatorics.permutations(2..4) |> Enum.to_list
  99.     [{2, 3, 4}, {2, 4, 3}, {3, 2, 4}, {3, 4, 2}, {4, 2, 3}, {4, 3, 2}]
  100.   """
  101.   def permutations(enum) when is_list(enum) do
  102.     permutations(enum, length(enum))
  103.   end
  104.   def permutations(enum = %Range{}) do
  105.     permutations(enum, Enum.count(enum))
  106.   end
  107.  
  108.   @doc ~S"""
  109.   Permutations - n-length tuples, all possible orderings, no repeated elements.
  110.  
  111.   ## Examples
  112.  
  113.     iex> Combinatorics.permutations(1..4, 2) |> Enum.to_list
  114.     [{1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 3}, {2, 4}, {3, 1}, {3, 2}, {3, 4}, {4, 1}, {4, 2}, {4, 3}]
  115.  
  116.     iex> Combinatorics.permutations(1..3, 3) |> Enum.to_list
  117.     [{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}]
  118.   """
  119.   def permutations(_enum, 0), do: []
  120.   def permutations(enum, 1), do: Stream.map(enum, &{&1})
  121.   def permutations(enum, n) when is_integer(n) and n > 1 do
  122.     case next(enum) do
  123.       {:next, v, rest} -> &do_permutations({[{v, [], rest}], [v], :next, n - 1}, &1, &2)
  124.       _  -> []
  125.     end
  126.   end
  127.  
  128.   defp do_permutations(_, {:halt, term}, _fun), do: {:halted, term}
  129.   defp do_permutations(v, {:suspend, term}, fun) do
  130.     {:suspended, term, &do_permutations(v, &1, fun)}
  131.   end
  132.   defp do_permutations({[], _, _, _}, {:cont, term}, _), do: {:done, term}
  133.   defp do_permutations({fs, vals, _, 0}, {:cont, term}, fun) do
  134.     do_permutations({fs, vals, :back, 1}, fun.(List.to_tuple(:lists.reverse(vals)), term), fun)
  135.   end
  136.   defp do_permutations({(fs=[{_, r, s}|_]), vals, :next, n}, acc = {:cont, term}, fun) do
  137.     case next({:lists.reverse(r), s}) do
  138.       {:next, v, rest} -> do_permutations({[{v, [], rest}|fs], [v|vals], :next, n - 1}, acc, fun)
  139.       _ -> {:done, term}
  140.     end
  141.   end
  142.   defp do_permutations({[{o, r, s}|fs], [_|vs], :back, n}, acc = {:cont, _}, fun) do
  143.     case next(s) do
  144.       {:next, v, rest} -> do_permutations({[{v, [o|r], rest}|fs], [v|vs], :next, n - 1}, acc, fun)
  145.       _ -> do_permutations({fs, vs, :back, n + 1}, acc, fun)
  146.     end
  147.   end
  148.  
  149.   # === Common Private Functions ===
  150.   defp reducer(v, _), do: {:suspend, v}
  151.  
  152.   defp next([]), do: :done
  153.   defp next([x|xs]), do: {:next, x, xs}
  154.   defp next(fun) when is_function(fun, 1) do
  155.     case fun.({:cont, nil}) do
  156.       {:suspended, v, next_fun} -> {:next, v, next_fun}
  157.       _ -> :done
  158.     end
  159.   end
  160.   defp next({a, b}) do
  161.     case next(a) do
  162.       {:next, v, as} -> {:next, v, {as, b}}
  163.       _ -> next(b)
  164.     end
  165.   end
  166.   defp next(it) do
  167.     case Enumerable.reduce(it, {:cont, nil}, &reducer/2) do
  168.       {:suspended, v, next_fun} -> {:next, v, next_fun}
  169.       _ -> :done
  170.     end
  171.   end
  172. end
  173.  
  174. ExUnit.start()
  175.  
  176. defmodule CombinatoricsTest do
  177.   use ExUnit.Case
  178.   # doctest Combinatorics
  179.  
  180.   test "Combinatorics.product(finite, finite)" do
  181.     assert (Combinatorics.product([1, 2, 3], 1..3) |> Enum.to_list) == [{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}]
  182.   end
  183.  
  184.   test "Combinatorics.product(infinite, finite)" do
  185.     assert (Stream.iterate(1, &(&1+1)) |> Combinatorics.product(1..3) |> Enum.take(10)) == [{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}, {4, 1}]
  186.   end
  187.  
  188.   test "Combinatorics.product([1..2, 3..4, 5..6])" do
  189.     assert (Combinatorics.product([1..2, 3..4, 5..6]) |> Enum.to_list) == [{1, 3, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6}, {2, 3, 5}, {2, 3, 6}, {2, 4, 5}, {2, 4, 6}]
  190.   end
  191.  
  192.   test "Combinatorics.product([infinite, finite])" do
  193.     assert (Combinatorics.product([Stream.iterate(1, &(&1+1)), 1..3]) |> Enum.take(10)) == [{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}, {4, 1}]
  194.   end
  195.  
  196.   test "Combinatorics.combinations(enum, 2)" do
  197.     assert (Combinatorics.combinations(1..4, 2) |> Enum.to_list) == [{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}]
  198.   end
  199.  
  200.   test "Combinatorics.combinations(enum, 3)" do
  201.     assert (Combinatorics.combinations(1..4, 3) |> Enum.to_list) == [{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}]
  202.   end
  203.  
  204.   test "Combinatorics.combinations(enum, 0)" do
  205.     assert (Combinatorics.combinations(1..4, 0) |> Enum.to_list) == []
  206.   end
  207.  
  208.   test "Combinatorics.combinations(enum, 1)" do
  209.     assert (Combinatorics.combinations(1..4, 1) |> Enum.to_list) == [{1}, {2}, {3}, {4}]
  210.   end
  211.  
  212.   test "Combinatorics.combinations(enum, n) when n == Enum.count(enum)" do
  213.     assert (Combinatorics.combinations(1..4, 4) |> Enum.to_list) == [{1, 2, 3, 4}]
  214.   end
  215.  
  216.   test "Combinatorics.combinations(enum, n) when n > Enum.count(enum)" do
  217.     assert (Combinatorics.combinations(1..4, 5) |> Enum.to_list) == []
  218.   end
  219.  
  220.   test "Combinatorics.permutations([1, 2, 3])" do
  221.     assert (Combinatorics.permutations([1, 2, 3]) |> Enum.to_list) == [{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}]
  222.   end
  223.  
  224.   test "Combinatorics.permutations(2..4)" do
  225.     assert (Combinatorics.permutations(2..4) |> Enum.to_list) == [{2, 3, 4}, {2, 4, 3}, {3, 2, 4}, {3, 4, 2}, {4, 2, 3}, {4, 3, 2}]
  226.   end
  227.  
  228.   test "Combinatorics.permutations(1..4, 2)" do
  229.     assert (Combinatorics.permutations(1..4, 2) |> Enum.to_list) == [{1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 3}, {2, 4}, {3, 1}, {3, 2}, {3, 4}, {4, 1}, {4, 2}, {4, 3}]
  230.   end
  231.  
  232.   test "Combinatorics.permutations(1..3, 3)" do
  233.     assert (Combinatorics.permutations(1..3, 3) |> Enum.to_list) == [{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}]
  234.   end
  235.  
  236.   test "Combinatorics.permutations(range)" do
  237.     assert (Combinatorics.permutations(3..1) |> Enum.to_list) == [{3, 2, 1}, {3, 1, 2}, {2, 3, 1}, {2, 1, 3}, {1, 3, 2}, {1, 2, 3}]
  238.   end
  239.  
  240.   test "Combinatorics.permutations(enum, 0)" do
  241.     assert (Combinatorics.permutations(1..4, 0) |> Enum.to_list) == []
  242.   end
  243.  
  244.   test "Combinatorics.permutations(enum, 1)" do
  245.     assert (Combinatorics.permutations(1..4, 1) |> Enum.to_list) == [{1}, {2}, {3}, {4}]
  246.   end
  247.  
  248.   test "Combinatorics.permutations(enum, n) when n > Enum.count(enum)" do
  249.     assert (Combinatorics.permutations(1..4, 5) |> Enum.to_list) == []
  250.   end
  251. end
Success #stdin #stdout 1.25s 112448KB
comments (?)
stdin 
Standard input is empty
stdout 
..................

Finished in 0.2 seconds (0.2s on load, 0.02s on tests)
18 tests, 0 failures

Randomized with seed 33425
https://ideone.com/3T0Ayu
language:
Elixir (elixir 1.8.2)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!