25 Oct 22:44 2012

## Building all possible element combinations from N lists.

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

addOne :: [a] -> [[a]] -> [[a]]

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

--}
```_______________________________________________
```
25 Oct 23:41 2012

### Re: Building all possible element combinations from N lists.

```On Fri, Oct 26, 2012 at 12:44:31AM +0400, dokondr wrote:
> I am looking for the algorithm and code better then the one I wrote (please
> 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.

combos [] = [[]]
combos ([]:ls) = combos ls
combos ((h:t):ls) = map (h:) (combos ls) ++ combos (t:ls)

Drop last element if you don't want to include the empty set. It
wouldn't be as elegant, but you can translate this to Java.

Alex
```
26 Oct 00:11 2012

### Re: Building all possible element combinations from N lists.

On Fri, Oct 26, 2012 Alex Stangl wrote:
> > combos [] = [[]] > combos ([]:ls) = combos ls > combos ((h:t):ls) = map (h:) (combos ls) ++ combos (t:ls) >

Excellent, thanks!
```_______________________________________________
```
26 Oct 00:34 2012

### Re: Building all possible element combinations from N lists.

```I golfed a bit. :)

sequence <=< filterM (const [False ..])

On Thu, Oct 25, 2012 at 6:11 PM, dokondr <dokondr <at> gmail.com> wrote:
>
> On Fri, Oct 26, 2012 Alex Stangl wrote:
>
>>
>> combos [] = [[]]
>> combos ([]:ls) = combos ls
>> combos ((h:t):ls) = map (h:) (combos ls) ++ combos (t:ls)
>>
>
> Excellent, thanks!
>
>
> _______________________________________________
>
```
26 Oct 06:35 2012

### Re: Building all possible element combinations from N lists.

```On Thu, Oct 25, 2012 at 06:34:53PM -0400, Jake McArthur wrote:
> I golfed a bit. :)
>
>     sequence <=< filterM (const [False ..])

I was thinking of golfing this myself tonight, but probably
wouldn't have come up with this. Thanks for sparing me the effort.

Bravo!

Alex
```
28 Oct 21:36 2012

### Re: Building all possible element combinations from N lists.

On Fri, Oct 26, 2012 at 2:34 AM, Jake McArthur wrote:

I golfed a bit. :)

sequence <=< filterM (const [False ..])

What is "golfed" and  "<=<" ? Please, explain.

Thanks,
Dmitri
```_______________________________________________
```
28 Oct 22:22 2012

### Re: Building all possible element combinations from N lists.

Golfed: http://en.wikipedia.org/wiki/Code_golf

On Sun, Oct 28, 2012 at 4:36 PM, dokondr wrote:
On Fri, Oct 26, 2012 at 2:34 AM, Jake McArthur wrote:
I golfed a bit. :)

sequence <=< filterM (const [False ..])

What is "golfed" and  "<=<" ? Please, explain.

Thanks,
Dmitri

_______________________________________________
```_______________________________________________