Prolog - Sublists question

Author

Sublists question

zeus

2004-03-27, 12:10 am

I want to implement the following algorithm in prolog:

given n,k:
I want to find a list L such that:
L=(_,_,...._) /* n*k variables */
for all i:1..n
L1=generate a list(i,_,_...,i,_,_,...i) /*k times i with i
variables between each two consecutive i's */
sublist(L1,L)

as I'm newbie to prolog, my questions are:
how can I generate such a sublist?
(As you can see it is a solution to the langford sequence problem)

Nick Wedd

2004-03-27, 12:10 am

In message <f238fff9.0403172317.325bf9d4@posting.google.com>, zeus
<zohar@sheernetworks.com> writes
>I want to implement the following algorithm in prolog:
>
>given n,k:
>I want to find a list L such that:
>L=(_,_,...._) /* n*k variables */
>for all i:1..n
> L1=generate a list(i,_,_...,i,_,_,...i) /*k times i with i
>variables between each two consecutive i's */
> sublist(L1,L)
>
>
>as I'm newbie to prolog, my questions are:
>how can I generate such a sublist?
>(As you can see it is a solution to the langford sequence problem)

Generate the sublists, then append them together to make the main list.

Nick
--
Nick Wedd nick@maproom.co.uk

Bill Spight

2004-03-27, 12:10 am

Dear zeus,

> I want to implement the following algorithm in prolog:
>
> given n,k:
> I want to find a list L such that:
> L=(_,_,...._) /* n*k variables */
> for all i:1..n
> L1=generate a list(i,_,_...,i,_,_,...i) /*k times i with i
> variables between each two consecutive i's */
> sublist(L1,L)
>
>
> as I'm newbie to prolog, my questions are:
> how can I generate such a sublist?
> (As you can see it is a solution to the langford sequence problem)

I am not sure what you want. Let n = 1, k = 2.

Then

L = [A,B].

L1 = [1,X,1].

There is no way for L1 to be a sublist of L, as it is longer.

Also, you might start by writing a sublist predicate. Break the problem
down.

Good luck!

Bill

zeus

2004-03-27, 12:10 am

Bill Spight <Xbspight@pacbell.net> wrote in message news:<4059B905.AFDD1A9F@pacbell.net>...
> Dear zeus,
>
>
> I am not sure what you want. Let n = 1, k = 2.
>
> Then
>
> L = [A,B].
>
> L1 = [1,X,1].
>
> There is no way for L1 to be a sublist of L, as it is longer.
>
> Also, you might start by writing a sublist predicate. Break the problem
> down.
>
> Good luck!
>
> Bill

Well, first its is invariant that n>3.
I'll give an example with n=3 k=2:

I would like to generate L=(_,_,_,_,_,_),
and L1=(1,_,1), L2=(2,_,_,2), L3=(3,_,_,_,3) and find the list L such
that L1,L2,L3 are its sublists. if my problem was specific this was
the predicate I would give:

sequence([_,_,_,_,_,_]).
solve(L):-
sequence(L),
sublist([3,_,_,_,3],L),
sublist([2,_,_,2],L),
sublist([1,_,1],L).

But I want to generalize it to any N, so first how do I create the
sequence with n variables? then how do I generate recursively the
sublists L1-Ln?

Thanks
Zeus

Nick Wedd

2004-03-27, 12:10 am

In message <f238fff9.0403182205.3d8adad4@posting.google.com>, zeus
<zohar@sheernetworks.com> writes
>Bill Spight <Xbspight@pacbell.net> wrote in message
>news:<4059B905.AFDD1A9F@pacbell.net>...
>
>Well, first its is invariant that n>3.
>I'll give an example with n=3 k=2:

I am finding your questions hard to understand. You say n>3, then you
say n=3. So my advice below may address the wrong questions.

>I would like to generate L=(_,_,_,_,_,_),
>and L1=(1,_,1), L2=(2,_,_,2), L3=(3,_,_,_,3) and find the list L such
>that L1,L2,L3 are its sublists. if my problem was specific this was
>the predicate I would give:
>
>sequence([_,_,_,_,_,_]).
>solve(L):-
> sequence(L),
> sublist([3,_,_,_,3],L),
> sublist([2,_,_,2],L),
> sublist([1,_,1],L).
>
>But I want to generalize it to any N, so first how do I create the
>sequence with n variables?

Write a predicate length( List, N ) which given a list, calculates its
length. Then call it with N instantiated and List uninstantiated.

> then how do I generate recursively the
>sublists L1-Ln?

Why do you want to do this recursively?

If I have understood your question, you want a predicate that, given an
integer N, generates a list of length N+2, with the first and last
elements being N and the rest being _. Is this right?

Nick
--
Nick Wedd nick@maproom.co.uk

Bill Spight

2004-03-27, 12:10 am

Dear Nick and zeus,

zeus:
>

Nick:
> Write a predicate length( List, N ) which given a list, calculates its
> length. Then call it with N instantiated and List uninstantiated.
>

zeus:
>

Nick:
> Why do you want to do this recursively?
>

Look at zeus's example. Instead of

sublist([3,_,_,_,3],L),
sublist([2,_,_,2],L),
sublist([1,_,1],L).

I think zeus would like to replace those with a recursive predicate.
Something like this:

solve_langford(N,K) :-
Length is N*K,
length(L,Length),
langford_sublists(N,K,L).

> If I have understood your question, you want a predicate that, given an
> integer N, generates a list of length N+2, with the first and last
> elements being N and the rest being _. Is this right?

I think it is more general. E. g.,

langford_sublist(K,N,Sublist)

Such that

langford_sublist(3,1,Sublist) yields Sublist = [1,_,1,_,1],
langford_sublist(2,2,Sublist) yields Sublist = [2,_,_,2],
langford_sublist(4,3,Sublist) yields Sublist =
[3,_,_,_,3,_,_,_,3,_,_,_,3],

etc.

Hint:

zeus, I think it might help to define

langford_sublist(1,N,[N]).

Best,

Bill

zeus

2004-03-27, 12:10 am

Bill Spight <Xbspight@pacbell.net> wrote in message news:<405B1418.EE633CBB@pacbell.net>...
> Dear Nick and zeus,
>
> zeus:
>
> Nick:
>
> zeus:
>
> Nick:
>
> Look at zeus's example. Instead of
>
> sublist([3,_,_,_,3],L),
> sublist([2,_,_,2],L),
> sublist([1,_,1],L).
>
> I think zeus would like to replace those with a recursive predicate.
> Something like this:
>
> solve_langford(N,K) :-
> Length is N*K,
> length(L,Length),
> langford_sublists(N,K,L).
>
>
> I think it is more general. E. g.,
>
> langford_sublist(K,N,Sublist)
>
> Such that
>
> langford_sublist(3,1,Sublist) yields Sublist = [1,_,1,_,1],
> langford_sublist(2,2,Sublist) yields Sublist = [2,_,_,2],
> langford_sublist(4,3,Sublist) yields Sublist =
> [3,_,_,_,3,_,_,_,3,_,_,_,3],
>
> etc.
>
> Hint:
>
> zeus, I think it might help to define
>
> langford_sublist(1,N,[N]).
>
>
> Best,
>
> Bill

