CODEWITHSUNDEEP
prolog
JaAnTr
JaAnTr

Reputation: 906

Generate list of numbers to fit certain criteria

I had a predicate to generate a list of numbers,

generate_numbers(0,[]).
generate_numbers(N,[Head|Tail]):-
                    N > 0,                      
                    Head is N,                  
                    N1 is N-1,                  
                    generate_numbers(N1,Tail).

I am trying to modify it so that it generates numbers X and Y up to a limit. The conditions are that 1 < X < Y and S = X + Y and S < 100.

I'm struggling to work out how to do it, I've tried but it's nowhere near correct.

generate_numbers(1,[]).
generate_numbers(X,[[Head,Y,S]|Tail]):-
                    X > 1,                      
                    Head is X,
                    Y is X+1,
                    S is X + Y,
                    X1 is X-1,                  
                    generate_numbers(X1,Tail).

I did have a check for S > 100 but that stopped the code from working at all.

The output I'm after would be along the lines of [1,2,3], [2,4,6], [3,9,12], [20,25,45]. Obviously that's just a few examples, there will be 1000s in reality.

I think that I might need to recurse twice. So add 1 to X then keep adding 1 to Y until the limit is reached, add 1 to X and keep adding 1 to Y again until the limit is reached and keep doing this recursively. This should make sure that every possible pair is created.

Upvotes: 0

Views: 387

Answers (1)

lurker
lurker

Reputation: 58244

There are a couple of ways to approach this. The brute force way is to have a second layer of base case to iterate over one of the two addends in the summation. This solution will provide the list first in order of total sum, then by value of X:

gen_numbers(MaxSum, Result) :-
    MaxSum > 1,
    gen_numbers(2, MaxSum, 1, Result).

gen_numbers(Sum, Sum, Sum, []).            % 'Sum' has reached max value
gen_numbers(Sum, MaxSum, Sum, Result) :-   % 'X' has reached max value
    Sum < MaxSum,
    Sum1 is Sum + 1,
    gen_numbers(Sum1, MaxSum, 1, Result).
gen_numbers(Sum, MaxSum, X, [[X, Y, Sum]|Result]) :-
    Sum =< MaxSum,
    X < Sum,
    Y is Sum - X,
    X1 is X + 1,
    gen_numbers(Sum, MaxSum, X1, Result).

By counting up instead of down, I could keep the list in forward order and maintain tail recursion without the use of an auxiliary list. I constrained by X and the Sum and let Y vary. I think you could easily modify this to vary based upon whatever variables you wish.

A cleaner approach is to use the CLPFD library and specify the conditions as constraints:

:- use_module(library(clpfd)).

summation(Sum, [X, Y, S]) :-
    [X, Y] ins 1..Sum,
    sum([X, Y], #=<, Sum),
    label([X, Y]),
    S is X + Y.

gen_numbers(MaxSum, Result) :-
    findall([X, Y, S], summation(MaxSum, [X, Y, S]), Result).

Here, summation/2 presents one of each solution at a time, and findall/3 collects them. This solution is easily scalable to support more addends.

Upvotes: 1

Related Questions