1

I am going through popular interview questions, and came up with the following solution to "Compute all permutations of a string."

def perm(s):
    if len(s) == 0:
        return ['']
    else:
        l = []
        prev = perm(s[1:])
        for old_str in prev:
            for i in range(len(old_str)):
                new_str = old_str[0:i] + s[0] + old_str[i:]
                l.append(new_str)
        return l

However, this solution returns [] on all input. If I make the string in the base case any string other than the empty string, the computation runs as expected. For example, with 'hi' in the base case, perm('abc') returns

['abchi', 'bachi', 'bcahi', 'bchai', 'acbhi', 'cabhi', 'cbahi', 'cbhai', 'achbi', 'cahbi', 'chabi', 'chbai', 'abhci', 'bahci', 'bhaci', 'bhcai', 'ahbci', 'habci', 'hbaci', 'hbcai', 'ahcbi', 'hacbi', 'hcabi', 'hcbai']

As far as I can tell the algorithm for this code is correct. I am unsure of why the empty string isn't behaving as I anticipate, while other strings do. I have referenced this thread for better solutions, but I am still puzzled by why this one doesn't work.

AKX
  • 152,115
  • 15
  • 115
  • 172
Tazzure
  • 75
  • 1
  • 4
  • 1
    The algorithm is *not* correct. – Martijn Pieters Aug 12 '18 at 19:43
  • 1
    See [For loop uses a recursive call's output as parameter](//stackoverflow.com/q/51809957) for a question asked earlier today that produces correct permutations. See if you can spot the difference between the implementations. Ignore the fact that the other works with tuples rather than strings. – Martijn Pieters Aug 12 '18 at 19:45
  • 2
    Notice how `perm('')` and `perm('a')` differ. The latter should return `['a']`, but doesn't. Try to work through the logic to see why it returns an empty list in that case. Compare this with the other implementation to see if you can spot why that version does work. – Martijn Pieters Aug 12 '18 at 19:48
  • My algorithm was to compute all permutations of the previous string, then insert the current character of the string to all indices of the permutations of the smaller string. From what I can tell, this is the method that is being used in Cracking the Coding Interview, however the code is Java. Any hints on what I'm missing? – Tazzure Aug 12 '18 at 19:49
  • How many times will `range(len(old_str))` iterate for the case where `s` is length 1, and thus `prev` is a list with a string of length 0? – Martijn Pieters Aug 12 '18 at 19:51

1 Answers1

0

You should probably add a special case for len(s)==1.

As written, the recursion will go down to the base case with an empty string, and then prev will be []. The for loop that follows this will never run, because prev is empty, so the final result will be empty too.

fishingpole
  • 43
  • 5