Bill, you understood correctly.
So I need to have 3 predicates:
1. solveLangford(N,K) :-
Length is N*K,
length(L,Length),
test_all_sublists(N,K,L).

2. test_all_sublists should (recursively?) generate all N sublists
using langford_sublist you suggested and test if they are sublists of
L. I guess this one I can handle myself.

3. langford_sublist(N,K,List) should generate the sublist of the
number N with its K instances spaced correctly. This I guess is back
to square one, being more understood, how do I generate this List?

langford_sublist(3,1,Sublist) yields Sublist = [1,_,1,_,1],
langford_sublist(2,2,Sublist) yields Sublist = [2,_,_,2],
langford_sublist(4,3,Sublist) yields Sublist
=[3,_,_,_,3,_,_,_,3,_,_,_,3]

Help!!!!!

Thanks,
Zeus

Nick Wedd

2004-03-27, 12:10 am

In message <f238fff9.0403200117.54cb94b3@posting.google.com>, zeus
<zohar@sheernetworks.com> writes

>3. langford_sublist(N,K,List) should generate the sublist of the
>number N with its K instances spaced correctly. This I guess is back
>to square one, being more understood, how do I generate this List?
>
>langford_sublist(3,1,Sublist) yields Sublist = [1,_,1,_,1],
>langford_sublist(2,2,Sublist) yields Sublist = [2,_,_,2],
>langford_sublist(4,3,Sublist) yields Sublist
>=[3,_,_,_,3,_,_,_,3,_,_,_,3]

You want to write langford_sublist( P, Q, List ). So break it into
simple tasks.
Write a predicate which, given Q, yields a list of Q _s and a Q.
Then write a predicate which, given P and Q, yields a list of a Q
followed by (P-1) of the above.

Nick
--
Nick Wedd nick@maproom.co.uk

zeus

2004-03-27, 12:10 am

Nick Wedd <nick@maproom.co.uk> wrote in message news:<4Hv9ceL01BXAFAES@maproom.demon.co.uk>...
> In message <f238fff9.0403200117.54cb94b3@posting.google.com>, zeus
> <zohar@sheernetworks.com> writes
>
>
> You want to write langford_sublist( P, Q, List ). So break it into
> simple tasks.
> Write a predicate which, given Q, yields a list of Q _s and a Q.
> Then write a predicate which, given P and Q, yields a list of a Q
> followed by (P-1) of the above.
>
> Nick

I implemented my solution as you suggested, it seems very tedious to
me, I didn't yet tested to see if it actually works (probably not...).
Anyways, this is what I understood from you suggestion Nick, what do
you think about it?

% finding a solution for the langford problem
solve_langford(N,K) :-
Length is N*K,
length(L,Length),
langford_sublists(N,K,L).

% recursive generation and testing of all sublists for 1..N against L
langford_sublists(N,K,L) :-
N>0,
insert(N,List),
insertCopies(N,K-1,List),
subList(List,L),
langford_sublists(N-1,K,List).

% generate I copies of the form N varaibles followed by the number N
% e.g. insertCopies(3,2,List) - List=(_,_,_,3,_,_,_,3)
insertCopies(N,I,List) :-
I>0,
generateNVars(N,SubList),
insert(N,SubList),
append(Sublist,List,List),
insertCopies(N,I-1,List).

% generate N variables list
generateNVars(N,List) :-
N > 0,
insert(_,List),
generateNVars(N-1,List).

(Please remember this is the first program I write in prolog, so if
I'm making stupid mistakes, don't be mean...)
(BTW, thanks!)

zeus

2004-03-27, 12:10 am

Nick Wedd

2004-03-27, 12:11 am

In message <f238fff9.0403210232.432c55fc@posting.google.com>, zeus
<zohar@sheernetworks.com> writes

>I implemented my solution as you suggested, it seems very tedious to
>me, I didn't yet tested to see if it actually works (probably not...).
>Anyways, this is what I understood from you suggestion Nick, what do
>you think about it?

I will leave it to you to test. There are some errors:

>% finding a solution for the langford problem
>solve_langford(N,K) :-
> Length is N*K,
> length(L,Length),
> langford_sublists(N,K,L).
>
>% recursive generation and testing of all sublists for 1..N against L
>langford_sublists(N,K,L) :-
> N>0,
> insert(N,List),
> insertCopies(N,K-1,List),
> subList(List,L),
> langford_sublists(N-1,K,List).

What happens when N is 0?
What do you think happens if Prolog finds the tail goal
6-1>0
?

>% generate I copies of the form N varaibles followed by the number N
>% e.g. insertCopies(3,2,List) - List=(_,_,_,3,_,_,_,3)
>insertCopies(N,I,List) :-
> I>0,
> generateNVars(N,SubList),
> insert(N,SubList),
> append(Sublist,List,List),
> insertCopies(N,I-1,List).

What happens when I is 0?

>% generate N variables list
>generateNVars(N,List) :-
> N > 0,
> insert(_,List),
> generateNVars(N-1,List).

What happens when N is 0? And what does insert/2 do? Ok, I will help
you with this one.

generateNVars( 0, [] ).
generateNVars( N, [_|T] ) :-
NM is N-1,
generateNVars( NM, T ).

>(Please remember this is the first program I write in prolog, so if
>I'm making stupid mistakes, don't be mean...)
>(BTW, thanks!)

This is an ambitious choice for your first Prolog program.

Nick
--
Nick Wedd nick@maproom.co.uk

zeus

2004-03-27, 12:11 am

Nick Wedd <nick@maproom.co.uk> wrote in message news:<bPZ1+3Bu8rXAFABm@maproom.demon.co.uk>...
> In message <f238fff9.0403210232.432c55fc@posting.google.com>, zeus
> <zohar@sheernetworks.com> writes
>
>
> I will leave it to you to test. There are some errors:
>
>
> What happens when N is 0?
> What do you think happens if Prolog finds the tail goal
> 6-1>0
> ?
>
>
> What happens when I is 0?
>
>
> What happens when N is 0? And what does insert/2 do? Ok, I will help
> you with this one.
>
> generateNVars( 0, [] ).
> generateNVars( N, [_|T] ) :-
> NM is N-1,
> generateNVars( NM, T ).
>
>
> This is an ambitious choice for your first Prolog program.
>
> Nick

First off, thanks for the patience, I know its pretty ambitious,
however, that what I need to do.

My questions are inlined as remarks:

% I assume this is fine, as this is pretty simple and straight forward
solve_langford(N,K) :-
Length is N*K,
length(L,Length),
langford_sublists(N,K,L).

% how do you define a predicate saying that langford_sublist on N=0
and
% any given K,L should be empty: langford_sublists(0,K,L). is this
legal?
langford_sublists(N,K,L) :-
N>0,
insert(N,List),
% do I need to do this or can I use directly K-1? and why?
KK is K-1,
insertCopies(N,KK,List),
subList(List,L),
NN is N-1,
langford_sublists(NN,K,L).

% same question as before, how do I formulate that
insertCopies(N,0,List) should be empty (as insertCopies(N,0,List). ?)
insertCopies(N,I,List) :-
I>0,
generateNVars(N,SubList),
insert(N,SubList),
% is this legal prolog at all? I want to append sublist to list
and assign
% the result to list??
append(Sublist,List,List),
II is I-1,
insertCopies(N,II,List).

% this is yours and clear so no quesions..
generateNVars( 0, [] ).

generateNVars( N, [_|T] ) :-
NM is N-1,
generateNVars( NM, T ).

Thanks, again,
Zeus

Nick Wedd

2004-03-27, 12:11 am

In message <f238fff9.0403220639.7192b941@posting.google.com>, zeus
<zohar@sheernetworks.com> writes

>First off, thanks for the patience, I know its pretty ambitious,
>however, that what I need to do.
>
>My questions are inlined as remarks:
>
>% I assume this is fine, as this is pretty simple and straight forward
>solve_langford(N,K) :-
> Length is N*K,
> length(L,Length),
> langford_sublists(N,K,L).
>
>% how do you define a predicate saying that langford_sublist on N=0
>and
>% any given K,L should be empty: langford_sublists(0,K,L). is this
>legal?

I don't understand what you are trying to do here.

>langford_sublists(N,K,L) :-
> N>0,
> insert(N,List),
> % do I need to do this or can I use directly K-1? and why?
> KK is K-1,
> insertCopies(N,KK,List),
> subList(List,L),
> NN is N-1,
> langford_sublists(NN,K,L).

You have to specify KK is K-1 . If you don't, you will just be
passing the term K-1 in the next call to insertCopies, and the
subtraction won't actually happen anywhere. You need to force it to
evaluate K-1.

>% same question as before, how do I formulate that
>insertCopies(N,0,List) should be empty (as insertCopies(N,0,List). ?)

I am not sure that I understand what you are trying to do. I guess that
you are writing insertCopies( N, K, L) and you want the list L to be
empty when K is 0. Here is how to do that:
insertCopies( _, 0, [] ).

>insertCopies(N,I,List) :-
> I>0,
> generateNVars(N,SubList),
> insert(N,SubList),
> % is this legal prolog at all? I want to append sublist to list
>and assign
> % the result to list??
> append(Sublist,List,List),
> II is I-1,
> insertCopies(N,II,List).

insert(N,SubList) is legal Prolog. But if you don't define insert/2,
it won't do anything, it will just fail.

>% this is yours and clear so no quesions..
>generateNVars( 0, [] ).
>
>generateNVars( N, [_|T] ) :-
> NM is N-1,
> generateNVars( NM, T ).

Yes, but study how I wrote it, and use the same technique for your other
predicates.

Nick
--
Nick Wedd nick@maproom.co.uk

zeus

2004-03-27, 12:11 am

Nick Wedd <nick@maproom.co.uk> wrote in message news:<UUoGobKqIyXAFAQ4@maproom.demon.co.uk>...
> In message <f238fff9.0403220639.7192b941@posting.google.com>, zeus
> <zohar@sheernetworks.com> writes
>
>
> I don't understand what you are trying to do here.
>
>
> You have to specify KK is K-1 . If you don't, you will just be
> passing the term K-1 in the next call to insertCopies, and the
> subtraction won't actually happen anywhere. You need to force it to
> evaluate K-1.
>
>
> I am not sure that I understand what you are trying to do. I guess that
> you are writing insertCopies( N, K, L) and you want the list L to be
> empty when K is 0. Here is how to do that:
> insertCopies( _, 0, [] ).
>
>
> insert(N,SubList) is legal Prolog. But if you don't define insert/2,
> it won't do anything, it will just fail.
>
>
> Yes, but study how I wrote it, and use the same technique for your other
> predicates.
>
> Nick

Nick I made lotsa progress:

solve_langford(N,K) :-
Length is N*K,
length(L,Length),
langford_sublists(N,K,L).

%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),
sublist(List,L),
NN is N-1,
langford_sublists(NN,K,L).

% responsible for generating one sublist
generate_list(N,I,List) :-
I>0,
II is I-1,
NN is N+1,

% the intention is if (II mod NN is 0) then
generate_list(N,II,[N|List]) else generate_list(N,II,[_|List])

((II mod NN is 0,generate_list(N,II,[N|List]));
generate_list(N,II,[_|List].

The only thing I'm still missing is the handling for the case I=0 in
generate_list and N=0 in langford_sublists.

I'll try to work it out by myself, but feel free to advise!

Thanks,
Zues

Nick Wedd

2004-03-27, 12:11 am

In message <f238fff9.0403230524.7c19f7c8@posting.google.com>, zeus
<zohar@sheernetworks.com> writes

>The only thing I'm still missing is the handling for the case I=0 in
>generate_list and N=0 in langford_sublists.

Start by thinking about what you want to happen in these cases.

>I'll try to work it out by myself, but feel free to advise!

Nick
--
Nick Wedd nick@maproom.co.uk

Bill Spight

2004-03-27, 12:11 am

Dear zeus,

> solve_langford(N,K) :-
> Length is N*K,
> length(L,Length),
> langford_sublists(N,K,L).
>

I'm afraid I led you a bit astray with that. You want to return the
Langford list (L), right? So it needs to be

solve_langford(N,K,L) :-

etc.

Good luck!

Bill

zeus

2004-03-27, 12:11 am

Bill Spight <Xbspight@pacbell.net> wrote in message news:<406096BE.72CD1068@pacbell.net>...
> Dear zeus,
>
>
> I'm afraid I led you a bit astray with that. You want to return the
> Langford list (L), right? So it needs to be
>
> solve_langford(N,K,L) :-
>
> etc.
>
> Good luck!
>
> Bill

Thanks guys, I'm only a mile from the end of it:I completed the
program, and now it compiles and even finds the langford sequence for
N=3 K=2. But when I invoke it with N=4, K=2 or N=3, K=3 then I get the
message:
"Out of global stack", which probably means I've done something
extremely inefficiently. I'd aprreciate it, if you could take a look
and see, what have I done wrong:

langford(N,K,L) :-
Length is N*K,
length(L,Length),
langford_sublists(N,K,L).

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

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

append([],L,L).
append([H|T],L,[H|LT]):-append(T,L,LT).
sublist(S,L):-append(_,S,P),append(P,_,L).

Bart Demoen

2004-03-27, 12:11 am

zeus wrote:

> Thanks guys, I'm only a mile from the end of it:I completed the
> program, and now it compiles and even finds the langford sequence for
> N=3 K=2. But when I invoke it with N=4, K=2 or N=3, K=3 then I get the
> message:
> "Out of global stack", which probably means I've done something
> extremely inefficiently. I'd aprreciate it, if you could take a look
> and see, what have I done wrong:
>
> langford(N,K,L) :-
> Length is N*K,
> length(L,Length),
> langford_sublists(N,K,L).
>
> 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).
>
> 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).
>
> append([],L,L).
> append([H|T],L,[H|LT]):-append(T,L,LT).
> sublist(S,L):-append(_,S,P),append(P,_,L).

