Re: multisets

On Feb 22, 2:20 pm, Stephan Lukits <Stephan.Luk...@xxxxxxxxxxxxxxxx>
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]))

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
.

Relevant Pages

  • multisets
    ... this time I wonder how the Prolog geeks would write ... a predicate which gets multisets of cardinality C ...
    (comp.lang.prolog)
  • Re: multisets
    ... this time I wonder how the Prolog geeks would write ... a predicate which gets multisets of cardinality C ... The multiset of cardinality C filled with numbers between M+1 and N ...
    (comp.lang.prolog)
  • Re: multisets
    ... this time I wonder how the Prolog geeks would write ... a predicate which gets multisets of cardinality C ... a multiset Set of length Len with numbers M up to N ...
    (comp.lang.prolog)
  • Re: multisets
    ... a predicate which gets multisets of cardinality C ... set of all multisets with cardinality C' over (O. ... Let (S be the set of all monotonically increasing sequence ... Thus it is sufficient to build the set (S of monotonically increasing ...
    (comp.lang.prolog)
  • Re: multisets
    ... this time I wonder how the Prolog geeks would write ... The multiset of cardinality C filled with numbers between ... The multiset of cardinality C filled with numbers between M+1 and N ... you are learning the ABC without first learning the language as a mother ...
    (comp.lang.prolog)