[Haskell-cafe] Building all possible element combinations from N lists.

[dokondr]

Hi all,
I am looking for the algorithm and code better then the one I wrote (please
see below) to solve the problem given in the subject.
Unfortunately I finally need to implement this algorithm in Java. That's
why I am not only interested in beautiful Haskell algorithms, but also in
the one that I can without much pain implement in procedural PL like Java
:(

{--
Build all possible element combinations from N lists.
Valid combination consists of k <= N elements.
Where each element of a single combination is taken from one of the N
lists.
When building combination any list can give only one element for this
combination.
In other words you can not take more then one element from one and the same
list when building current combination. Thus combinations between elements
from the same input list are not allowed.
Yet when building next combination you can use any of the lists again.
Order of elements in combinaton does not matter.

For example:
input = [
  [["a"],["b"]],
  [["1"],["2"]],
  [["<"],[">"]]
  ]

output =
[

["a"],["b"],["1"],["2"],
["a","1"],["a","2"],["b","1"],["b","2"],
["<"],[">"],
["a","<"],["a",">"],["b","<"],["b",">"],
["1","<"],["1",">"],["2","<"],["2",">"],
["a","1","<"],["a","1",">"],["a","2","<"],["a","2",">"],
["b","1","<"],["b","1",">"],["b","2","<"],["b","2",">"]
]

(see bigger example at the end of the code)

Current implementation is based on the idea of using combinations
accumulator.
After first run accumulator contains:
1) All elements from the first two lists. These two lists are taken from
the input list of lists.
The elements of these first two lists are put in accumulator as is.
For example: ["a"],["b"],["1"],["2"]
2) All combinations of these elements:
["a","1"],["a","2"],["b","1"],["b","2"]
Note: Combinations between elements from the same input list are not allowed

Next, on each run we add combinations built from accumulator elements
together with next list taken from the input list of list.
--}


input = [
  [["a"],["b"]],
  [["1"],["2"]],
  [["<"],[">"]],
  [["X"],["Y"]]
  ]


addAll :: [[[a]]] -> [[a]]
addAll [] = []
addAll (x:[]) = x
addAll (x:y:[]) = accum x [y]
addAll inp = accum (initLst inp) (restLst inp)

initLst inp = fstLst ++ sndLst ++ (addLst fstLst sndLst) where
  fstLst = inp !! 0
  sndLst = inp !! 1

restLst inp = (tail . tail) inp

accum :: [[a]] -> [[[a]]] -> [[a]]
accum xs (r:rs) =  accum (xs ++ r ++ addLst xs r) rs
accum xs _ = xs

addLst :: [[a]] -> [[a]] -> [[a]]
addLst (x:xs) ys = addOne x ys ++ addLst xs ys
addLst _ [] = []
addLst [] _ = []

addOne :: [a] -> [[a]] -> [[a]]
addOne x (y:ys) = [x ++ y] ++ addOne x ys
addOne x [] = []

{--
For example:

input = [
  [["a"],["b"]],
  [["1"],["2"]],
  [["<"],[">"]],
  [["X"],["Y"]]
  ]

output =
[
["<"],[">"],
["a"],["b"],["1"],["2"],
["a","1"],["a","2"],["b","1"],["b","2"],
["a","<"],["a",">"],["b","<"],["b",">"],
["1","<"],["1",">"],["2","<"],["2",">"],
["a","1","<"],["a","1",">"],["a","2","<"],["a","2",">"],
["b","1","<"],["b","1",">"],["b","2","<"],["b","2",">"],
["X"],["Y"],
["a","X"],["a","Y"],["b","X"],["b","Y"],
["1","X"],["1","Y"],["2","X"],["2","Y"],
["a","1","X"],["a","1","Y"],["a","2","X"],["a","2","Y"],
["b","1","X"],["b","1","Y"],["b","2","X"],["b","2","Y"],
["<","X"],["<","Y"],[">","X"],[">","Y"],
["a","<","X"],["a","<","Y"],["a",">","X"],["a",">","Y"],
["b","<","X"],["b","<","Y"],["b",">","X"],["b",">","Y"],
["1","<","X"],["1","<","Y"],["1",">","X"],["1",">","Y"],
["2","<","X"],["2","<","Y"],["2",">","X"],["2",">","Y"],
["a","1","<","X"],["a","1","<","Y"],["a","1",">","X"],["a","1",">","Y"],
["a","2","<","X"],["a","2","<","Y"],["a","2",">","X"],["a","2",">","Y"],
["b","1","<","X"],["b","1","<","Y"],["b","1",">","X"],["b","1",">","Y"],
["b","2","<","X"],["b","2","<","Y"],["b","2",">","X"],["b","2",">","Y"]
]

--}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20121026/1c62fcdb/attachment.htm>