without knowing what a langford list should be ...

you must have ignored a singleton variable warning from your Prolog
system - for the List variable in the recursive clause of langford_sublists

also, your definition of sublist is flawed wrt the instantiation of its
arguments at the moment of the call

finally: never think that your program works if it delivers a first correct solution;
try the query ?- langford(3,2,L), write(L), nl, fail.
and you will see what I mean

cheers

Bart Demoen

Bill Spight

2004-03-27, 12:11 am

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,

Bill

P. S. After a query has produced an answer, to get another one, if
Prolog can find it, enter a semicolon.

zeus

2004-03-27, 12:11 am

Bill Spight <Xbspight@pacbell.net> wrote in message news:<4061F60C.C38F0A28@pacbell.net>...
> Dear zeus,
>
> Bart's comments are right on. :-)
>
>
> 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.

Understood, thanks.

>
>
> 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.
>
>
> 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:
>
>
> _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,
>
> Bill
>
> P. S. After a query has produced an answer, to get another one, if
> Prolog can find it, enter a semicolon.

I don't understand whats wrong in the generate_list logics.
I'm using ECLiPSe.
What I intend to do in the 3 generate lists prdeicates is this:
for N=1, I=3 generate the list [1,_,1,_,1] which at the end of the
recursion when I=0 will be tested to be sublist of L. somehow it
doesn't work, but I don't understand why.
HHHHHEEELLLLLLLLP. I'm pretty desperate, this logic programming can be
very tedious.

Thanks.

Bill Spight

2004-03-27, 12:11 am

Dear zeus,

> I don't understand whats wrong in the generate_list logics.
> I'm using ECLiPSe.
> What I intend to do in the 3 generate lists prdeicates is this:
> for N=1, I=3 generate the list [1,_,1,_,1] which at the end of the
> recursion when I=0 will be tested to be sublist of L. somehow it
> doesn't work, but I don't understand why.

There is a general rule of thumb for programing: Do one thing and do it
well. That holds for Prolog predicates, too.

You are trying to do two things with generate_list/4: generate a list of
a certain kind and then test whether the list is a sublist of another
list. Why not do only one thing with generate_list/4, and do it well:
generate a Langford sublist. E. g.,

generate_list(K,N,List) generates a Langford sublist, given a number,
N, which appears in the list K times N places apart.

This will also solve the singleton variable problem in a natural way.

%recursively generate and test all sublists

langford_sublists(0,_,_).
langford_sublists(N,K,L) :-
N>0,
generate_list(K,N,List), % List appears here
sublist(List,L), % and here.
NN is N-1,
langford_sublists(NN,K,L).

Good luck!

Bill

zeus

2004-03-27, 12:11 am

Bill Spight <Xbspight@pacbell.net> wrote in message news:<4061F60C.C38F0A28@pacbell.net>...
> Dear zeus,
>
> Bart's comments are right on. :-)
>
>
> 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.
>
>
> 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.
>
>
> 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:
>
>
> _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 p

s 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

Bill Spight

2004-03-27, 12:11 am

Dear zeus,

> What I intend to do in the 3 generate lists prdeicates is this:
> for N=1, I=3 generate the list [1,_,1,_,1]

I see a problem. 'I' is the size of the list. So you should have I = 5,
not I = 3.

> which at the end of the
> recursion when I=0 will be tested to be sublist of L

I = 0? Why would you decrease the size of the list? Are you building a
list from its sublists?

OK, I think I see what you are up to. Let's clean the predicate up by
eliminating the sublist test.

generate_list(_,0,_).

% responsible for placing the Ns in the sublist
generate_list(N,I,List) :-
I>0,
II is I-1,
NNN is N+1,
III is II mod NNN,
III is 0,
generate_list(N,II,[N|List]).

What you are doing here is building a list from the bottom, by adding N
*before* it. That's OK if you call generate_list/3 like this:
generate_list(N,Size,[]), with the empty list. But then how do you
return the eventual list that you have built? You need another variable
for that: generate_list(N,Size,[],List).

You can do it that way, but I think what you want to do is build the
list from left to right. Here's how to do that.

generat_list(_,0,[]).

A list of length 0 is empty.

generate_list(N,I,[Head|Tail]) :-
I>0,
II is I-1,
NNN is N+1,
III is II mod NNN,
III is 0,
Head = N,
generate_list(N,II,Tail).

% responsible for placing the variables in the sublist
generate_list(N,I,[_|Tail]) :-
I>0,
II is I-1,
generate_list(N,II,Tail).

In the one case, the head of the list is N, in the other, it is
undetermined.

Note that you have a dependency in the clauses. The third clause assumes
that the second has failed. Often that's the way to go, for practical
reasons, to avoid unnecessary tests inside a loop. But you should be
aware that you are getting away from a logical reading of the predicate.

This still may not work, but I think it's closer to what you want to do.
:-)

Good luck!

Bill

Bill Spight

2004-03-27, 12:11 am

Dear zeus,

I wrote:

> This still may not work, but I think it's closer to what you want to do.

It needs just one minor change, now. I think I can leave that as an
exercise for the reader. ;-)

Best,

Bill

zeus

2004-03-27, 12:11 am

zohar@sheernetworks.com (zeus) wrote in message news:<f238fff9.0403250916.70ba3225@posting.google.com>...
> Bill Spight <Xbspight@pacbell.net> wrote in message news:<4061F60C.C38F0A28@pacbell.net>...
>
> 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 p

billh

2004-03-27, 12:11 am

zeus wrote:
> Bill Spight <Xbspight@pacbell.net> wrote in message news:<4061F60C.C38F0A28@pacbell.net>...
>
>
>
> 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 p

s 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

& #91;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]
& #91;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]
& #91;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,1
2,10,15,6]
& #91;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]
& #91;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]
& #91;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,1
2,4,15,14]
& #91;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,1
4,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

