Question about string permutation using Recursion

Question

This is related to recursion. s is string 'abc'.

Return all permutations of s. So the desired output is: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']. But I am having trouble understanding the line in below code :

"for perm in permute(s[:i] + s[i+1:]):"

In the first print statement of"s[:i] + s[i+1:]", it printed out "c" as opposed to "bc". I thought that since index i started at 0 (where i = 0 and let = "a"), "s[:0] + s[o+1:]" would become s[1:]

which should return "bc" because "b" is at index 1 and c is the last letter. But the print statement returned "c" instead.

def permute(s):
    out = []

    # Base Case
    if len(s) == 1:
        out = [s]

    else:
        # For every letter in string
        for i, let in enumerate(s):

            # For every permutation resulting from Step 2 and 3 described above
            for perm in permute(s[:i] + s[i+1:]):
                print('s is ' + s)
                print('s[:i] + s[i+1:] is ' + str(s[:i] + s[i+1:]))
                print('i is ' + str(i))
                print('Current letter is ' + let)
                print('Current perm is ' + perm)

                # Add it to output
                out += [let + perm]
                print('out is ' + str(out))
                print()

    return out          

permute('abc')

s is bc
s[:i] + s[i+1:] is c
i is 0
Current letter is b
Current perm is c
out is ['bc']

s is bc
s[:i] + s[i+1:] is b
i is 1
Current letter is c
Current perm is b
out is ['bc', 'cb']

s is abc
s[:i] + s[i+1:] is bc
i is 0
Current letter is a
Current perm is bc
out is ['abc']

s is abc
s[:i] + s[i+1:] is bc
i is 0
Current letter is a
Current perm is cb
out is ['abc', 'acb']

s is ac
s[:i] + s[i+1:] is c
i is 0
Current letter is a
Current perm is c
out is ['ac']

s is ac
s[:i] + s[i+1:] is a
i is 1
Current letter is c
Current perm is a
out is ['ac', 'ca']

s is abc
s[:i] + s[i+1:] is ac
i is 1
Current letter is b
Current perm is ac
out is ['abc', 'acb', 'bac']

s is abc
s[:i] + s[i+1:] is ac
i is 1
Current letter is b
Current perm is ca
out is ['abc', 'acb', 'bac', 'bca']

s is ab
s[:i] + s[i+1:] is b
i is 0
Current letter is a
Current perm is b
out is ['ab']

s is ab
s[:i] + s[i+1:] is a
i is 1
Current letter is b
Current perm is a
out is ['ab', 'ba']

s is abc
s[:i] + s[i+1:] is ab
i is 2
Current letter is c
Current perm is ab
out is ['abc', 'acb', 'bac', 'bca', 'cab']

s is abc
s[:i] + s[i+1:] is ab
i is 2
Current letter is c
Current perm is ba
out is ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

The first output line is s is bc which explains the rest. Reason for this output is that the inner for-loop recursively calls permute before the first print with s == 'abc' happens. — Michael Butscher
– Michael Butscher, Commented Nov 9, 2019 at 6:15

Michael Hearn · Accepted Answer · 2019-11-09 18:35:15Z

1

This is such a cooky practice problem. so...

for i, let in enumerate(s): gives 0 a for the first value then it passes it to Permute for loop...

[0 a,1 b,2 c] These are the values in the loop at this point

"for perm in permute(s[:i] + s[i+1:]):

which calls the function permute() on you are right it passes bc which calls enumerate('bc') again 0 b for the first value then it passes it to... permute

[0 b,1 c] These are the values in the loop at this point

"for perm in permute(s[:i] + s[i+1:]):

See what's happening? It calls the function permute() on...c ! which is where we were trying to reach. c is the first perm because it is the len(s)==1 that gets added to out at the very start. Definitely not an easy problem. Edit:

The permute function takes the string s and and splits it into the pieces start of s through to the i index which is the s[:i] and the other portion is s[i+1:] which is i+1 to the end of the string. so on bc where i is 0 it takes s[:0] the empty string and s[0+1:] which is index 1 to the end which is just c and permutes on that. s is now length 1 which means it is stored in out. i is zero abc-> bc i is zero bc->c. i was 0 and let=b and perm =c then when i=1 let is c and perm=b .

I thought of something that might make you understand this code a lot better. You should add in a print statement in the position like so.

    # Base Case
if len(s) == 1:
    print('Length is 1 s=',s)
    out = [s]

I think because this is omitted it makes it harder to see when it is reaching the end of needing to call permutation.

edited Nov 9, 2019 at 18:35

answered Nov 9, 2019 at 6:34

Michael Hearn

5768 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Stanleyrr Over a year ago

This makes more sense now. Could you explain why the first perm is "c" and not "b"? If s is "bc" then shouldn't the "for perm in permutate("bc")" statement return "b" as the first perm item?

Michael Hearn Over a year ago

when s=bc it recurses on bc making s=c when i is zero then when i is 1 and let is c then s=b because when s=bc , s[:i]+s[i+1:]=b

Collectives™ on Stack Overflow

Question about string permutation using Recursion

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related