multisets

Hi,
this time I wonder how the Prolog gs would write
a predicate which gets multisets of cardinality C
filled with numbers between M and N (inclusive).
(Example: C: 2, M: 1, N 2:
[1, 1]; [1, 2]; [2,2] (because [1, 2] = [2, 1]))

The only solution I can think of is, producing
all combinations and cutting the duplicates:

checkSet([E1,E2|[]]) :-
!, E1 =< E2.
checkSet([E1,E2|R]) :-
E1 =< E2,
checkSet([E2|R]).

multiSets(M, N, 1, S) :-
length(S, 1),
maplist(between(M, N), S).

multiSets(M, N, C, S) :-
length(S, C),
maplist(between(M, N), S),
checkSet(S).

But this seems more expensive as it needs
to be?

Thanks for any suggestions.  And even bigger
Thanks for any explications.

best regards
Stephan

On Feb 22, 2:20 pm, Stephan Lukits <Stephan.Luk...@FernUni-Hagen.de>
wrote:
> Hi,
> this time I wonder how the Prolog gs would write
> a predicate which gets multisets of cardinality C
> filled with numbers between M and N (inclusive).
> (Example: C: 2, M: 1, N 2:
> [1, 1]; [1, 2]; [2,2] (because [1, 2] = [2, 1]))
>
> The only solution I can think of is, producing
> all combinations and cutting the duplicates:
>
> checkSet([E1,E2|[]]) :-
>         !, E1 =< E2.
> checkSet([E1,E2|R]) :-
>         E1 =< E2,
>         checkSet([E2|R]).
>
> multiSets(M, N, 1, S) :-
>         length(S, 1),
>         maplist(between(M, N), S).
>
> multiSets(M, N, C, S) :-
>         length(S, C),
>         maplist(between(M, N), S),
>         checkSet(S).
>
> But this seems more expensive as it needs
> to be?
>
> Thanks for any suggestions.  And even bigger
> Thanks for any explications.
>
> best regards
> Stephan

I'd modify your approach to produce a monotone
increasing list of length C (containing values
between M and N inclusive).

Untested code follows:

multiset(C,M,N,S) :-
length(S,C),
increasing(M,N,S).

increasing(_,_,[]).
increasing(M,N,[H|T]) :-
between(M,N,H),
increasing(H,N,T).

Alternatively we might eliminate dependence on a
built-in length/2:

