Finding up to N unique solutions of a goal in Prolog
prolog
Solution
Here is a solution, although not particularly efficient. The idea is to repeatedly call (copies of) Goal, looking for solutions that are not yet in the Sols list:
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).
If your solutions are all ground, you can use ==/2 in place of variant/2.
Alternatively, if your Prolog has convenient primitives to save data across backtracking, you can use a failure-driven approach like in the following ECLiPSe example:
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)
).
where the store-primitives implement a non-backtrackable hash table. Similar solutions using assert/retract are possible, but nontrival to make reentrant and memory leak free.
Problem
Could you tell me how to find up to N unique solutions of a goal in Prolog? I know using findall/3 all the solutions of a goal can be found, but for a goal which has too many, or infinite solutions, I want to find only up to N unique solutions if it is enough. What I want to do is like this: ``` ?- find_unique_n(10, X, any_goal(X), Xs). Xs = [...] % up to 10 unique solutions. ``` If the total number of the unique solutions for a goal is below N, I want to find all of them. Edit: As false pointed out, itt was not clear what 'unique solutions' means. If sample_goal/1 is defined as below: ``` sample_goal(1). sample_goal(1). sample_goal(2). sample_goal(2). ``` the expected results are: ``` ?- 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] ``` And for goals with infinite solutions, the expected results are: ``` ?- 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 ```