stevensonmt

stevensonmt

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

Showing Posts 1 to 10

APB9785

APB9785

Creator of ECSx

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.

dimitarvp

dimitarvp

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])
dimitarvp

dimitarvp

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

dimitarvp

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?

stevensonmt

stevensonmt OP

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

stevensonmt

stevensonmt OP

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.

al2o3cr

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.

thepeoplesbourgeois

thepeoplesbourgeois

You’ll generate the permutations faster with a map

stevensonmt

stevensonmt OP

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!

stevensonmt

stevensonmt OP

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.

Where Next? Top

Trending in Questions Top

itzmidinesh
Hi all, I’m working on a Phoenix project where I need to make external HTTP requests and I’m trying to choose between Req and HTTPoison....
New
yarrichar
I’m very new to Elixir, so sorry if this is a silly question: I am wondering what happens to the mailbox of a process when the machine i...
New
Hellowman
Hello everyone! I am new to coding with Elixir/Erlang. And i am looking for some utilities for fuzzing testing like AFL++. Does anyone ...
New
pragdave
How do I tell Hologram not to escape HTML when substituting into templates? {Textile.render(@product.long_description)} escapes the HTM...
New
Fl4m3Ph03n1x
Background When trying to execute mix release on a Windows 11 machine for a Phoenix project I get the following error: * assembling mark...
New
rlipscombe
I’d like to create a file with 600 permissions (rw-------), but there’s a race condition if I create it and then change the permissions. ...
New
saleyn
Is there a way to import record definitions in the iex shell for pretty printing (similar to the rr command in the erl shell)? This woul...
New

Other Trending Topics Top

dominicletz
Hey there, I haven’t seen a list of useful Elixir specific skills for the popular AI tools yet so I’m starting one here with my first. ...
New
raa-ziq
Hi everyone :waving_hand: I wanted to share something I’ve been building — NowBlind, a random chat app designed to help people discover ...
New
mudasobwa
I fully migrated to my own harness from Anthropic/Gemini and I think it’s time to share it. Welcome DSH, the DeepSeek Harness, fully writ...
New
OndrejValenta
(I just needed to vent somewhere and LinkedIn is full of hope, or hype, I’m not sure which exactly) AI dream has many faces, but general...
New
kip
Localize is the next generation localisation library for Elixir. Think of it as ex_cldr version 3.0. The first version will be released ...
New
jimsynz
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews