Did you know ... Search Documentation:
Predicate permutation/2
Availability::- use_module(library(lists)).(can be autoloaded)
Source[nondet]permutation(?Xs, ?Ys)
True when Xs is a permutation of Ys. This can solve for Ys given Xs or Xs given Ys, or even enumerate Xs and Ys together. The predicate permutation/2 is primarily intended to generate permutations. Note that a list of length N has N! permutations, and unbounded permutation generation becomes prohibitively expensive, even for rather short lists (10! = 3,628,800).

If both Xs and Ys are provided and both lists have equal length the order is |Xs|^2. Simply testing whether Xs is a permutation of Ys can be achieved in order log(|Xs|) using msort/2 as illustrated below with the semidet predicate is_permutation/2: 

is_permutation(Xs, Ys) :-
  msort(Xs, Sorted),
  msort(Ys, Sorted).

The example below illustrates that Xs and Ys being proper lists is not a sufficient condition to use the above replacement. 

?- permutation([1,2], [X,Y]).
X = 1, Y = 2 ;
X = 2, Y = 1 ;
false.
Errors
type_error(list, Arg) if either argument is not a proper or partial list.
Tags are associated to your profile if you are logged in
Tags:
Carlo Capelli said (2013-06-10T08:28:22):1 upvotes 1 0 downvotes
Picture of user Carlo Capelli.

on stackoverflow, an interesting question pointed out that a non tail recursive definition attains a threefold gain on execution time: then, if you are not interested in lexicographic order that permutation/2 offers (and first argument is bound), you could use this definition

permute([], []).
permute([X|Rest], L) :-
    permute(Rest, L1),
    select(X, L, L1).

based on my - minimal - test, YAP execution offers still more gain.