Re: Sublists question
From: billh (sequitur_at_sonic.net)
Date: 03/26/04
- Next message: Matthew Huntbach: "Re: Mainstreaming Prolog a Pragmatic Approach?"
- Previous message: zeus: "Re: Sublists question"
- In reply to: zeus: "Re: Sublists question"
- Next in thread: zeus: "Re: Sublists question"
- Reply: zeus: "Re: Sublists question"
- Reply: Bart Demoen: "Re: Sublists question"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Fri, 26 Mar 2004 08:53:11 GMT
zeus wrote:
> Bill Spight <Xbspight@pacbell.net> wrote in message news:<4061F60C.C38F0A28@pacbell.net>...
>
>>Dear zeus,
>>
>>Bart's comments are right on. :-)
>>
>>
>>>sublist(S,L):-append(_,S,P),append(P,_,L).
>>
>>Since any of the variables can be []s, this clause is certainly true.
>>And it seems to cover all possibilities.
>>
>>However, I believe that it is the cause of your stack overflows. When
>>append(P,_,L) fails, it will backtrack into append(_,S,P), which can
>>always succeed by increasing the length of the anonymous list by one.
>>Since P gets longer than L (given that the size of L is determined
>>before calling sublist(S,L)), append(P,_,L) keeps failing and
>>append(_,S,P) keeps succeeding. That gives you a kind of infinite loop.
>>
>>Here is an alternative predicate that does not have that problem.
>>
>>sublist(Sublist,List) :-
>> append(Midlist,_,List),
>> append(_,Sublist,Midlist).
>>
>>All we did was switch the goals, so that the information about List gets
>>used first. Remember that if List is uninstantiated, there will be an
>>infinity of solutions to sublist/2. That's generally not what you want.
>>With this ordering, you fail early, which is usually what you want.
>>
>>
>>>langford_sublists(0,_,_).
>>>
>>>%recursively generate all sublists
>>>langford_sublists(N,K,L) :-
>>> N>0,
>>> % every list consists on K copies of N + K-1 copies of N variables
>>> Size is K+(K-1)*N,
>>> generate_list(N,Size,List,L),
>>> NN is N-1,
>>> langford_sublists(NN,K,L).
>>
>>List in generate_list(N,Size,List,L) occurs only once in this clause.
>>That means that you neither extract nor provide information using it.
>>Sometimes that's what you want, but often it indicates a problem. In
>>fact, the corresponding variable does not appear in the first clause,
>>either, and that is definitely problematic.
>>
>>
>>>generate_list(_,0,L1,L2) :-
>>> sublist(L1,L2).
>>>
>>>% responsible for placing the Ns in the sublist
>>>generate_list(N,I,List,L) :-
>>> I>0,
>>> II is I-1,
>>> NNN is N+1,
>>> III is II mod NNN,
>>> III is 0,
>>> generate_list(N,II,[N|List],L).
>>>
>>>% responsible for placing the variables in the sublist
>>>generate_list(N,I,List,L) :-
>>> I>0,
>>> II is I-1,
>>> generate_list(N,II,[_|List],L).
>>
>>I like your style of commenting, but here you may want to get more
>>specific about what is going on, particularly as you are learning the
>>language. I do not really get what the predicate means or does. It often
>>helps just to write the predicate out clearly in natural language, and
>>then translate into Prolog.
>>
>>What Prolog are you using? What debugging facilities does it provide?
>>You need to learn to use them. :-)
>>
>>Anyway, with the new sublist/2 predicate, the query, langford(4,2,List),
>>does not blow the stack. Instead, it returns this answer:
>>
>>
>>>List = [4, 2, 3, 1, 2, 4, 3, _G239]
>>
>>_G239 is an anonymous variable generated by Prolog. Plainly this is
>>wrong. There is no substitution for the anonymous variable that will
>>produce a Langford list. The problem probably lies in generate_list/4.
>>
>>Best,
>>
>
>
> I have changed completely the implementation. I will give it shortly,
> in the mean time, I have a minor question:
>
> 1. I have a list L: for every number between 1..N I would like to
> check that it is contained in L exactly k times I have implemented my
> way of doing that (possibly the inefficient way), could you help with
> that?
>
> 2. When checking my program, it works when I provide it a list, that
> is it answers correctly to the question whether the input is a legal
> langford sequence or not, but when I run it: test(3,2,L) I get a
> message: "instantiation fault in _298{[1 .. 3]} =:= 3" what might be
> the problem?
>
> Now the new solution:
>
> % The algorithm:
> % 1. verify that each number (1..N) is contained in the list exactly K
> times.
> % 2. for each item i in the list the following invariant:
> % either the item following it by i items is similar to it
> % or it is the last occurrence of i in the list
> %
> % Therefore the algorithm verifies the first claim, and then
> recursively walks on the
> % list checking for each i the second attribute.
>
> :- lib(apply_macros).
> :- lib(fd).
>
> % N - the range of the numbers in the list - 1..N
> % K - the number of sets of N numbers in the list
> % L - the sequence
> langford(N,K,L) :-
> Length is N*K,
> length(L,Length),
> L :: [1..N],
> validateN(L,K,N),
> langford_test(L).
>
> langford_test([]).
>
> % recursively walk on the list while validate succeeds.
> % validate peeks if the value of the element which is H elements after
> H in the list is similar to H or
> % this is the last occurrence of H in the list.
> langford_test([H|T]) :-
> Inc is H,
> validate(H,T,Inc),
> langford_test(T).
>
> validate(_,[],_).
>
> validate(XX,[H|_],0) :-
> XX is H.
>
> validate(XXX,[H|T],0) :-
> XXX =\= H,
> validate1(XXX,T).
>
> validate(X,[_|T],Inc) :-
> Inc > 0,
> Inc1 is (Inc - 1),
> validate(X,T,Inc1).
>
> validate1(_,[]).
> validate1(X,[H|T]) :-
> X =\= H,
> validate1(X,T).
>
> % -------------------------------------
> % utilities
> % -------------------------------------
>
> % recursively walk on all the elements between N and 1
> validateN([],_,_).
> validateN(_,_,0).
>
> % List - the list to validate
> % K - The expected number of copies
> % I - The number currently validated
> validateN(List,K,I) :-
> I>0,
> % verify that for the number I there are K occurrences in List
> validateK(List,I,K),
> II is I-1,
> validateN(List,K,II).
>
> validateK([],_,0).
>
> % [H|T] - the list currently examined
> % I - the number currently verified
> % K - the number of occurrences of I expected in [H|T]
> validateK([H|T],I,K) :-
> H =:= I,
> % if H is equal to I then K is decremented
> KK is K-1,
> validateK(T,I,KK).
>
> % [H|T] - the list currently examined
> % I - the number currently verified
> % K - the number of occurrences of I expected in [H|T]
> validateK([HH|TT],_I,_K) :-
> % if H is not equal to I then K is not decremented, but the
> recursion continues.
> HH =\= _I,
> validateK(TT,_I,_K).
>
>
> I think, that the algorithm and even its implementation is correct,
> but somewhere in the middle with prolog I have some mistake.
>
> If you have any comments regarding the style, please do,
> Thanks,
> Zeus
First, I would like to thank you for bringing this fascinating little
problem to this newsgroup.
Second, I don't want to interrupt your train of thought, but I think
you were already on the right track.
As to your first question, I am not familiar with
L :: [1..N]
but unless it has the effect here of filling in the "empty" slots of L
with integers in the range [1..N], I would expect the predicate
> langford(N,K,L) :-
> Length is N*K,
> length(L,Length),
> L :: [1..N],
> validateN(L,K,N),
> langford_test(L).
to give you an instantiation error when called in (i,i,o) mode.
More to the point, you seem to me to be thinking i.t.o. applying a
battery of sufficiency tests to an already-constructed object, rather
than (as you were doing in your earlier approach) stagewise filling-in a
given template in such a way that the finished product is guaranteed to
have the desired properties by construction.
I find your style commendable but you seem to me to be using Prolog
more as a functional programming language than as a logic
programming language.
Of course, since predicates in which some particular argument is
logically speaking a function of all the others occur in most Prolog
programs, most Prolog programs are a mixture of both styles, but I think
the distinction is nevertheless a meaningful and useful one to make.
In logic programming and theorem-proving based on the first order
predicate language, it is not unusual for the "dimensions" of the
problem being described to translate into corresponding "textual
dimensions" of the description and, in such cases, sometimes the
simplest way to parameterize the problem is to use a preprocessor to
"parameterize" the text.
For example, let sublist_i_k(I,K,L) iff L is a list consisting of
K occurrences of the integer I, successive occurrences of I being
separated by I dummy variables, K>1, I>0. That is,
sublist_i_k(3,4,L) => L = [3, _, _, _, 3, _, _, _, 3, _, _, _, 3]
etc.
Then, without too much effort, I can say
test_3_2 :-
make_list(6,L),
sublist_i_k(1,2,L12),
is_sublist(L12,L),
sublist_i_k(2,2,L22),
is_sublist(L22,L),
sublist_i_k(3,2,L32),
is_sublist(L32,L),
write(L),nl.
and if I execute the goal
?- test_3_2,fail.
I get
[3, 1, 2, 1, 3, 2]
[2, 3, 1, 2, 1, 3]
Now comes the question: how can I generalize this solution without
sacrificing simplicity or intelligibility?
One obvious possibility is, rather than laboriously typing in a new
'test_n_k' for each n and k, to use Prolog to do it:
gen_clause(N,K) :-
write('test_'),write(N),write('_'),write(K),write(' :-'),nl,
NK is N*K,
write('make_list('),
write(NK),
write(','),
write('L'),
write('),'),nl,
member_list(I,1,N),
write('sublist_i_k('),
write(I),
write(','),
write(K),
write(','),
write('L'),write('_'),write(I),write('_'),write(K),
write('),'),nl,
write('is_sublist('),
write('L'),write('_'),write(I),write('_'),write(K),
write(','),
write('L'),
write('),'),nl,
fail.
gen_clause(N,K) :-
write('write('),
write('L'),
write(').'),nl.
For example, executing the goal
?- tell(test_17_3),gen_clause(17,3),told.
gives me a text file named 'test_17_3' that contains
test_17_3 :-
make_list(51,L),
sublist_i_k(1,3,L_1_3),
is_sublist(L_1_3,L),
sublist_i_k(2,3,L_2_3),
is_sublist(L_2_3,L),
sublist_i_k(3,3,L_3_3),
is_sublist(L_3_3,L),
sublist_i_k(4,3,L_4_3),
is_sublist(L_4_3,L),
sublist_i_k(5,3,L_5_3),
is_sublist(L_5_3,L),
sublist_i_k(6,3,L_6_3),
is_sublist(L_6_3,L),
sublist_i_k(7,3,L_7_3),
is_sublist(L_7_3,L),
sublist_i_k(8,3,L_8_3),
is_sublist(L_8_3,L),
sublist_i_k(9,3,L_9_3),
is_sublist(L_9_3,L),
sublist_i_k(10,3,L_10_3),
is_sublist(L_10_3,L),
sublist_i_k(11,3,L_11_3),
is_sublist(L_11_3,L),
sublist_i_k(12,3,L_12_3),
is_sublist(L_12_3,L),
sublist_i_k(13,3,L_13_3),
is_sublist(L_13_3,L),
sublist_i_k(14,3,L_14_3),
is_sublist(L_14_3,L),
sublist_i_k(15,3,L_15_3),
is_sublist(L_15_3,L),
sublist_i_k(16,3,L_16_3),
is_sublist(L_16_3,L),
sublist_i_k(17,3,L_17_3),
is_sublist(L_17_3,L),
write(L).
which, using a text editor, I can incorporate into my program.
And, if I now execute the goal
:- test_17_3,fail.
I get
[1,8,1,2,1,16,2,3,17,2,8,3,12,4,13,3,14,15,4,8,6,10,16,4,11,12,17,6,13,7,9,14,10,15,6,5,11,7,12,16,9,5,13,10,17,7,14,5,11,15,9]
[1,11,1,2,1,16,2,3,14,2,8,3,17,11,12,3,4,15,13,8,10,4,16,14,9,11,4,12,8,7,17,10,13,15,9,5,6,7,14,16,12,5,10,6,9,7,13,5,17,15,6]
[1,14,1,2,1,8,2,3,16,2,17,3,5,13,8,3,14,15,5,9,11,12,7,8,5,16,10,13,17,9,7,14,11,15,12,4,6,10,7,9,4,13,16,6,11,4,17,12,10,15,6]
[1,12,1,2,1,17,2,3,13,2,7,3,16,5,12,3,11,15,7,5,14,10,13,17,9,5,7,12,11,16,8,6,10,15,9,14,13,4,6,8,11,17,4,10,9,6,16,4,8,15,14]
[1,10,1,2,1,16,2,3,7,2,14,3,10,17,15,3,7,11,9,12,13,5,16,10,7,14,8,5,9,11,15,17,12,5,13,8,6,4,9,16,14,11,4,6,8,12,15,4,13,17,6]
[1,11,1,2,1,17,2,3,10,2,16,3,5,11,13,3,9,15,5,10,14,12,8,17,5,11,9,16,13,7,10,8,6,15,12,14,9,7,4,6,8,17,13,4,16,7,6,12,4,15,14]
[1,14,1,2,1,15,2,3,8,2,17,3,5,16,12,3,14,8,5,9,11,15,13,10,5,7,8,12,17,9,16,14,11,7,10,6,13,15,4,9,12,7,6,4,11,10,17,16,4,6,13]
...
etc.
Not too bad, taking into consideration the fact that I am using a
400MHz AMD k6-3 cpu. I was frankly surprised to get any answers at all,
and I look forward to seeing how well a "closed form" method of dealing
with the general case performs in comparison.
billh
- Next message: Matthew Huntbach: "Re: Mainstreaming Prolog a Pragmatic Approach?"
- Previous message: zeus: "Re: Sublists question"
- In reply to: zeus: "Re: Sublists question"
- Next in thread: zeus: "Re: Sublists question"
- Reply: zeus: "Re: Sublists question"
- Reply: Bart Demoen: "Re: Sublists question"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