multiset(0,_,_,[].
multiset(C,M,N,[H|T]) :-
C > 0,
between(M,N,H),
B is C - 1,
multiset(B,H,N,T).



regards, chip

On Fri, 22 Feb 2008 20:20:02 +0100, Stephan Lukits wrote:

> Hi,
> this time I wonder how the Prolog gs would write
> a predicate which gets multisets of cardinality C
> filled with numbers between M and N (inclusive).
> (Example: C: 2, M: 1, N 2:
> [1, 1]; [1, 2]; [2,2] (because [1, 2] = [2, 1]))


Since I feel you have been shortchanged with the answer you got until now ..
.

Here is the inductive definition way to arrive at a decent solution
to your problem (under the assumption I understood you correctly):

a multiset Set of length Len with numbers M up to N

starts with M and the rest of it is a multiset of numbers
M up to N of length Len-1
or
it does not start with M, and in this case, it is a multiset
of numbers M+1 up to N of length Len

of course, if Len equals 0, the only answer is []
and if M > N, I refuse to give it a meaning


ms(M,N,Len,Set) :-
Len > 0,
M =< N,
Set = [M|RestSet],
Len1 is Len - 1,
ms(M,N,Len1,RestSet).
ms(M,N,Len,Set) :-
Len > 0,
M =< N,
M1 is M + 1,
ms(M1,N,Len,Set).
ms(M,N,Len,Set) :-
Len == 0,
M =< N,
Set = [].

Beautiful, isn't it ?

Cheers

Bart Demoen

bart demoen schrieb:
> On Fri, 22 Feb 2008 20:20:02 +0100, Stephan Lukits wrote:
> 
>
>
> Since I feel you have been shortchanged with the answer you got until now 
..
>
> Here is the inductive definition way to arrive at a decent solution
> to your problem (under the assumption I understood you correctly):

Yes.  As I posted the questions I where still thinking in
the term of "multiset".  Though figuring the relation between
the elements of the sets I was to tired to step back and see
what consequences it has on the whole set.  At the latest with
Chips post I saw the obvious (theorem):
Let (O be a set (of objects) with cardinality C.  Let |M be the
set of all multisets with cardinality C' over (O.
Let (S be the set of all monotonically increasing  sequence
with length C' and members from {1, 2, 3, ..., C}.

There is a bijection from (S on |M.

Thus it is sufficient to build the set (S of monotonically increasing
sequences to get all multisets from |M.

O.K. lets switch to the term of monotonically increasing sequences.

> a multiset Set of length Len with numbers M up to N
>
>            starts with M and the rest of it is a multiset of numbers
>                        M up to N of length Len-1
> or
>            it does not start with M, and in this case, it is a multiset
>                        of numbers M+1 up to N of length Len
>
> of course, if Len equals 0, the only answer is []
> and if M > N, I refuse to give it a meaning
>
>
> ms(M,N,Len,Set) :-
>         Len > 0,
>         M =< N,
>         Set = [M|RestSet],
>         Len1 is Len - 1,
>         ms(M,N,Len1,RestSet).
> ms(M,N,Len,Set) :-
>         Len > 0,
>         M =< N,
>         M1 is M + 1,
>         ms(M1,N,Len,Set).
> ms(M,N,Len,Set) :-
>         Len == 0,
>         M =< N,
>         Set = [].
>
> Beautiful, isn't it ?

Yes, very appealing and interresting
approach.

Thank you and regards
Stephan (who will sleep over it).

On Feb 25, 8:48 pm, bart demoen <b...@cs.kuleuven.be> wrote:
> On Fri, 22 Feb 2008 20:20:02 +0100, Stephan Lukits wrote: 
>
> Since I feel you have been shortchanged with the answer you got until now 
..
>
> Here is the inductive definition way to arrive at a decent solution
> to your problem (under the assumption I understood you correctly):
>
> a multiset Set of length Len with numbers M up to N
>
>            starts with M and the rest of it is a multiset of numbers
>                        M up to N of length Len-1
> or
>            it does not start with M, and in this case, it is a multiset
>                        of numbers M+1 up to N of length Len
>
> of course, if Len equals 0, the only answer is []
> and if M > N, I refuse to give it a meaning
>
> ms(M,N,Len,Set) :-
>         Len > 0,
>         M =< N,
>         Set = [M|RestSet],
>         Len1 is Len - 1,
>         ms(M,N,Len1,RestSet).
> ms(M,N,Len,Set) :-
>         Len > 0,
>         M =< N,
>         M1 is M + 1,
>         ms(M1,N,Len,Set).
> ms(M,N,Len,Set) :-
>         Len == 0,
>         M =< N,
>         Set = [].
>
> Beautiful, isn't it ?
>
> Cheers
>
> Bart Demoen

Yes, it isn't so much a 'program' as it is a translation of the
definition in English into the formal syntax of prolog. Tell the
computer what you want, not how to do it.

On Feb 25, 3:48 pm, bart demoen <b...@cs.kuleuven.be> wrote:
> On Fri, 22 Feb 2008 20:20:02 +0100, Stephan Lukits wrote: 
>
> Since I feel you have been shortchanged with the answer you got until now ...[/col
or]

I have that effect on people!  And true, there was an
omitted closing parenthesis...

Stylistically I seem to code more of the algorithm
into the unification side of things than Bart did.
I expect my readability suffers somewhat for that,
hopefully with compensation in performance.

I've been thinking about how fortunate we were that
Stephan wanted a multiset of integers (between M and
N), which made the equivalence of multisets to an
increasing list natural (in a gy kind of way).

What if the underlying domain weren't so conveniently
generated?  One approach would be to require a list
of the (distinct) available "objects", replacing the
arguments M and N with such a list:

multiset(0,_,[]) :- !.
multiset(Count,[H|T],[H|L]) :-
Down is Count - 1,
Down >= 0,
multiset(Down,[H|T],L).
multiset(Count,[_|T],L) :-
multiset(Count,T,L).

Another approach could be to work with a multiset of
"indexes" into an underlying domain of objects, using
the integer code, then converting index lists to
object lists by "lookup" (maplist?) as necessary.


regards, chip

On Wed, 27 Feb 2008 08:27:45 -0800, Chip Eastham wrote:

> I've been thinking about how fortunate we were that
> Stephan wanted a multiset of integers (between M and
> N), which made the equivalence of multisets to an
> increasing list natural (in a gy kind of way).

Oh no, the restriction to integers (from M to N) wasn't fortunate at
all, but I tried to stick to what Stephan asked.

And there is nothing gy about the equivalence - in fact, it
applies beyond integers, because one can order any set.
(for finite sets, this is trivial; for infinite sets, you need
AC, but we won't be programming with them)

Below is a solution to Stephan's problem which has as a helper
predicate multiset/2: I warn you, it will make your code dabbling and
comments about objects, indexes, lookup and maplist look very
childish, so take a deep breath before you read on ...


% multiset/4 to respond to the OP

multiset(Size,From,To,MultiSet) :-
findall(X,between(From,To,X),Items), % (*)
length(MultiSet,Size),
multiset(MultiSet,Items).

multiset([],_).
multiset(MultiSet,Items) :-
MultiSet = [El|Els],
Items = [I|Is],
(
El = I,               % I is in the multiset
multiset(Els,Items)
;
multiset(MultiSet,Is) % I is not
).


(*) I am not happy with this line, and I suspect there is some
predicate in some library that does the same - I am not acquainted
with the lib that much, sorry.

Now ... since you wrote
> hopefully with compensation in performance.
why don't you put this to the test ?
Speculating or just hoping is not enough to teach us something !

Cheers

Bart Demoen

ps. we (not necessarily Chip and me) might get into the discussion whether
p(X, ...) :- X = [A|B], ...
gives the same indexing as
p([A|B], ...) :- ...
please let's not do that: look up the previous conclusive discussion on
this issue instead

On 2008-02-27, bart demoen <bmd@cs.kuleuven.be> wrote:

> multiset(Size,From,To,MultiSet) :-
>         findall(X,between(From,To,X),Items), % (*)
>         length(MultiSet,Size),
>         multiset(MultiSet,Items).

<snip>

> (*) I am not happy with this line, and I suspect there is some
> predicate in some library that does the same - I am not acquainted
> with the lib that much, sorry.

Even after a small enhancement of numlist, I get this (SWI-Prolog
5.6.51 with this enhancement, 64-bit version on AMD3800+):

?-  time(findall(X,between(0,1000000,X),Item
s)).
% 1,000,012 inferences, 0.57 CPU in 0.64 seconds (90% CPU, 1754407 Lips)
Items = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].

?- time(numlist(0, 1000000, X)).
% 2,000,009 inferences, 0.72 CPU in 0.77 seconds (93% CPU, 2777790 Lips)
X = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].

I must admit I was a bit surprised as well (and the performance of
findall/3 has almost doubled a few months ago).  I would suspect
SWI-Prolog is one of the few systems for which the findall/between
attack is faster than numlist.

Cheers --- Jan

On Wed, 27 Feb 2008 20:53:09 +0000, Jan Wielemaker wrote:

> Even after a small enhancement of numlist, I get this (SWI-Prolog
> 5.6.51 with this enhancement, 64-bit version on AMD3800+):
>
> ?-  time(findall(X,between(0,1000000,X),Item
s)).
> % 1,000,012 inferences, 0.57 CPU in 0.64 seconds (90% CPU, 1754407 Lips)
> Items = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].
>
> ?- time(numlist(0, 1000000, X)).
> % 2,000,009 inferences, 0.72 CPU in 0.77 seconds (93% CPU, 2777790 Lips)
> X = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].
>
> I must admit I was a bit surprised as well (and the performance of
> findall/3 has almost doubled a few months ago).  I would suspect
> SWI-Prolog is one of the few systems for which the findall/between
> attack is faster than numlist

Sure enough - in other systems numlist is between 4 and 15 times faster !
One reason is maybe the SWI implementation of if-then-else.
If I replace between/2 with something in plain Prolog, the timings tend to
be worse for findall/mybetween.

Such surprises (on top of that experienced by the author of a systems)
must be very confusing for users.

Cheers

Bart Demoen

On 2008-02-27, bart demoen <bmd@cs.kuleuven.be> wrote:
> On Wed, 27 Feb 2008 20:53:09 +0000, Jan Wielemaker wrote:
> 
>
> Sure enough - in other systems numlist is between 4 and 15 times faster !
> One reason is maybe the SWI implementation of if-then-else.
> If I replace between/2 with something in plain Prolog, the timings tend to
> be worse for findall/mybetween.
>
> Such surprises (on top of that experienced by the author of a systems)
> must be very confusing for users.

That is partly a problem that is associated to any higher level
programming languages. They sometimes optimize some code from a more
abstract specification to something unexpectely fast and sometimes fail
to do so and end up with something unexpectely slow. Same happens even
to C programmers who do not know the price of malloc (or new for C++
users).  I was once surprised that

switch (n)
{ case 0:
case 1:
..
}

is faster than

switch (n)
{ case 1:
case 2:
..
}

Dunno whether that is still the case with modern compilers.  After
all they could decide to turn this into

switch (n)
{ case 0:
break;
case 1:
case 2:
..
}

Anyone with a rough model of Prolog execution will assume that the
findall/between version is slower. Ok, on one particular system it is
the other way around, but by so little it doesn't matter much which
option you choose.

I'm sure you find this issue on any programming language. From the
popular ones, C is the most easy predictable language, but in my
experience the performance of some of the C library functions also
varies widely.

Cheers --- Jan