Re: multisets

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

Hi,
this time I wonder how the Prolog geeks 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):

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).
.

Relevant Pages

  • Re: multisets
    ... this time I wonder how the Prolog geeks would write ... a predicate which gets multisets of cardinality C ...
    (comp.lang.prolog)
  • multisets
    ... this time I wonder how the Prolog geeks would write ... a predicate which gets multisets of cardinality C ...
    (comp.lang.prolog)