Generating all permutations, combinations, and power set of a string (2012)

Very nice, thank you for sharing!

For comparison, here are Prolog solutions for these tasks.

The first building block is a relation between a list, one of its elements, and the list of remaining elements:

    list_element_rest([E|Ls], E, Ls).
    list_element_rest([L|Ls0], E, [L|Ls]) :-
            list_element_rest(Ls0, E, Ls).

In the following, I assume you have set double_quotes to chars, so that you can easily work on a string as a list of characters:

    :- set_prolog_flag(double_quotes, chars).

Here is a sample interaction, using this relation:

    ?- list_element_rest("abc", E, Ls).
    E = a,
    Ls = [b, c] ;
    E = b,
    Ls = [a, c] ;
    E = c,
    Ls = [a, b] ;
    false.

Importantly, we can use it in all directions, for example also to insert an element into a list:

    ?- list_element_rest(Ls, a, "bc").
    Ls = [a, b, c] ;
    Ls = [b, a, c] ;
    Ls = [b, c, a] ;
    false.

Using list_element_rest/3 as a building block, we can define the relation between a list and one of its permutations as follows:

    list_permutation([], []).
    list_permutation([L|Ls], Ps) :-
            list_permutation(Ls, Ps0),
            list_element_rest(Ps, L, Ps0).

This completes the first task. Example:

    ?- list_permutation("abc", Ps).
    Ps = [a, b, c] ;
    Ps = [b, a, c] ;
    Ps = [b, c, a] ;
    Ps = [a, c, b] ;
    Ps = [c, a, b] ;
    Ps = [c, b, a] ;
    false.

In many Prolog implementations, this predicate is already implemented as permutation/2, but the point here is to show that you can also implement it easily yourself, at least in the input->output direction, where the first argument is fully instantiated.

To solve both the second and third task, let us relate a list to one of its subsequences:

    subseq([]) --> [].
    subseq([L|Ls]) --> ([] | [L]), subseq(Ls).

With this definition, you can for example get all 2-element combinations of "abcd" as follows:

    ?- length(Ls, 2), phrase(subseq("abcd"), Ls).
    Ls = [c, d] ;
    Ls = [b, d] ;
    Ls = [b, c] ;
    Ls = [a, d] ;
    Ls = [a, c] ;
    Ls = [a, b] ;
    false.

The powerset is a natural generalization of this query, where you simply omit the first goal:

    ?- phrase(subseq("abcd"), Ls).
    Ls = [] ;
    Ls = [d] ;
    Ls = [c] ;
    Ls = [c, d] ;
    Ls = [b] ;
    Ls = [b, d] ;
    Ls = [b, c] ;
    Ls = [b, c, d] ;
    Ls = [a] ;
    Ls = [a, d] ;
    Ls = [a, c] ;
    Ls = [a, c, d] ;
    Ls = [a, b] ;
    Ls = [a, b, d] ;
    Ls = [a, b, c] ;
    Ls = [a, b, c, d].

If anyone wants to know how deep down the rabbit hole this stuff goes, they should read this blog post [1] on writing a Levenshtein Automaton to speed up fuzzy matching in Lucene by 100 times. It gets deep!

[1]: http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is...