Bill Spight

2004-03-27, 12:11 am

Dear zeus,

> generat_list(_,0,[]).
> generate_list(N,I,[Head|Tail]) :-
> I>0,
> II is I-1,
> NNN is N+1,
> III is II mod NNN,
> III is 0,
> Head = N,
> generate_list(N,II,Tail).
>
> % responsible for placing the variables in the sublist
> generate_list(N,I,[_|Tail]) :-
> I>0,
> II is I-1,
> generate_list(N,II,Tail).
>
> It still doesn't work and nowm I really can't figure why.
> Thanks.

Did you catch my typo? The first clause should be

generate_list(_,0,[]).

The problem is in the third clause.

generate_list(N,I,[_|Tail]) :-
I>0,
II is I-1,
generate_list(N,II,Tail).

This says that the list (of length I > 0) being generated has an
undefined variable as its head, and a tail that can be generated by the
same predicate with the number, N. That, as we know, is incorrect.

This is correct.

generate_list(N,I,[_|Tail]) :-
I>0,
II is I-1,
NNN is N+1,
III is II mod NNN,
III =\= 0,
generate_list(N,II,Tail).

However, this is inefficient, since it repeats the test of the previous
clause, succeeding where it fails. In fact, we know that if the previous
clause succeeds, this one should fail.

The traditional way of dealing with this inefficiency is to use the cut,
which is written with an exclamation point: !. The cut prunes the
succeeding clauses of the predicate. That's not all there is to the cut.
There are good cuts and bad cuts, dangerous and benign. If you study
Prolog you need to become familiar with the cut. Here we know that the
cut is benign.

generate_list(_,0,[]).

generate_list(N,I,[Head|Tail]) :-
I>0,
II is I-1,
NNN is N+1,
III is II mod NNN,
III is 0,
!, % The test has succeeded, and we know that the Head is
N.
% No need to look further.
Head = N,
generate_list(N,II,Tail).

% responsible for placing the variables in the sublist
generate_list(N,I,[_|Tail]) :-
I>0,
II is I-1,
generate_list(N,II,Tail).

This works. :-)

However, it is not the best style. Today we have the If-Then-Else
construct, and it is better to combine the last two clauses.

generate_list(_,0,[]).

% responsible for placing the Ns in the sublist
generate_list(N,I,[Head|Tail]) :-
I>0,
II is I-1,
NNN is N+1,
III is II mod NNN,
(
III =:= 0 % If III equals 0 (arithmetic equality test)
-> % Then
Head = N
; % Else
true
),
generate_list(N,II,Tail).

Note that this is not a logical implication. If the condition fails, the
If-Then will also fail unless there is an Else clause. That's why we
need the 'true'.

For reference, we can clean this up a bit more.

Minor point: Better to have something that changes as the first argument
of a predicate. Most Prolog implementations index on it; so it's
slightly more efficient than having it be the same in each clause. So we
move the length of the list to the first place.

generate_list(0,_,[]) :- !.

%% Once we get here, we know that we are done, *and that there are no
more solutions*. The cut is benign. This saves us a test in the next
clause.

% responsible for placing the Ns in the sublist
generate_list(Length,N,[Head|Tail]) :-

%% Instead of I, how about Length? Use descriptive variable names.
%% No need to test if Length > 0. See the benign cut.

(
Length mod (N+1) =:= 1

%% Prolog can evaluate arthimetic expressions. No need to do it
piecemeal.
%% Test on Length instead of calculating Length -1 and testing on it.

->
Head = N
;
true
),
LL is Length-1,

%% Now we need to find Length - 1, not before.

generate_list(LL,N,Tail).

Best,

Bill

zeus

2004-03-27, 12:11 am

billh <sequitur@sonic.net> wrote in message news:<XbS8c.1965$Fo4.21052@typhoon.sonic.net>...
> zeus wrote:
>
> 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
>
>
> 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
>
> & #91;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]
> & #91;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]
> & #91;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,1
2,10,15,6]
> & #91;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]
> & #91;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]
> & #91;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,1
2,4,15,14]
> & #91;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,1
4,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

Imagine that guys, I finally made it. After a long time of struggling
with this I made it alright. You are right billh, I think as
functional programming more than logic programming as this is what I
am familiar with. It takes time getting used to programming in prolog,
but I think this way of "pure abstract" thinking is mind challenging
and fun.

So here's what I did finally:

langford(N,K,L) :-
Size is N*K,
length(L,Size),
make_list(Size,L),
all_sublists(N,K,L).

all_sublists(0,_,_).
all_sublists(N,K,L) :-
N>0,
NInc is N+1,
KDec is K-1,
Size is (NInc*KDec)+1,
sublist_i_k(N,K,List,Size),
sublist(List,L),
NN is N-1,
all_sublists(NN,K,L).

make_list(0,[]).
make_list(N,[_|T]) :-
N > 0,
NN is N-1,
make_list(NN,T).

sublist_i_k(_,0,[],0).
sublist_i_k(I,K,[H|T],Index) :-
Index>0,
II is Index-1,
NN is I+1,
III is II mod NN,
III is 0,
KK is K-1,
H is I,
Index1 is Index-1,
sublist_i_k(I,KK,T,Index1).

sublist_i_k(_I,_K,[_|Tail],_Index) :-
_Index > 0,
Index1 is _Index-1,
sublist_i_k(_I,_K,Tail,Index1).

append([],L,L).
append([H|T],L,[H|LT]):-append(T,L,LT).
sublist(Sublist,List) :-
append(Midlist,_,List),
append(_,Sublist,Midlist).

1. If anyone has comments, please do.
2. I want to add a counting for the backtracking made by prolog when
executing the program. I know its something with retract or something,
but I'm not sure of how to do it.

Bill Spight

2004-03-27, 12:11 am

Dear zeus,

FWIW, here is my current solution. I am sure it can be improved, but you
can see how I like to break things down into smaller, more
understandable parts.

prefix([X],[X|_]) :- !.
prefix([X|Xs],[X|Ys]) :-
prefix(Xs,Ys).

sublist(Sublist,List) :-
prefix(Sublist,List).
sublist(Sublist,[_|Tail]) :-
sublist(Sublist,Tail).

strip(0,List,List) :- !.
strip(N0,[_|Tail],Suffix) :-
N is N0 - 1,
strip(N,Tail,Suffix).

langford_sublist(1,N,[N]) :- !.
langford_sublist(K0,N,[N|Tail]) :-
strip(N,Tail,Suffix),
K is K0 - 1,
langford_sublist(K,N,Suffix).

% In langford_sublists(N,K,List), List must have a determinate length,
% and N and K are positive integers.

