在Prolog中找到N个独特的目标解决方案

Question

你能告诉我如何在Prolog中找到N个独特的目标解决方案吗？

我知道使用findall/3可以找到目标的所有解决方案,但是对于有太多或无限解决方案的目标,如果足够的话我想要找到最多N个唯一解决方案.

我想做的是这样的:

?- find_unique_n(10, X, any_goal(X), Xs).
Xs = [...] % up to 10 unique solutions.

如果目标的唯一解决方案的总数低于N,我想找到所有这些.

编辑:正如虚假指出的那样,尚不清楚"独特解决方案"的含义.如果sample_goal/1定义如下:

sample_goal(1).
sample_goal(1).
sample_goal(2).
sample_goal(2).

预期的结果是:

?- find_unique_n(1, X, sample_goal(X), Xs).
Xs = [1]
?- find_unique_n(2, X, sample_goal(X), Xs).
Xs = [1,2]
?- find_unique_n(3, X, sample_goal(X), Xs).
Xs = [1,2]

对于具有无限解决方案的目标,预期结果是:

?- find_unique_n(2, X, (repeat, between(1,2,X)), Xs).
Xs = [1,2]
?- find_unique_n(3, X, (repeat, between(1,2,X)), Xs).
% This won't stop, it's ok

Answer 1

这是一个解决方案，尽管不是特别有效。这个想法是重复调用Goal（的副本），寻找尚未在Sols列表中的解决方案：

find_unique_n(N, X, Goal, Xs) :-
    find_unique_n(N, X, Goal, Xs, []).

find_unique_n(N, X, Goal, Xs, Sols) :-
    N > 0,
    copy_term(X-Goal, CX-CGoal),
    call(CGoal),
    \+ (member(Sol,Sols), variant(Sol,CX)),
    !,
    N1 is N-1,
    Xs = [CX|Xs1],
    Sols1 = [CX|Sols],
    find_unique_n(N1, X, Goal, Xs1, Sols1).
find_unique_n(_N, _X, _Goal, [], _Sols).

如果你的解决方案都是地面的，你可以使用==/2代替variant/2。

或者，如果您的 Prolog 有方便的原语来保存回溯数据，您可以使用故障驱动方法，如以下ECLiPSe示例所示：

find_unique_n(N, X, Goal, Xs) :-
    store_create(Solutions),
    (
        once((
            call(Goal),
            store_set(Solutions, X, _),
            store_count(Solutions) >= N
        )),
        fail
    ;
        stored_keys(Solutions, Xs)
    ).

其中存储原语实现了不可回溯的哈希表。使用断言/收回的类似解决方案是可能的，但对于实现可重入和无内存泄漏来说并不简单。