[Tutor] Recursive permutation

[Gregor Lingl]

x x schrieb:

> Here is my 2 bits worth.
> If I understand what you want you need only use the Result and make a 
> new list that takes each item and creates all possible orders of that 
> item.
>
Hi x x!

Yes, this is what I suggested in my previous post.

> Result = ['']
>
> def Combination(S):
>
>    if len(S)>0:
>        if S not in Result:
>            Result.append(S)
>            for I in range(len(S)):
>                str2= S[0:I] + S[I+1:len(S)]
>                Combination(str2)
>
>    return Result
>
o.k., your code produces the correct Result. But it suffers from
a serious drawback: it computes most of the elements of Result a
lot of times - therefore you have to check for each of your candidates
if its already in Result. This check is rather expensive, especially if
Result is already a long list.

Another way to get your Result, but much faster is:

def subsets(txt):
    if txt:
        rest = subsets(txt[1:])
        return rest + [txt[0] + x for x in rest]
    else:
        return [""]

it relies on the idea, that you get all subsets of a given
set, if you first compute all subsets, which do not contain the
first element and then add all subsets which contain the first element.
These have the form txt[0]+x where x is a subset without txt[0], that
means it is in the first - already computed - set of subsets.

For a string of 12 elements (resulting in a Result of  4096 elements)
this algorithm is faster  by a factor of 500 than your  function
Combination.

On the other hand, these considerations are of minor importance
if the function is used for solving Eivinds problem, because then
there are necessarily only few elements in txt to be processed and
most of the processing time is used to construct the permutations.

Regards,
Gregor


>
> Combination("123456")
> Result.sort()
>
> print Result
>
>