StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I know the original question was posted quite some time ago, but I was very recently working through some of the problems in <em>The Art Of Prolog</em> as well and thought over the even/odd permutation problem for a few days. I didn't want to open a duplicate problem, so I'm posting my solution here.</p> <p>The problem in the book asks:</p> <blockquote> <p>Write programs for <code>even_permutation(Xs, Ys)</code> and <code>odd_permutation(Xs, Ys)</code> <strong>that find <code>Ys</code></strong>, the even and odd permutations, respectively, of a list <code>Xs</code>. For example, <code>even_permutation([1,2,3], [2,3,1])</code> and <code>odd_permutation([1,2,3], [2,1,3])</code> are true.</p> </blockquote> <p>So it's asking for permutation generators, not just verifiers. @hardmath has provided a link to the correct definition of even or odd permutation. The authors of the book gave two simple examples to illustrate.</p> <p>For me, the key was figuring out a recursive definition for an even or odd permutation. For all permutations, the classical permutation generator in Prolog uses the following notion:</p> <ul> <li>Every permutation of N+1 elements is a list representing a permutation of N of the elements with the (N+1)st element inserted into the list.</li> </ul> <p>The predicate <code>select</code> or <code>insert</code> is used to do the insertion.</p> <p>For even and odd permutations, I considered a similar idea:</p> <ul> <li><p>Every <em>even</em> permutation of N+1 elements is either a list representing an <em>even</em> permutation of N of the elements with the (N+1)st element inserted at an <em>odd</em> position in the list, or a list representing an <em>odd</em> permutation of N of the elements with the (N+1)st element inserted at an <em>even</em> position in the list.</p></li> <li><p>Every <em>odd</em> permutation of N+1 elements is either a list representing an <em>odd</em> permutation of N of the elements with the (N+1)st element inserted at an <em>odd</em> position in the list, or a list representing an <em>even</em> permutation of N of the elements with the (N+1)st element inserted at an <em>even</em> position in the list.</p></li> </ul> <p>The rational is that the insertion of an element at an odd position represents an even number of swaps relative to the original list (the front of the list, being the first position, requires no swaps, so it's even). Similarly, the insertion of an element at an even position represents an odd number of swaps relative to the original list.</p> <p>If I add to this the rule that the empty list is it's own even permutation, then I can define the following predicates as follows to generate the even and odd permutations:</p> <pre><code>even_permutation( [], [] ). even_permutation( [X|T], Perm ) :- even_permutation( T, Perm1 ), insert_odd( X, Perm1, Perm ). even_permutation( [X|T], Perm ) :- odd_permutation( T, Perm1 ), insert_even( X, Perm1, Perm ). odd_permutation( [X|T], Perm ) :- odd_permutation( T, Perm1 ), insert_odd( X, Perm1, Perm ). odd_permutation( [X|T], Perm ) :- even_permutation( T, Perm1 ), insert_even( X, Perm1, Perm ). insert_odd( X, InList, [X|InList] ). insert_odd( X, [Y,Z|InList], [Y,Z|OutList] ) :- insert_odd( X, InList, OutList ). insert_even( X, [Y|InList], [Y,X|InList] ). insert_even( X, [Y,Z|InList], [Y,Z|OutList] ) :- insert_even( X, InList, OutList ). </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload