Re: [Haskell-cafe] Re: efficient and/or lazy partitions of a multiset

2007-05-23 Thread Greg Meredith

Henning,

i need the bi-partitions of a multiset. That is, all the ways you can split
a multiset, M, into two multisets, M1 and M2, such that M = M1
`multiset-union` M2.

Best wishes,

--greg

On 5/23/07, Henning Thielemann <[EMAIL PROTECTED]> wrote:



On Tue, 22 May 2007, Greg Meredith wrote:

> mSplitC :: [a] -> [([a], [a])] -- C for comprehension
>
> mSplitC [] = [([],[])]
> mSplitC [x] = [([x],[])]
> mSplitC (x:xs) = concat [ [(x:l,r),(l,x:r)] | (l,r) <- mSplitC xs ]
>
> which Matthias Radestock suggested to me.
>
> Note that if you only supply the empty multiset case, then you end up
with
> duplicates.

That is ([1,2],[3]) and ([3],[1,2]) are considered the same? But you need
always pairs not only [1,2] and [3] ?





--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


Re: [Haskell-cafe] Re: efficient and/or lazy partitions of a multiset

2007-05-23 Thread Henning Thielemann

On Tue, 22 May 2007, Greg Meredith wrote:

> mSplitC :: [a] -> [([a], [a])] -- C for comprehension
>
> mSplitC [] = [([],[])]
> mSplitC [x] = [([x],[])]
> mSplitC (x:xs) = concat [ [(x:l,r),(l,x:r)] | (l,r) <- mSplitC xs ]
>
> which Matthias Radestock suggested to me.
>
> Note that if you only supply the empty multiset case, then you end up with
> duplicates.

That is ([1,2],[3]) and ([3],[1,2]) are considered the same? But you need
always pairs not only [1,2] and [3] ?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


[Haskell-cafe] Re: efficient and/or lazy partitions of a multiset

2007-05-22 Thread Greg Meredith

Henning,

In your reply, you made a number of interesting suggestions. You could also
have written

mSplitC :: [a] -> [([a], [a])] -- C for comprehension

mSplitC [] = [([],[])]
mSplitC [x] = [([x],[])]
mSplitC (x:xs) = concat [ [(x:l,r),(l,x:r)] | (l,r) <- mSplitC xs ]

which Matthias Radestock suggested to me.

Note that if you only supply the empty multiset case, then you end up with
duplicates.

mSplitCD :: [a] -> [([a], [a])]
mSplitCD [] = [([],[])]
mSplitCD (x:xs)  = concat [[(x:l,r),(l,x:r)] | (l,r) <- mSplitCD xs]

*Zoup> mSplitCD [1,2,3]
[([1,2,3],[]),([2,3],[1]),([1,3],[2]),([3],[1,2]),([1,2],[3]),([2],[1,3]),([1],[2,3]),([],[1,2,3])]

*Zoup> mSplitC [1,2,3]
[([1,2,3],[]),([2,3],[1]),([1,3],[2]),([3],[1,2])]
*Zoup>

Is there anyway to peer under the hood to see the code being generated? i
notice, for example, that the original concat/zip-based implementation
occasionally comes in quite a bit faster that the comprehension based
example.

Best wishes,

--greg


On 5/21/07, Greg Meredith <[EMAIL PROTECTED]> wrote:


HC-er's,

Find below some simple-minded code from a naive Haskeller for generating
all partitions of a multiset about which i have two questions.

mSplit :: [a] -> [([a], [a])]
mSplit [x] = [([x],[])]
mSplit (x:xs) = (zip (map (x:) lxs) rxs)
  ++ (zip lxs (map (x:) rxs))
  where (lxs,rxs) = unzip (mSplit xs)

   1. Is there a clever way to reduce the horrid complexity of the
   naive approach?
   2. How lazy is this code? Is there a lazier way?

i ask this in the context of checking statements of the form \phi * \psi
|= e_1 * ... * e_n where

   - [| \phi * \psi |] = { a \in U : a === b_1 * b_2, b_1 \in [| \phi
   |], b_2 \in [| \psi |] }
   - === is some congruence generated from a set of relations

A nice implementation for checking such statements will iterate through
the partitions, generating them as needed, checking subconditions and
stopping at the first one that works (possibly saving remainder for a rainy
day when the client of the check decides that wasn't the partition they
meant).

Best wishes,

--greg

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com





--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe