生成符合特定条件的数字列表

Question

我有一个谓词来生成数字列表，

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

我正在尝试对其进行修改，使其生成的数字 X 和 Y 达到上限。条件是 1 < X < Y 和 S = X + Y 和 S < 100.

我正在努力弄清楚如何去做，我已经尝试过了，但离正确还差得很远。

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

我确实检查了 S > 100，但这完全阻止了代码的工作。

我所追求的输出与 [1,2,3], [2,4,6], [3,9,12], [20,25,45] 类似。显然这只是几个例子，现实中会有1000个。

我想我可能需要递归两次。因此，将 1 加到 X 然后继续将 1 加到 Y 直到达到限制，将 1 加到 X 并继续将 1 加到 Y 直到达到限制并继续递归执行此操作。这应该确保创建每个可能的对。

Answer 1

有几种方法可以解决这个问题。蛮力方法是让第二层基本案例迭代求和中的两个加数之一。此解决方案将首先按总和的顺序提供列表，然后按 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).

通过向上计数而不是向下计数，我可以在不使用辅助列表的情况下保持列表的正向顺序并保持尾递归。我受 X 和 Sum 约束，并让 Y 变化。我认为您可以轻松修改它以根据您希望的任何变量而变化。

更简洁的方法是使用 CLPFD 库并将条件指定为约束：

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

在这里，summation/2 一次呈现每个解决方案之一，findall/3 收集它们。此解决方案可轻松扩展以支持更多加数。

生成符合特定条件的数字列表

Generate list of numbers to fit certain criteria

prolog