name = 'permute/2'
slug = 'generate permutations of a list'

description = '''\
<p><code>permute(L1, L2)</code>: the list <code>L2</code> is a permutation of the elements of the list <code>L1</code>.</p>
<pre>
?- permute([1,2,3], L).
  L = [1,2,3] ;
  L = [1,3,2] ;
  L = [2,1,3] ;
  L = [2,3,1] ;
  L = [3,1,2] ;
  L = [3,2,1].
</pre>'''

plan = ['''\
<p><img src="[%@resource plan.svg%]" /></p>
<p>Try recursively constructing one possibility, but leave prolog its freedom. It will then return
all the possibilities by itself.</p>
''', '''\
<p>There are several options, one goes like this: if I take away the head, this reduces the problem and I can
leave it to recursion, and at the end I put the head back. Where do I put the head? I insert it in
<em>all</em> possible places, one solution at a time.</p>
''', '''\
<p>If I assume the recursion permutes the tail <code>T</code> into the "permutated tail"
<code>PT</code> and then I insert head <code>H</code> somewhere into <code>PT</code>, then I will get
some permutation of the initial list <code>[H|T]</code>.</p>
''']

hint = {
    'eq_instead_of_equ': '''\
<p>The operator <code>==</code> is "stricter" than operator <code>=</code> in the sense that
for the latter it is enough to be able to make the two operands equal (unification).</p>
<p>Of course, you can also solve the exercise without explicit use of either of these two operators, just
remember that unification is implicitly performed with the predicate's arguments (head of clause).</p>
''',

    'eq_instead_of_equ_markup': '''\
<p>Perhaps the operator for unification (=) would be better?</p>
''',

    'base_case': '''\
<p>Did you think of a base case? What's the most elementary case? What if the list is empty?</p>
''',

    'base_case_arbitrary': '''\
<p>How can the result of permutating a list be an arbitrary list or an unassigned variable?</p>
<p>If your base case is reminiscent of <code>permute([], _)</code>, rethink it!
What should be the result of permutating a list?
The base case <em>always</em> fully specifies the result, usually there are no unknowns (<code>_</code>
or variables without assigned values) in what is being returned as the result.</p>
''',

    'unsuccessful_conc_use': '''\
<p>Are you using <code>conc/3</code>? It's probably not so useful to solve this exercise,
but the solution to some other previous exercise might be what is required.</p>
''',

    'forcing_result_onto_recursion': '''
<p>Don't force the result onto recursion, don't tell it what it should return. Just let it be and
assume it will do its job. If this assumption is correct, then the rule will work for a larger case.</p>
<p>Is your recursive call of the form <code>permute(T, [H|...])</code>? This forces the recursive call to
also <em>return</em> the head <code>H</code> which it <em>doesn't know of</em> since you previously took it away.
Inserting the head into the result, returned by the recursive call, is your job. To put it shortly,
insert <code>H</code> outside of the recursive call.</p>
''',

    'recursive_case': '''\
<p>The base case is ok. However, what about the general recursive case?</p>
''',

    'no_insert_or_delete': '''\
<p>The base case is ok. However, what about the general recursive case? Perhaps it's a good idea
to reuse some previous exercise?</p>
''',

    'predicate_always_false': '''\
<p>It seems your predicate is <emph>always</emph> "false". Did you give it the correct name,
or is it perhaps misspelled?</p>
<p>If the name is correct, check whether something else is misspelled, perhaps there is a full stop instead of
a comma or vice versa, or maybe you typed a variable name in lowercase?</p>
<p>It is, of course, also possible that your conditions are too restrictive, or even impossible to satisfy
(as would be, for example, the condition that an empty list <code>[]</code> is equal to a list with
exactly three elements <code>[A,B,C]</code>, or something similarly impossible).</p>
''',

    'timeout': '''\
<p>Is there an infinite recursion at work here? How will it ever stop?</p>
<p>Or perhaps is there a missing, faulty, or simply incompatible (with the general recursive case) base case?</p>
''',
}