[Haskell-cafe] All combinations in order.

[Christian Brolin]

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...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20160516/061fb952/attachment.html>
-------------- 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 )
Linking Comb ...
[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