langford_sublists(0,_,_).
langford_sublists(N0,K,List) :-
langford_sublist(K,N0,Sublist),
sublist(Sublist,List),
N is N0 - 1,
langford_sublists(N,K,List).

langford_list(N,K,List) :-
Length is N * K,
length(List,Length),
langford_sublists(N,K,List).

Best,

Bill

Bill Spight

2004-03-27, 12:11 am

There's more than one way to skin a cat.

I thought that not bothering to build the sublists might be more
efficient, as well as not attempting to fit in numbers past the point
where they will.

Bill

langford_list(N,K,List) :-
Length is N * K,
length(List,Length),
fill_in_numbers(N,K,Length,List).

fill_in_numbers(0,_,_,_) :- !.
fill_in_numbers(N0,K,Length,List) :-
Size is N0 * K - N0 + K,
Diff is Length - Size,
fill_in_number(Diff,Size,N0,List),
N is N0 - 1,
fill_in_numbers(N,K,Length,List).

fill_in_number(-1,_,_,_) :-
!,
fail.
fill_in_number(_,Size0,N,[N|Tail]) :-
Size is Size0 - 1,
fill_in_number_1(Size,N,Tail).
fill_in_number(Diff0,Size,N,[_|Tail]) :-
Diff is Diff0 - 1,
fill_in_number(Diff,Size,N,Tail).

fill_in_number_1(0,_,_) :- !.
fill_in_number_1(Size0,N,List) :-
strip(N,List,[N|Tail]),
Size is Size0 - N - 1,
fill_in_number_1(Size,N,Tail).

strip(0,List,List) :- !.
strip(N0,[_|Tail],Suffix) :-
N is N0 - 1,
strip(N,Tail,Suffix).

Bill Spight

2004-03-27, 12:11 am

Dear zeus,

> Imagine that guys, I finally made it. After a long time of struggling
> with this I made it alright.

Congratulations! :-)

> If anyone has comments, please do.

OK. :-)

> langford(N,K,L) :-
> Size is N*K,
> length(L,Size),
> make_list(Size,L),
> all_sublists(N,K,L).

make_list/2 is redundant. length/2 has already constructed the template
list, L.

> sublist_i_k(_I,_K,[_|Tail],_Index) :-
> _Index > 0,
> Index1 is _Index-1,
> sublist_i_k(_I,_K,Tail,Index1).

Starting a variable name with an underscore normally means that the
variable is anonymous, but you do not just write '_' for readability. So
this is better:

sublist_i_k(I,K,[_|Tail],Index) :-
Index > 0,
Index1 is _Index-1,
sublist_i_k(I,K,Tail,Index1).

I'm glad you came through. :-)

Best,

Bill

Bill Spight

2004-03-27, 12:11 am

Correction:

I wrote:

> langford_list(N,K,List) :-
> Length is N * K,
> length(List,Length),
> fill_in_numbers(N,K,Length,List).

I might as well get real. ;-)

langford_list(N,K,List) :-
integer(N),
integer(K),
K > 0,
N >= K,
Length is N * K,
length(List,Length),
fill_in_numbers(N,K,Length,List).

Ciao,

Bill

Bart Demoen

2004-03-27, 11:59 pm

billh wrote:

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

Would you please be so kind as to provide us with the definitions of
sublist_i_k and is_sublist that you used.
I can write my own version of these pr4edicates, but I'd rather use yours
before I start reporting on a few "closed form" methods.

Cheers

Bart Demoen

no-spam

2004-03-28, 10:29 pm

Bart Demoen wrote:
> billh wrote:
>
>
>
> Would you please be so kind as to provide us with the definitions of
> sublist_i_k and is_sublist that you used.
> I can write my own version of these pr4edicates, but I'd rather use yours
> before I start reporting on a few "closed form" methods.
>
> Cheers
>
> Bart Demoen

Here is the version of sublist_i_k that I used yesterday:

sublist_i_k(I,K,Sublist_I_K) :-
K > 1,
K1 is K - 1,
sublists_i_k(I,K1,[I],Sublist_I_K).

% example: sublist_i_k(2,3,L) => L=[2_,_,2,_,_,2]

sublists_i_k(I,0,In,In).
sublists_i_k(I,K,In,Out) :-
K > 0,
sublist_i(I,I,In,Next),
K1 is K - 1,
sublists_i_k(I,K1,Next,Out).

sublist_i(0,I,In,[I|In]).
sublist_i(J,I,In,Out) :-
J > 0,
J1 is J - 1,
sublist_i(J1,I,[_|In],Out).

and here is the version of is_sublist that I used:

is_sublist(S,L) :-
append(A,SB,L),
append(S,B,SB).

