# Stream chunking with every possible combination

Hey everyone,
I’ve been trying to generate every possible non-equal combination of N elements from a list of known size. This would be a really long list, and I would like to create these combinations and in a stream-fashion, apply filters and calculations of top.

## Example for N=3

``````list = [1, 2, 3, 4, 5, 6]

Stream.magic_method(list)
|> Stream.map(&IO.inspect/1)                       # [1, 2, 3], [1, 2, 4], ..., [1, 3, 5], ..., [4, 5, 6]
|> Stream.reject(fn n -> Enum.at(n, 0) == 1 end)   # Rejects combinations starting with 1
|> Stream.map(&IO.inspect/1)                       # [2, 3, 5], ..., [4, 5, 6]
``````

I’ve tried to use `Stream.transform` and `Stream.chunk_every`, but no luck so far.

I also thought of a way using messages between Agents as a queue to process every nested `for` combination, but I imagine that it would be overkill.

Is there a simple way of doing it using Streams?

You need a recursive approach to generate permutations. The stream api for recursive is `Stream.unfold`.

1 Like

If anyone is looking for a more complete solution, this is what I was able to do:

``````  def create_combinations(list, n) do
List.duplicate(0, n)
|> Enum.with_index
|> Enum.reduce(%{}, fn { v, i }, map -> Map.put(map, i, v) end)
"""
Creates a map with the index of every possible combination of list like this:
%{ 0 => 0, 1 => 0, 2 => 0, ... }
"""
|> Stream.unfold(fn
nil -> nil
indexes ->
# Generate the combination based on the index map
combination = Enum.map(indexes, fn { _, i } -> Enum.at(list, i) end)
new_indexes = next_indexes(indexes, length(list) - 1)

{ combination, new_indexes }
end)
end

defp next_indexes(indexes, max),
do: next_indexes_at(indexes, max, map_size(indexes) - 1)

defp next_indexes_at(indexes, max, pos) do
curr_value = Map.get(indexes, pos)

if curr_value == max do
if pos == 0 do
nil
else
indexes
|> Map.put(pos, 0)
|> next_indexes_at(max, pos - 1)
end
else
Map.put(indexes, pos, curr_value + 1)
end
end
``````

You can save computations and construct the map in just one step without `Enum.reduce` by changing the above piece with this one:

``````|> Map.new(fn {v, k} -> {k, v} end)
``````

Though I am not sure that is dramatically faster (likely not because each pair has to be reversed). Still it reads better IMO.

1 Like

Several years ago I wrote `LazyFor` library, replicating `for/1` comprehension for streams.

With it, it’d be as straightforward as

``````iex(1)> Mix.install([:lazy_for])
iex(2)> import LazyFor
iex(3)> list = 1..6

iex(4)> stream i <- list, j <- list, i != j, k <- list, i != k, j != k,
do: [i, j, k]
#⇒ #Function<62.38948127/2 in Stream.transform/3>

iex(5)> stream i <- list, j <- list, i != j, k <- list, i != k, j != k,
take: 5, do: [i, j, k]
#⇒ [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 6], [1, 3, 2]]
``````
3 Likes