2 ms·
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
by zmonx 9y ago
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].