CODEWITHSUNDEEP
listprologpermutation
viktor
viktor

Reputation: 21

Prolog permutation extracting solutions

permutation([], []).
permutation(L, [X|Xs]) :- select(X, L, Rest), permutation(Rest, Xs).

If I type permutation([1,2,3],R), the first solution is "[1,2,3]" but how to get to the second one without using ";" or "fail". I need to use the 2nd solution like "[1,3,2]" or so in order compare it to another list.

What I mean is: 

permutation([], []).
permutation(L, [X|Xs]) :- select(X, L, Rest), permutation(Rest, Xs).

go_perm(L,P) :-     
        L = P,
        write(P),nl.

go_perm(L,P) :- 
        permutation(P,P2), % in this case i wanna get the next solution -.- 
        go_perm(L,P2).

If L = P then it finishes. Permutation of the first solution for "[1,2,3]" is "[1,2,3]". But that pulls me into stackoverflow because it runs into never-endless thing. Perhaps you understand me. Thanks!

Upvotes: 2

Views: 5182

Answers (3)

DaveEdelstein
DaveEdelstein

Reputation: 1256

You need to look at various aggregate predicates. Here, findall would work nicely. you can invoke it:

ListIn=[1,2,3], findall(Perm, permutation(ListIn, Perm), Permutations).

This will call permutation on ListIn until it fails. Each Perm returned by permutation will be collected into the Permutations variable.

Upvotes: 1

Jerome
Jerome

Reputation: 2370

Assuming you want to loop over the solutions to print them

One standard way to accomplish this is to fail and backtrack, as in:

print_all_permutations(X)
  :- permutation(X, Y), print(Y), nl, fail ; true.

Assuming you just want to check if a given solution is correct

You are already done. Just call the function with the reference list and the list you want to test:

permutation([1, 2, 3], [2, 1, 3]).

will return true, because [2, 1, 3] is a permutation of [1, 2, 3]. If the second argument is not a permutation, the goal will evaluate to false.

This is the magic of prolog: finding a solution, or checking if a given solution is correct, are the same thing.

In between: partial solution

The same reasoning still applies:

permutation([1, 2, 3], [2, X, 3]).

will display the only possible value for X.

Or, if you want the whole list to be the result:

X = [2, X, 3], permutation([1, 2, 3], X).

Upvotes: 1

Neil
Neil

Reputation: 55402

permutation is a predicate that succeeds when one list is a permutation of the other. You don't actually need to enumerate them; just write permutation([1, 2, 3], [2, 1, 3]) and Prolog will tell you "true".

Upvotes: 0

Related Questions