dokondr | 25 Oct 22:44 2012
Picon

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 :: [[[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
Alex Stangl | 25 Oct 23:41 2012
Picon

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
dokondr | 26 Oct 00:11 2012
Picon

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!
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Jake McArthur | 26 Oct 00:34 2012
Picon

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!
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
Alex Stangl | 26 Oct 06:35 2012
Picon

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
dokondr | 28 Oct 21:36 2012
Picon

Re: Building all possible element combinations from N lists.

On Fri, Oct 26, 2012 at 2:34 AM, Jake McArthur <jake.mcarthur <at> gmail.com> wrote:

I golfed a bit. :)

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


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

Thanks,
Dmitri
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Clark Gaebel | 28 Oct 22:22 2012
Picon
Picon

Re: Building all possible element combinations from N lists.

Golfed: http://en.wikipedia.org/wiki/Code_golf
<=< : Also known as Kleisli composition. More info: http://www.haskell.org/hoogle/?hoogle=%3C%3D%3C

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

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


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

Thanks,
Dmitri

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


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

Gmane