Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 40 ยท Lists and Recursion

Prolog List Patterns: Permutations, Subsets, Sorting and Puzzles

Write classic Prolog list programs: permutation with select, subsequences and the power set, insertion sort, duplicate removal, zip and a seating puzzle solved by generate and test.

This lesson collects the list patterns that come up again and again: generating all arrangements, choosing subsets, sorting by hand, de-duplicating, and combining two lists. Each is only a few lines, and each is a good exercise in writing predicates that work in more than one direction. At the end you will solve a small puzzle with the generate-and-test method.

Prolog is read-only on this site. Every program below runs unchanged in SWI-Prolog; the runnable blocks execute the same text in the Python mini-Prolog stand-in.

Permutations with select/3

A permutation of a list is the same elements in some other order. The definition is short if you use select/3 from earlier:

PROLOG
perm([], []).
perm(List, [H | T]) :-
    select(H, List, Rest),
    perm(Rest, T).

Read it: a permutation of List starts with some element H of List, followed by a permutation of the remaining elements. select(H, List, Rest) picks each element in turn (backtracking), and the recursion permutes what is left.

PROLOG
?- perm([a, b, c], P).
P = [a, b, c] ;
P = [a, c, b] ;
P = [b, a, c] ;
P = [b, c, a] ;
P = [c, a, b] ;
P = [c, b, a].

A list of n elements has n! permutations: 6 for three, 24 for four, 3,628,800 for ten. SWI-Prolog's library has permutation/2 with the same behavior.

Subsequences and the power set

A subsequence keeps some elements in their original order. For each element there are two choices: keep it or skip it.

PROLOG
subseq([], []).
subseq([H | T], [H | R]) :- subseq(T, R).    % keep H
subseq([_ | T], R)       :- subseq(T, R).    % skip H
PROLOG
?- subseq([a, b, c], S).
S = [a, b, c] ;
S = [a, b] ;
S = [a, c] ;
S = [a] ;
S = [b, c] ;
S = [b] ;
S = [c] ;
S = [].

All 2^n subsets appear. Collect them with findall(S, subseq(List, S), PowerSet) to get the power set. Choosing K items (combinations) is the same program with a size check, or written directly:

PROLOG
combination(0, _, []).
combination(K, [H | T], [H | R]) :- K > 0, K1 is K - 1, combination(K1, T, R).
combination(K, [_ | T], R) :- K > 0, combination(K, T, R).

combination(2, [a, b, c], C) gives [a, b], [a, c], [b, c].

Insertion sort

Sorting by hand shows recursion plus a helper:

PROLOG
isort([], []).
isort([H | T], Sorted) :-
    isort(T, SortedTail),
    insert(H, SortedTail, Sorted).

insert(X, [], [X]).
insert(X, [Y | T], [X, Y | T]) :- X =< Y.
insert(X, [Y | T], [Y | R]) :- X > Y, insert(X, T, R).

Sort the tail, then insert the head in its proper place. The two guards make the clauses mutually exclusive. It takes O(nยฒ) time; for real work use msort/2 or sort/2. Since insert/3 is a relation you can also run it backwards (with the output given) to remove an element from a sorted list. Variants such as quicksort use partition and append:

PROLOG
quicksort([], []).
quicksort([P | Xs], Sorted) :-
    partition_by(P, Xs, Small, Big),
    quicksort(Small, SS),
    quicksort(Big, SB),
    append(SS, [P | SB], Sorted).

partition_by(_, [], [], []).
partition_by(P, [X | Xs], [X | S], B) :- X =< P, partition_by(P, Xs, S, B).
partition_by(P, [X | Xs], S, [X | B]) :- X > P, partition_by(P, Xs, S, B).

Removing duplicates

PROLOG
dedup([], []).
dedup([H | T], R)       :- member(H, T), dedup(T, R).         % drop H: it appears later
dedup([H | T], [H | R]) :- \+ member(H, T), dedup(T, R).      % keep the last occurrence

