CODEWITHSUNDEEP
listprologpermutation
Big Bear
Big Bear

Reputation: 21

Create lists of permutations of size N from elements of another list

How do I, given a List = [(1,1),(1,2),(1,3),(1,4)], N = 2, create a list containing the multiple ordered permutations of List, size N:

permutations([(1,1),(1,2),(1,3),(1,4)],2,ListOut). ListOut=[[(1,1),(1,2)],[(1,1),(1,3)],[(1,1),(1,4)],[(1,2),(1,3)],[(1,2),(1,4)],[(1,3),(1,4)]]

??

Upvotes: 0

Views: 408

Answers (1)

fferri
fferri

Reputation: 18950

First let's solve the problem of finding one permutation:

perm(_, 0, []).
perm([X|Xs], N, [X|Ys]) :- N1 is N-1, perm(Xs,N1,Ys).
perm([_|Xs], N, Y) :- N>0, perm(Xs,N,Y).

There are two recursive rules: 1) X can be the first element of the output, and find the remaining permutation of N-1 for the rest of the list; 2) skip the first element, and find the permutation over the remaining elements of the input list.

Finding all permutations is just about using findall/3:

permutations(X, N, Y) :- findall(Z, perm(X, N, Z), Y).

Test:

?- permutations([(1,1),(1,2),(1,3),(1,4)], 2, X).

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

Upvotes: 3

Related Questions