CODEWITHSUNDEEP
prolog
user3344370
user3344370

Reputation:

Form a single list from multiple answers in Prolog

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

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?

Upvotes: 1

Views: 642

Answers (2)

repeat
repeat

Reputation: 18726

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!

Upvotes: 2

user27815
user27815

Reputation: 4797

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

Upvotes: 0

Related Questions