I have since discovered that the version of sublist_i given above
throws the PDC Prolog (v3.21) flow-analyzer into an endless loop, so
today I am experimenting with the following version of sublist_i_k
(which doesn't):

sublist_i_k(I,K,Sublist_I_K) :-
K > 1,
K1 is K - 1,
sublists_i_k(I,K1,[],Sublist_I_K).

% example: sublist_i_k(2,3,L) => L=[2_,_,2,_,_,2]

sublists_i_k(I,0,In,[I|In]).
sublists_i_k(I,K,In,Out) :-
K > 0,
sublist_i(I,I,In,Next),
K1 is K - 1,
sublists_i_k(I,K1,Next,Out).

sublist_i(0,I,In,[I|In]).
sublist_i(J,I,In,[_|Out]) :-
J > 0,
J1 is J - 1,
sublist_i(J1,I,In,Out).

p.s. I hope I didn't give anyone the impression that my program printed
out all 26,880 answers to the case n=17, k=3 while I was writing my
commemt. That took a little longer. (Just kidding!)

Bill
--

zeus

2004-03-28, 10:29 pm

Bart Demoen <bmd@cs.kuleuven.ac.be> wrote in message news:<1080419042.820510@seven.kulnet.kuleuven.ac.be>...
> billh wrote:
>
>
> Would you please be so kind as to provide us with the definitions of
> sublist_i_k and is_sublist that you used.
> I can write my own version of these pr4edicates, but I'd rather use yours
> before I start reporting on a few "closed form" methods.
>
> Cheers
>
> Bart Demoen

I already posted. see #31

no-spam

2004-03-28, 10:29 pm

no-spam wrote:
>
>
> p.s. I hope I didn't give anyone the impression that my program printed
> out all 26,880 answers to the case n=17, k=3 while I was writing my
> commemt. That took a little longer. (Just kidding!)
>
>
> Bill
> --

p.p.s. I notice a rather large (order of magnitude?) improvement in
performance if I simply reverse the order of the sublist_i_k calls, as in

test_17_3R :-
make_list(51,L),
sublist_i_k(17,3,L_1_3),
is_sublist(L_17_3,L),
sublist_i_k(16,3,L_2_3),
is_sublist(L_16_3,L),
sublist_i_k(15,3,L_3_3),
is_sublist(L_15_3,L),
sublist_i_k(14,3,L_4_3),
is_sublist(L_14_3,L),
sublist_i_k(13,3,L_5_3),
is_sublist(L_13_3,L),
sublist_i_k(12,3,L_6_3),
is_sublist(L_12_3,L),
sublist_i_k(11,3,L_7_3),
is_sublist(L_11_3,L),
sublist_i_k(10,3,L_8_3),
is_sublist(L_10_3,L),
sublist_i_k(9,3,L_9_3),
is_sublist(L_9_3,L),
sublist_i_k(8,3,L_10_3),
is_sublist(L_8_3,L),
sublist_i_k(7,3,L_11_3),
is_sublist(L_7_3,L),
sublist_i_k(6,3,L_12_3),
is_sublist(L_6_3,L),
sublist_i_k(5,3,L_13_3),
is_sublist(L_5_3,L),
sublist_i_k(4,3,L_14_3),
is_sublist(L_4_3,L),
sublist_i_k(3,3,L_15_3),
is_sublist(L_3_3,L),
sublist_i_k(2,3,L_16_3),
is_sublist(L_2_3,L),
sublist_i_k(1,3,L_17_3),
is_sublist(L_1_3,L),
write(L),nl.

<B

bart demoen

2004-03-28, 10:29 pm

zeus wrote:
> Bart Demoen <bmd@cs.kuleuven.ac.be> wrote in message news:<1080419042.820510@seven.kulnet.kuleuven.ac.be>...
>
>
>
> I already posted. see #31

Unless zeus and billh is the same person, I don't know why zeus answered
my request.
Also, if you are asking for help, better make it easy for the net people
from whom you expect help, and don't just give'm obscure pointers like
#31. Thanks.

Bart Demoen

bart demoen

2004-03-28, 10:29 pm

no-spam wrote:

> p.p.s. I notice a rather large (order of magnitude?) improvement in
> performance if I simply reverse the order of the sublist_i_k calls, as in
>
> test_17_3R :-
> make_list(51,L),
> sublist_i_k(17,3,L_1_3),
> is_sublist(L_17_3,L),
> sublist_i_k(16,3,L_2_3),
> is_sublist(L_16_3,L),

That's what I expected and now also observed (with my own version
of langford/3), but the factor seems to diminish for larger
values of the arguments.

Cheers

Bart Demoen

bart demoen

2004-03-28, 10:29 pm

no-spam wrote:

> p.p.s. I notice a rather large (order of magnitude?) improvement in
> performance if I simply reverse the order of the sublist_i_k calls, as in
>
> test_17_3R :-
> make_list(51,L),
> sublist_i_k(17,3,L_1_3),
> is_sublist(L_17_3,L),
> sublist_i_k(16,3,L_2_3),
> is_sublist(L_16_3,L),
[...]

I suppose you meant:

sublist_i_k(17,3,L_17_3),
is_sublist(L_17_3,L),
sublist_i_k(16,3,L_16_3),
is_sublist(L_16_3,L),
....

???

otherwise it becomes very bad.

Also, have you tried to put all the sublist_i_k goals first and
then issue all the is_sublist goals ? It prevents the repeated
generation of the same sublist_i_k :-)

Cheers

Bart Demoen

no-spam

2004-03-28, 10:29 pm

bart demoen wrote:
> no-spam wrote:
>
>
> [...]
>
> I suppose you meant:
>
>
> sublist_i_k(17,3,L_17_3),
> is_sublist(L_17_3,L),
> sublist_i_k(16,3,L_16_3),
> is_sublist(L_16_3,L),
> ...
>
> ???
>
> otherwise it becomes very bad.
>

Oops, way past my bedtime.

I meant to say this:

test_17_3R :-
make_list(51,L),
sublist_i_k(17,3,L_17_3),
is_sublist(L_17_3,L),
sublist_i_k(16,3,L_16_3),
is_sublist(L_16_3,L),
sublist_i_k(15,3,L_15_3),
is_sublist(L_15_3,L),
sublist_i_k(14,3,L_14_3),
is_sublist(L_14_3,L),
sublist_i_k(13,3,L_13_3),
is_sublist(L_13_3,L),
sublist_i_k(12,3,L_12_3),
is_sublist(L_12_3,L),
sublist_i_k(11,3,L_11_3),
is_sublist(L_11_3,L),
sublist_i_k(10,3,L_10_3),
is_sublist(L_10_3,L),
sublist_i_k(9,3,L_9_3),
is_sublist(L_9_3,L),
sublist_i_k(8,3,L_8_3),
is_sublist(L_8_3,L),
sublist_i_k(7,3,L_7_3),
is_sublist(L_7_3,L),
sublist_i_k(6,3,L_6_3),
is_sublist(L_6_3,L),
sublist_i_k(5,3,L_5_3),
is_sublist(L_5_3,L),
sublist_i_k(4,3,L_4_3),
is_sublist(L_4_3,L),
sublist_i_k(3,3,L_3_3),
is_sublist(L_3_3,L),
sublist_i_k(2,3,L_2_3),
is_sublist(L_2_3,L),
sublist_i_k(1,3,L_1_3),
is_sublist(L_1_3,L),
write(L),nl.

> Also, have you tried to put all the sublist_i_k goals first and
> then issue all the is_sublist goals ?

You mean like this?

test_17_3R2 :-
make_list(51,L),
sublist_i_k(17,3,L_17_3),
sublist_i_k(16,3,L_16_3),
sublist_i_k(15,3,L_15_3),
sublist_i_k(14,3,L_14_3),
sublist_i_k(13,3,L_13_3),
sublist_i_k(12,3,L_12_3),
sublist_i_k(11,3,L_11_3),
sublist_i_k(10,3,L_10_3),
sublist_i_k(9,3,L_9_3),
sublist_i_k(8,3,L_8_3),
sublist_i_k(7,3,L_7_3),
sublist_i_k(6,3,L_6_3),
sublist_i_k(5,3,L_5_3),
sublist_i_k(4,3,L_4_3),
sublist_i_k(3,3,L_3_3),
sublist_i_k(2,3,L_2_3),
sublist_i_k(1,3,L_1_3),
is_sublist(L_17_3,L),
is_sublist(L_16_3,L),
is_sublist(L_15_3,L),
is_sublist(L_14_3,L),
is_sublist(L_13_3,L),
is_sublist(L_12_3,L),
is_sublist(L_11_3,L),
is_sublist(L_10_3,L),
is_sublist(L_9_3,L),
is_sublist(L_8_3,L),
is_sublist(L_7_3,L),
is_sublist(L_6_3,L),
is_sublist(L_5_3,L),
is_sublist(L_4_3,L),
is_sublist(L_3_3,L),
is_sublist(L_2_3,L),
is_sublist(L_1_3,L),
write(L),nl.

