prolog - Prolog 中的不同素数分区

Question

我需要枚举将给定数字 n 划分为一个或多个不同素数之和的所有方法，Prolog 中的 a + b + ... + m

例如:

给定一个整数 n，程序应将适当的总和写入标准输出。例如，如果 n = 20，程序可能会打印

2 + 5 + 13
2 + 7 + 11
3 + 17
7 + 13

n可以是任意数字，并且运行时间没有限制。

这是我所拥有的:

partition(N, _, []) :- N = 0.
partition(N, [], _) :- fail.

partition(N, [IH|IT], [OH|OT]) :-
    N =< 0, fail;
    N >= IH, M is N-IH, OH = IH,
    partition(M, [IH|IT], OT).

partition(N, [_|IT], Output) :-
    N =< 0, fail;
    partition(N, IT, Output).

partition(N, Output) :-
    generatePrime(N,L),
    partition(N, L, Output).

generatePrime(1, []) :- !.
generatePrime(N, X) :-
    not(isPrime(N)), !,
    Z is N-1,
    generatePrime(Z,X).
generatePrime(N, [N | X]) :-
    Z is N-1,
    generatePrime(Z,X).

isPrime(2).
isPrime(P) :-
    P > 2,
    isDivisible(P, P-1). 

isDivisible(P,X) :-
    X > 1,
    P mod X =\= 0,
    isDivisible(P, X-1).
isDivisible(_, X) :-
    1 is X.

目前，我尝试运行这样的东西:

[?- 分区(5, X)。

我得到了重复的[5]和[3,2]提示。当我使用更大的数字(例如 n = 20)时，还有另一种类型的问题，因为我收到重复素数的提示，例如 [2,2,2,2,2,2,2,2,2,2]。

我对序言非常陌生，我确信甚至可能有一种更简单的方法来解决这个问题，但我不确定我在代码中遇到了什么问题。

Answer 1

你还没有...

更大的问题是你调用partition/3的方式

partition(5, generatePrime(5,Y), X)

partition/3 需要第二项的列表，而不是 generatePrime(5, Y)。

我建议您添加一个partition/2，如下所示

partition(N, Output) :-
    generatePrime(N, L),
    partition(N, L, Output).

并调用此版本的分区

partition(5, X)

还有其他问题，因为此调用返回相同响应的时间更多(在 X 中返回，[5] 四次，[3,2 ] 两次)。

我会看一下是否发现问题

--- 编辑 ---

抱歉，我在理解带有剪切 (!)、fail 和 or (;) 的 Prolog 代码时遇到了很大的问题。

我想这是我的问题。

我已按以下方式修改了您的 partition/3

partition(0, _, []).

partition(N, [H | It], [H | Ot]) :-
   N >= H,
   M is N-H,
   partition(M, [H | It], Ot).

partition(N, [_ | It], O) :-
   N > 0, 
   partition(N, It, O).

这应该避免列表重复

如果您想避免同一列表中出现重复的素数(如果您不接受 [3, 3, 2] 或 [2, 2, 2, 2] 对于 8，因为素数重复)，您应该避免在以下对 partition/3 的调用中重复使用 H(原始代码中的 IH) >.

我的意思是下面的子句

partition(N, [H | It], [H | Ot]) :-
   N >= H,
   M is N-H,
   partition(M, [H | It], Ot).

应该变成

partition(N, [H | It], [H | Ot]) :-
   N >= H,
   M is N-H,
   partition(M, It, Ot).