Lazily generate permutations

[stevensonmt]

Thanks for that tip. Because I’m generating permutations of N length from a set of M items I had to change the terminating case from a map size of zero to map size of M - N. It’s about 30% faster than my original version. I also threw in a Enum.shuffle(M) when generating the permutations. This randomness occasionally leads to another big increase in speed, though it could equally likely lead to a longer search as well. Thanks!

@al2o3cr

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.

Will try to implement this and see how it goes. Thanks for your help!