1

I currently have this piece of code in Prolog

s1(Q,100) :- generate(Q).

generate([X,Y,S,P]) :-
  nat(X, 49),
  nat(Y, 98),
  S is X+Y,
  P is X*Y,
  S =< 100,
  X < Y.

nat(2,_).
nat(X,N) :-
  N > 2,
  M is N - 1,
  nat(Y,M),
  X is Y + 1.

It currently generates a list of quadruples, X, Y, S, P such that

  • 1 < X < 49
  • 1 < Y < 98
  • 1 < X < Y
  • X + Y <= 100
  • P = X * Y
  • S = X + Y

This works and creates all possible solutions but with multiple answers (i.e, having to press ; every time to get the next result.)

How can a single list be formed of all these results, for instance,

[[2, 3, 5, 6], [2, 4, 6, 8], ...]

without using any built in predicates such as findall/3?

Nicholas Carey
  • 71,308
  • 16
  • 93
  • 135
  • 1
    Are you allowed to use `member` or `memberchk`? Those are built in predicates well. There seems to be an epidemic phobia of common ISO Prolog predicates in SO Prolog questions for some odd reason. ;) – lurker Mar 16 '15 at 15:20
  • @lurker Yeah, not allowed to use them, anything built in. In sense have to code from scratch in pure Prolog. –  Mar 16 '15 at 15:22
  • As a hint to one approach: write yourself a simple `memberchk/2` predicate (you can look that one up), then write a simple recursive `genall/1` that starts with an empty list and fills it recursively, but avoids elements that were already added (that's where `memberchk/2` comes in). – lurker Mar 16 '15 at 16:07

2 Answers2

2

First, the upper interval bounds you gave for X and Y are both off by one:

  • 1 < X < 49 does not match nat(X,49), 1 < X =< 49 does.
  • 1 < Y < 98 does not match nat(Y,98), 1 < Y =< 98 does.

Let's get it started!

If you want to collect all solutions without using findall/3 (etc), one way is to calculate the Cartesian product (a.k.a. cross-product) of two lists Xs and Ys.

To get Xs and Ys, we can use the builtin predicate numlist/3:

?- numlist(2,49,Xs).
Xs = [2,3,4,/* consecutive integers from 5 to 47 omitted */,48,49].

?- numlist(2,98,Ys).
Ys = [2,3,4,/* consecutive integers from 5 to 96 omitted */,97,98].

To combine every X in Xs with every Y in Ys we use xproduct//3.

For selecting which quadruples to collect, use the grammar rule x_y_maybe_quadruple//2:

x_y_maybe_quadruple(X,Y) -->
   (  { 1 < X, X < Y, X+Y =< 100 }       % if all these conditions are met
   -> { P is X * Y },
      { S is X + Y },
      [[X,Y,S,P]]                        % then add single "quadruple"
   ;  []                                 % else add nothing.
   ).

Let's put it all together!

?- numlist(2,49,Xs),
   numlist(2,98,Ys),
   phrase(xproduct(x_y_maybe_quadruple,Xs,Ys),Qss).
Qss = [[2,3,5,6],[2,4,6,8],
       /* lots of other quadruples omitted */,
       [48,51,99,2448],[48,52,100,2496]].

So... do we actually get all quadruples we would have gotten if we had used findall/3?

?- findall(Qs,generate(Qs),Qss1),
   numlist(2,49,Xs),
   numlist(2,98,Ys),
   phrase(xproduct(x_y_maybe_quadruple,Xs,Ys),Qss2),
   Qss1 = Qss2.
Qss1 = Qss2, 
Qss2 = [[2, 3, 5, 6], [2, 4, 6, 8], [2|...], [...|...]|...],
Xs   = [2, 3, 4, 5, 6, 7, 8, 9, 10|...],
Ys   = [2, 3, 4, 5, 6, 7, 8, 9, 10|...].

It works! And not just that: we get exactly the same quadruples in the exact same order!

false
  • 10,264
  • 13
  • 101
  • 209
repeat
  • 18,496
  • 4
  • 54
  • 166
0

You need to add a solution to a list if it is not already in the list..if its in the list fail.

so 

myfindall(List) :-
   my_find(List,[]),
   !.

my_find(List,Ac) :-
   s1(Q,100), 
   my_set(Q,Ac,NewAc),
   my_find(List,NewAc).
my_find(Ac,Ac).

my_set(X,[],[X]) :-
   !.
my_set(H,[H|_],_) :-
   !,
   fail.
my_set(X,[H|T],L) :- 
   my_set(X,T,Rtn),
   L = [H|Rtn].
repeat
  • 18,496
  • 4
  • 54
  • 166
user27815
  • 4,767
  • 14
  • 28