No, I hadn't but I am now. It does seem to be going somewhat faster,
but I haven't made any precise measurements, so I'm not sure. Should it?

It prevents the repeated
> generation of the same sublist_i_k :-)

Sorry, I don't understand: what same sublist_i_k is being generated?

<B

Bart Demoen

2004-03-29, 2:33 am

mijnlesno-spam wrote:

> I meant to say this:
>
> test_17_3R :-
> make_list(51,L),
> sublist_i_k(17,3,L_17_3),
> is_sublist(L_17_3,L),
> sublist_i_k(16,3,L_16_3),
> is_sublist(L_16_3,L),
> sublist_i_k(15,3,L_15_3),
> is_sublist(L_15_3,L),
> sublist_i_k(14,3,L_14_3),
> is_sublist(L_14_3,L),
> sublist_i_k(13,3,L_13_3),
> is_sublist(L_13_3,L),
> sublist_i_k(12,3,L_12_3),
> is_sublist(L_12_3,L),
> sublist_i_k(11,3,L_11_3),
> is_sublist(L_11_3,L),
> sublist_i_k(10,3,L_10_3),
> is_sublist(L_10_3,L),
> sublist_i_k(9,3,L_9_3),
> is_sublist(L_9_3,L),
> sublist_i_k(8,3,L_8_3),
> is_sublist(L_8_3,L),
> sublist_i_k(7,3,L_7_3),
> is_sublist(L_7_3,L),
> sublist_i_k(6,3,L_6_3),
> is_sublist(L_6_3,L),
> sublist_i_k(5,3,L_5_3),
> is_sublist(L_5_3,L),
> sublist_i_k(4,3,L_4_3),
> is_sublist(L_4_3,L),
> sublist_i_k(3,3,L_3_3),
> is_sublist(L_3_3,L),
> sublist_i_k(2,3,L_2_3),
> is_sublist(L_2_3,L),
> sublist_i_k(1,3,L_1_3),
> is_sublist(L_1_3,L),
> write(L),nl.
>
>
>
> You mean like this?
>
> test_17_3R2 :-
> make_list(51,L),
> sublist_i_k(17,3,L_17_3),
> sublist_i_k(16,3,L_16_3),
> sublist_i_k(15,3,L_15_3),
> sublist_i_k(14,3,L_14_3),
> sublist_i_k(13,3,L_13_3),
> sublist_i_k(12,3,L_12_3),
> sublist_i_k(11,3,L_11_3),
> sublist_i_k(10,3,L_10_3),
> sublist_i_k(9,3,L_9_3),
> sublist_i_k(8,3,L_8_3),
> sublist_i_k(7,3,L_7_3),
> sublist_i_k(6,3,L_6_3),
> sublist_i_k(5,3,L_5_3),
> sublist_i_k(4,3,L_4_3),
> sublist_i_k(3,3,L_3_3),
> sublist_i_k(2,3,L_2_3),
> sublist_i_k(1,3,L_1_3),
> is_sublist(L_17_3,L),
> is_sublist(L_16_3,L),
> is_sublist(L_15_3,L),
> is_sublist(L_14_3,L),
> is_sublist(L_13_3,L),
> is_sublist(L_12_3,L),
> is_sublist(L_11_3,L),
> is_sublist(L_10_3,L),
> is_sublist(L_9_3,L),
> is_sublist(L_8_3,L),
> is_sublist(L_7_3,L),
> is_sublist(L_6_3,L),
> is_sublist(L_5_3,L),
> is_sublist(L_4_3,L),
> is_sublist(L_3_3,L),
> is_sublist(L_2_3,L),
> is_sublist(L_1_3,L),
> write(L),nl.
>
> No, I hadn't but I am now. It does seem to be going somewhat faster,
> but I haven't made any precise measurements, so I'm not sure. Should it?
>
> It prevents the repeated
>
>
>
> Sorry, I don't understand: what same sublist_i_k is being generated?
>

The first of your two versions I am quoting, generates (e.g.) L_1_3 many times,
because of backtracking.
The second version doesn't have that problem and that's the reason is it faster.

Cheers

Bart Demoen

no-spam

2004-03-29, 6:51 pm

Bart Demoen wrote:
> mijnlesno-spam wrote:
>
>
> The first of your two versions I am quoting, generates (e.g.) L_1_3 many
> times,
> because of backtracking.

Aha. I see what you mean. I could, in fact, put a "!" after the last
sublist_i_k call in test_17_3R2 (above). Sorry, I got

about
which of the versions that I posted you were referring to. Excellent
suggestion. Thank you.

billh

Bart Demoen

2004-03-30, 2:34 am

no-spam wrote:

[...][color=darkred]
> Aha. I see what you mean. I could, in fact, put a "!" after the last
> sublist_i_k call in test_17_3R2 (above).

You could, but that wouldn't make much difference, as
sublist_i_k is (supposed to be) delivering exactly one solution.

Cheers

Bart Demoen

zeus

2004-03-30, 3:35 am

bart demoen <bmd@cs.kuleuven.ac.be> wrote in message news:<1080504586.48374@seven.kulnet.kuleuven.ac.be>...
> zeus wrote:
>
> Unless zeus and billh is the same person, I don't know why zeus answered
> my request.

Sorry Bart, didn't notice you referred to billh. sorry.

> Also, if you are asking for help, better make it easy for the net people
> from whom you expect help, and don't just give'm obscure pointers like
> #31. Thanks.
>

The posts are numbered #31 is post number 31, whats obscure about it?
Anyways thank you all guys for the interesting discussion.

> Bart Demoen

no-spam

2004-03-30, 11:44 am

Bart Demoen wrote:
> no-spam wrote:
>
>
> [...]
>
>
>
> You could, but that wouldn't make much difference

Exactly my point: it wouldn't make /any/ difference i.t.o. the
answers that were obtained.

bart demoen

2004-03-30, 4:37 pm

zeus wrote:

> The posts are numbered #31 is post number 31, whats obscure about it?

I see it as 1080504586.48374.
I suppose you would find it obscure if I referred to a post like that.

Cheers

Bart Demoen

bart demoen

2004-03-30, 4:37 pm

no-spam wrote:

>
>
> Exactly my point: it wouldn't make /any/ difference i.t.o. the answers
> that were obtained.

I must have been blind: nothing in your post gave me the impression that
was exactly your point.

Cheers

Bart Demoen

bart demoen

2004-04-02, 4:33 pm

no-spam wrote:

> p.s. I hope I didn't give anyone the impression that my program printed
> out all 26,880 answers to the case n=17, k=3 while I was writing my
> commemt. That took a little longer. (Just kidding!)

How much longer ? (not kidding !)

Cheers

Bart Demoen

Sponsored Links