Lazily generate permutations

Questions / Help
,
1

I know how to use comprehensions to generate combinations/permutations:

(for a <- 0..9,
b <- 0..9 |> Enum.reject(&Kernel.==(&1, a)),
c <- 0..9 |> Enum.reject(fn i -> i == a or i == b end),
do:
[a,b,c])
|> apply_criteria()

How would I do this lazily so that I stop generating permutations once I find the one that fulfills some criteria? I tried using Stream.repeatedly:

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

But this only works in the cases for which there is a permutation that satisfies the criteria. If there is no match it will just go infinitely. In this example I’m using permutations of 3 items, but in the real problem the length of the permutations is variable. The best non lazy approach I’ve come up with generating permutations of variable length is recursive:

def gen_perms(0, combos), do: combos
def gen_perms(len, []) do 
  gen_perms(len - 1, Enum.map(0..9, fn i -> [i] end))
end
def gen_perms(len, combos) do 
  new_combos = 
    for combo <- combos,
      n <- 0..9 |> Enum.filter(fn i -> not Enum.member?(combo, i) end),
    do: [n | combo]

  gen_perms(len - 1, new_combos)
end

(As an aside, in the Stream approach I used the random function to pick the starting digit because there is no reason to suspect that sequential order is going to be the most efficient path, even if in the worst case the randomness leads to never getting all permutations. I have not yet decided if that is a good tradeoff.)

2

I think you need to go in order, otherwise you won’t know when you have exhausted all possibilities. I would use the recursive approach like such:

def gen_perms(criteria), do: gen_perms({0, 0, 0}, criteria)

def gen_perms({_, _, 10}, criteria), do: {:no_match, criteria}
def gen_perms({a, 10, c}, criteria), do: gen_perms({a, 0, c+1}, criteria)
def gen_perms({10, b, c}, criteria), do: gen_perms({0, b+1, c}, criteria)
def gen_perms({a, b, c}, criteria) do
  if criteria_match?({a, b, c}, criteria) do
    {:ok, {a, b, c}, criteria}
  else
    gen_perms({a+1, b, c}, criteria)
  end
end

This way the function will go through each possibility one-by-one, and immediately stop when a match is found.

2 Likes
3

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])
3 Likes
4

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()
5

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?

6

@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.

7 
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.

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
9

You’ll generate the permutations faster with a map

1 Like
10

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!

1 Like
11

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.

12

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.

3 Likes