25 Oct 22:44 2012

## Building all possible element combinations from N lists.

dokondr <dokondr <at> gmail.com>

2012-10-25 20:44:31 GMT

2012-10-25 20:44:31 GMT

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"]

]

--}

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"]

]

--}

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe