[Haskell-cafe] List all multiply/add combinations

Rune Harder Bak rune at bak.dk
Sat Nov 17 20:07:26 CET 2012


It might be rare that a "real world" problem can be formulated as such
a simple mathematical challenge,
so I can't blame you for thinking about home work. I did too.
Actually it's part of a logic puzzle I'm implementing.

Attacking the problem textually, I can treat the list of infix
operators as char, and
insert parentheses in all possible configurations. Then remove the
illegal and unnecessary one.
To get the result, I then need to parse the string.
That seems slow, and awkward.
I need to do hundreds of thousands of these calculations.
I could then work directly with parsing trees, and generate all binary
trees of fixed lengths.
But most of them would be unnecessary, so it seems like I'm attacking
it from the wrong angle.

I get that using permutations you can get rid of the need for
parentheses, but you also get a lot of
impossible calculations (like a*c+b in the example before). It's also
not straight forward to go back to the
original representation with parentheses. But maybe I'm missing
something obvious here?



On Sat, Nov 17, 2012 at 4:18 PM,  <timothyhobbs at seznam.cz> wrote:
> This smells like homework to me,
> which isn't a bad thing,
> it will however change the way I answer you.
>
> Please look at
> http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-List.html#v:permutations
> and show us your attempts to use this function.
>
> Timothy
>
>
> ---------- Původní zpráva ----------
> Od: Rune Harder Bak <rune at bak.dk>
> Datum: 17. 11. 2012
> Předmět: [Haskell-cafe] List all multiply/add combinations
>
> Given a list of numbers of fixed length I need to list all possible
> values (and the associated computation) you get by
> inserting +,-,*,/ between the numbers, and also set parentheses where
> you please.
> It shouldn't list computations with unnecessary parentheses.
> Example list of length 3 [a,b,c] and only with + and *:
> a*b+c, a*(b+c),a*b*c,a+b*c,(a+b)*c,a+b+c
>
> What would be a good way to do this, and a good representation in Haskell?
>
> Best,
> Rune
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe



More information about the Haskell-Cafe mailing list