Lazily generate permutations

If you know the length of the permutation you want, then RecursiveStream.all is doing more computation than you need.

RecursiveStream.all_exactly(alphabet, desired_permutation_length) gives a stream of permutations of a specific length; RecursiveStream.all concatenates those streams for all possible lengths.

I can’t seem to get this to work. The problem is that I don’t want any permutations of the wrong length, so I’d have to introduce a filtering step after generating them all, which seems terribly inefficient. For some reason I’m finding it very difficult to follow how your code works so I don’t know how to adjust it to only return permutations of the desired length.

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!

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

You’ll generate the permutations faster with a map

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.

defp gen_combos(len, elements, criteria) do
    Stream.cycle([0])
    |> Enum.take(len)
    |> Enum.zip(elements)
    |> next_combo(len, elements, criteria)
  end

  defp valid_combo(combo, criteria) do
    Enum.all?(criteria, fn check -> apply(check, combo) end)
  end

  defp next_combo([{hd, c} | tl] = combo, len, elements, criteria)) do
    cond do
      valid_combo(combo, criteria) ->
        Enum.reduce(combo, %{}, fn {v, <<c>>}, map -> Map.put(map, c, v) end)

      Enum.any?(combo, fn {v, _} -> v == 10 end) ->
        case Enum.find_index(combo, fn {v, _} -> v == 10 end) do
          x when x == len - 1 ->
            %{}

          x ->
            combo
            |> Enum.with_index()
            |> Enum.map(fn {{v, c}, i} ->
              case i do
                y when y == x -> {0, c}
                y when y == x + 1 -> {v + 1, c}
                _ -> {v, c}
              end
            end)
            |> next_combo(len, elements, criteria)
        end

      true ->
        next_combo([{hd + 1, c} | tl], len, elements, criteria)
    end
  end

This is the code I came up with for that approach, but it turns out to actually be slower than generating all the combinations and turning them into a stream for the criteria checks. I’m not sure why.

@APB9785’s solution is a great illustration of what I’m trying to do. I’m trying to check each combination as they’re created and short circuit at the first correct combination. I had it in my head that it should be possible to do with a Stream of some sort but that recursive approach is fine. The importance of short circuiting is that the set of elements has no predefined boundaries, so there could be up to 3,628,800 possible permutations. Generating those permutations is potentially the bottleneck in the problem as applying the criteria is trivial.

This is great, except I cannot know ahead of time that there are only 3 elements in each permutation. So I think I can start with gen_perms(Enum.take(0..9, perm_len), criteria) and try to make it work. I’ll have to think on it some more.

Even though @APB9785’s code is sound and does what it says it does, I am still not sure I understand your requirements. Can you share some more of them? Or ideally a small GitHub projects where you show where are you at currently?

You can insert one Stream.take call in the pipe to enforce a hard limit, like so?

  Stream.repeatedly(Enum.random(0..9))
+ |> Stream.take(9_999_999)
  |> Stream.chunk_every(3)
  |> Stream.filter(fn combo -> Enum.uniq(combo) == combo end)
  |> apply_criteria()

As an aside: filtering is supported out of the box by Elixir’s for comprehension:

(for a <- 0..9, b <- 0..9, c <- 0..9, a != b and b != c, do: [a,b,c])