dedup([a, b, a, c, b], R) gives R = [a, c, b]: each element's last occurrence stays. The library's list_to_set/2 keeps the first occurrences instead. The negation \+ member(H, T) is safe here because H and T are bound, as the negation lesson requires.

Combining two lists

PROLOG
zip([], [], []).
zip([A | As], [B | Bs], [A-B | Rest]) :- zip(As, Bs, Rest).

rotate([H | T], R) :- append(T, [H], R).
PROLOG
?- zip([a, b, c], [1, 2, 3], Pairs).
Pairs = [a-1, b-2, c-3].

?- zip(Xs, Ys, [a-1, b-2]).          % unzip, with the same predicate
Xs = [a, b],
Ys = [1, 2].

?- rotate([1, 2, 3, 4], R).
R = [2, 3, 4, 1].

The same zip/3 zips and unzips; this reversibility is typical of relational programs. (The library names are pairs_keys_values/3 and maplist/4.)

A puzzle by generate and test

Four friends sit in a row: Ann, Bob, Cy and Dee. Ann and Bob must not sit next to each other. Generate every arrangement with perm/2, then reject those that violate the rule:

PROLOG
adjacent(X, Y, L) :- append(_, [X, Y | _], L).

seating(Row) :-
    perm([ann, bob, cy, dee], Row),
    \+ adjacent(ann, bob, Row),
    \+ adjacent(bob, ann, Row).

There are 24 permutations; in 12 of them Ann and Bob touch (3 adjacent seat pairs ร— 2 orders ร— 2 ways to seat the other two), so 12 valid seatings remain. This is the standard shape of constraint puzzles: pick a candidate, then check rules. When the search space is big, generate with constraints applied as early as possible, or use constraint logic programming instead.

Put every test after the generator has bound its variables, but as early as possible: checking a partial row is far cheaper than checking complete permutations.

Try it

Python Permutations, subsets and sorting (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Try it: the seating puzzle

Python Generate and test: seating (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Count the answers: there are twelve of them, in the order in which perm/2 generates them.

Exercises

  1. Write delete_all(X, List, Rest) that removes every occurrence of X. Think about what happens when an element is not equal to X and when it is.
  2. Write sum_pairs(List, Target, X-Y) that finds two different members adding to Target (use select/3 twice).
  3. Define flatten_list/2, which turns [1, [2, [3]], 4] into [1, 2, 3, 4]. You will need is_list/1 to tell lists from other terms.
  4. Use perm/2 to find all anagrams of [c, a, t], and atom_chars/2 to turn them into atoms.
  5. Write ordered/1 that succeeds if a list is sorted ascending, using patterns [X, Y | T].

After these, you are ready for chapter 5 on arithmetic and program control.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many answers does perm([a, b, c, d], P) have?

    n! = 4! = 24 permutations.
  2. 2. In perm(List, [H|T]) :- select(H, List, Rest), perm(Rest, T)., what does select/3 do?

    Backtracking over select/3 tries every element as the first one of the permutation.
  3. 3. How many solutions does subseq([a, b, c], S) have?

    Each of three elements is kept or skipped: 2^3 = 8.
  4. 4. Why are the guards X =< Y and X > Y used in insert/3?

    Exactly one of the guards holds, so there is a single correct place to insert.
  5. 5. What is the generate-and-test pattern?

    A generator such as perm/2 or member/2 supplies candidates; later goals check the constraints.

Summary

  • perm/2 uses select/3: pick an element, permute the rest. n elements give n! answers.
  • subseq/2 keeps or skips each element: 2^n subsets; findall/3 makes the power set.
  • Insertion sort and quicksort are short recursive definitions with exclusive guards.
  • Many list predicates (zip/3, insert/3, select/3) run in several directions.
  • Puzzles are solved by generating candidates and testing constraints as early as possible.

Next: Arithmetic and the is Operator