[Tutor] permutations using list comprehensions

[Danny Yoo]

> The best I've been able to do is pretty obvious:-
> def perms (t):
>     if len (t) == 0:
>         return []
>     else:
>         return [[x] + perms ([y for y in t if y <> x]) for x in t]
>
>        Needless to say, it doesn't work.  It does produce a list of
> lists but they are so horribly nested that I've no idea whether I am
> getting close.


Hi Logesh,

Ok, let's try this out.  Let's assume for the moment that it works for
lists of length two.  That is, let's say that we know that:

    perms([2, 3]) == [[2, 3],
                      [3, 2]]

will work.  I'll pretend this without even looking at the function
definition.  *grin*


With our "let's pretend" hat on, now let's think about what happens if we
trying doing perms() on a slightly larger example:

    perms([1, 2, 3])

on the function.  We know what we expect to get, and now we're checking to
see if our function gives that to us.


We look at the function definition, and the list isn't empty, so we hit
the recursive case:

    return [[x] + perms ([y for y in t if y <> x]) for x in t]


This is a bit nested, but if we expand these list comprensions out, then
we get:

    return [[1] + perms([2, 3]),
            [2] + perms([1, 3]),
            [3] + perms([1, 2])]


This looks slightly off.  From looking at this, we already notice that the
return value only has three elements, and that's probably not what we
want.  We want a list of six elements.  (3! == 6)



But let's also take a look at one of those subexpressions --- let's look
at:

    [1] + perms([2, 3])

We know that perms()  returns a list of list of integers, and:

    [1] + perms([2, 3])

will do something slightly funky!  We already know what we expect out of
perms([2, 3]), so let's work this out.  We'll get back:

        [1] + perms([2, 3])

    ==> [1] + [[2, 3], [3, 2]]

    ==> [1, [2, 3], [3, 2]]


So just from a pure typing point of view, we're in a slight mess, because
we now have a mixed list of either sublists or integers.  What I think you
want to get, instead, is something like:

    [[1, 2, 3],
     [1, 3, 2]]

for the value of the first subexpression.  Does this make sense so far?



> I've also tried adding and removing square brackets in various
> combinations.

Don't flail randomly.  Just adding brackets here and there will not help.
Recursive functions demand more respect than that.  *grin*


If you have more questions, please feel free to ask.