Re: Sublists question

From: zeus (zohar_at_sheernetworks.com)
Date: 03/21/04 

Date: 21 Mar 2004 02:32:53 -0800

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

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

Relevant Pages

  • Re: Sublists question
    ... >>to square one, being more understood, how do I generate this List? ... > Then write a predicate which, given P and Q, yields a list of a Q ... Anyways, this is what I understood from you suggestion Nick, what do ...
    (comp.lang.prolog)
  • Re: Sublists question
    ... In message, zeus ... >to square one, being more understood, how do I generate this List? ... 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 ...
    (comp.lang.prolog)
  • Re: Partial recursive functions and minimization
    ... still unclear how can there be something like Normal Form Theorem for ... Our professor told us we can look at the predicate Tin a way ... predicate is true if the program 'e' for input 'x' yields the value ...
    (sci.math)