# [Haskell-cafe] All combinations in order.

Christian Brolin cbrolin at gmail.com
Mon May 16 17:48:22 UTC 2016

```Hmm, I tried to post this via google groups but it was rejected. So I
try to mail the list instead. Sorry for any duplicates.

Hi list!

How to transform a list of streams of elements into a stream of lists of
elements such that all combinations of exactly one element of each input
stream is present? I.e. something like this:

|
|type Streama =[a]
|tr ::[Streame]->Stream[e]
tr = sequence
|

But I want the order of the output lists so the ones with early elements
come first. The above starts with the first elements from each stream
but does not treat the streams fairly. All the elements of the last
stream are used before the next element of the second last stream is
used, i.e.

|
> tr [[1..3], [1..2], [1..3]]
[[1,1,1],[1,1,2],[1,1,3],[1,2,1].....
|

I don't want the third element of one stream before I have seen all the
combinations of the first two elements of each stream and so on. In this
case I want something like this:

|
[[1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,2,2], [2,1,2], [2,2,1],
[2,2,2], [1,1,3]....
|

Also [2,1,1] comes before [1,2,2] because the former contains two first
element and one second element while the latter contains only one first
element and two second elements.

The number of streams are fairly low but the sequences can be very long
(almost infinte :) and I want the first results without having to go
though a full stream. Also the streams may vary in length so one stream
may ran out of elements before the others. If that happens, the
non-empty streams should contrbute fairly with new elements, i.e:

|
> sequence_ \$ map print  \$ tr [[1..2], [3..5]]  -- two times three equals to six combinations
[1,3]  -- 1: first and first
[1,4]  -- 2: first and second
[2,3]  -- 3: second and first
[2,4]  -- 4: second and second
[1,5]  -- 5: first and third
[2,5]  -- 6: second and third
|

Note, I'm not just interested to handle infinite streams (nor infinite
number of streams) using some diagonal algorithm. I have looked at the
Omega library. But it doesn't return the combinations in wanted order.

If someone still wonder about the output ordering, the following program
may help:
|
importData.List(sort,sortBy)

type Streama =[a]

tr ::Orde =>[Streame]->Stream[e]
tr =sortBy myOrder .sequence
wheremyOrder ::Orde =>[e]->[e]->Ordering
myOrder xs ys =compare (reverse \$ sort xs)(reverse \$ sort ys)

main =sequence_ \$ map print\$ tr [[1..3],[1..2],[1..3],[1..4]]
|

But this of course is not a valid solution since it inspects every
combinations before producing any output.

Attached the sample output.
-------------- next part --------------
An HTML attachment was scrubbed...
-------------- next part --------------
-*- mode: compilation; default-directory: "~/" -*-
Compilation started at Mon May 16 19:23:20

ghc --make Comb && ./Comb
[1 of 1] Compiling Main             ( Comb.hs, Comb.o )
[1,1,1,1]
[1,1,1,2]
[1,1,2,1]
[1,2,1,1]
[2,1,1,1]
[1,1,2,2]
[1,2,1,2]
[1,2,2,1]
[2,1,1,2]
[2,1,2,1]
[2,2,1,1]
[1,2,2,2]
[2,1,2,2]
[2,2,1,2]
[2,2,2,1]
[2,2,2,2]
[1,1,1,3]
[1,1,3,1]
[3,1,1,1]
[1,1,2,3]
[1,1,3,2]
[1,2,1,3]
[1,2,3,1]
[2,1,1,3]
[2,1,3,1]
[3,1,1,2]
[3,1,2,1]
[3,2,1,1]
[1,2,2,3]
[1,2,3,2]
[2,1,2,3]
[2,1,3,2]
[2,2,1,3]
[2,2,3,1]
[3,1,2,2]
[3,2,1,2]
[3,2,2,1]
[2,2,2,3]
[2,2,3,2]
[3,2,2,2]
[1,1,3,3]
[3,1,1,3]
[3,1,3,1]
[1,2,3,3]
[2,1,3,3]
[3,1,2,3]
[3,1,3,2]
[3,2,1,3]
[3,2,3,1]
[2,2,3,3]
[3,2,2,3]
[3,2,3,2]
[3,1,3,3]
[3,2,3,3]
[1,1,1,4]
[1,1,2,4]
[1,2,1,4]
[2,1,1,4]
[1,2,2,4]
[2,1,2,4]
[2,2,1,4]
[2,2,2,4]
[1,1,3,4]
[3,1,1,4]
[1,2,3,4]
[2,1,3,4]
[3,1,2,4]
[3,2,1,4]
[2,2,3,4]
[3,2,2,4]
[3,1,3,4]
[3,2,3,4]

Compilation finished at Mon May 16 19:23:22
```