# Lazily generate permutations

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

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

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

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

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?

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

``````defp gen_combos(len, elements, criteria) do
Stream.cycle()
|> 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.

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

You’ll generate the permutations faster with a map

1 Like

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

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.

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