multiset ordering
- From: Giovanni Gherdovich <gherdovich@xxxxxxxxxxxxxxxxxxxxxx>
- Date: Sun, 15 Jul 2007 14:07:52 -0000
Hello,
I'm trying to extend the usual strict order on natural numbers
to multiset (or bag) of numbers (special sets where duplicates are
allowed).
There are various way to define the multiset-extension of an
order; I choose the transitive closure of the relation
`the bag X is greater then the bag Y iff Y is obtained from
X replacing a single element with a finite (eventually empty)
collection of smaller elements`,
as I read in a paper of N. Dershowitz,
http://www.cs.tau.ac.il/%7Enachumd/papers/Orderings4TRS.pdf ,
pag. 289.
It seems to be allright, but my code doesn't work on
some inputs. Here is it:
%*************************************************
% ORDERING FOR MULTISETS OF NATURAL NUMBERS
%*************************************************
% gt_all(A,B) means `the element A is greater of
% every element in the list B`
gt_all(S,[]).
gt_all(S,[T|Ts]):-
S > T,
gt_all(S,Ts).
% gt_ms_onestep(X,Y) means `Y is obtained from
% X replacing a single element with a finite collection
% (eventually empty) of smaller elements`.
gt_ms_onestep(X,Y):-
select(Pivot,X,Rest),
permutation(Y,Yperm),
append(Yi,Rest,Yperm),
gt_all(Pivot,Yi).
% The following is the transitive closure of the
% relation above.
gt_ms(X,Y):- gt_ms_onestep(X,Y).
gt_ms(X,Y):-
gt_ms_onestep(X,Y1),
gt_ms(Y1,Y).
%***********************************************
But I got from my swi-prolog interpreter:
?- gt_ms([3],[3]).
ERROR: Arguments are not sufficiently instantiated
Can somebody find out why?
I think gt_ms_onestep works well, the problem is
in the two other predicates.
Best regards,
Giovanni Gherdovich
.
- Follow-Ups:
- Re: multiset ordering
- From: Pierpaolo BERNARDI
- Re: multiset ordering
- Prev by Date: TOY 2.3.0 launched
- Next by Date: Re: multiset ordering
- Previous by thread: TOY 2.3.0 launched
- Next by thread: Re: multiset ordering
- Index(es):
Relevant Pages
|
|
