Lazily generate permutations

Questions / Help
,
8

Here’s a fully-lazy approach:

defmodule RecursiveStream do
  def all_exactly(_, 0), do: []
  def all_exactly([], _), do: []
  def all_exactly(alphabet, 1) do
    Stream.map(alphabet, &[&1])
  end

  def all_exactly(alphabet, n) do
    streams = Enum.map(alphabet, &prepend(&1, all_exactly(alphabet -- [&1], n-1)))
    Stream.concat(streams)
  end

  def all(alphabet) do
    Stream.iterate(1, &(&1 + 1))
    |> Stream.take(length(alphabet))
    |> Stream.map(&all_exactly(alphabet, &1))
    |> Stream.concat()
  end

  defp prepend(x, stream) do
    Stream.map(stream, &([x] ++ &1))
  end
end

alphabet = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

result =
  RecursiveStream.all(alphabet) |> Stream.take(1000) |> Enum.to_list()

IO.inspect(result, limit: :infinity)

This produces results in order of length: all the length-1 permutations, all the length-2, etc

The maximum length of a result in the output is bounded by the length of the input alphabet, since the values cannot appear more than once. The Stream.take(length(alphabet)) makes sure that the calculation terminates; otherwise, all_exactly will return [] for too-large n and the Stream.concat will iterate forever.

1 Like