0

My code takes in a string and returns a list of strings that are permutations of the input string. (No repeats)

def perm(slist, c):
  rTup = []
  for s in slist: #O(n!)    
    for i in range(len(s) + 1): #O(n)
      rstr = s[:i] + c + s[i:] #O(n)
      rTup.append(rstr)
  return rTup  


def permWrap(s): #wrapper
  slist = [s]
  rlist = [""]
  for i in reversed(range(-1,len(s)-1)): #O(n)
    rlist = perm(rlist , s[i+1])

  return list(set(rlist))  #O(n!)

permWrap("abbc")

I put little comments for what I believe the time complexity is at each step. However, I could be wrong.

I am thinking that the time complexity is O(n! * n^3). Is that correct?

In addition, how would you make this function more efficient?

Evan L
  • 37
  • 1
  • 12
  • I would import permutations from collections. A generator is much more space efficient. – Kenny Ostrom Sep 24 '18 at 23:17
  • @KennyOstrom `itertools.permutations` outputs duplicates if the input sequence contains repeated items. They can be eliminated using a set, but that consumes space, and is very slow if thete are more than a few repeats. – PM 2Ring Sep 24 '18 at 23:28
  • For an efficient permutation algorithm that doesn't produce duplicates when the input contains repeated items please see https://stackoverflow.com/a/31678111/4014959 – PM 2Ring Sep 24 '18 at 23:30
  • @PM2Ring , I will look into this! Thanks! Do you guys also know what the complexity of my code is? I just want to make sure I understand how to analyze Big O time complexity. – Evan L Sep 24 '18 at 23:56
  • I'm not sure about the top O(n!), I'll check it after I've had some sleep & I'm not on my phone. ;) The O(n) all look correct. – PM 2Ring Sep 25 '18 at 00:15
  • I understand the question now. Please check out https://stackoverflow.com/questions/12836385/how-can-i-interleave-or-create-unique-permutations-of-two-strings-without-recur/12837695#12837695 – Kenny Ostrom Sep 25 '18 at 12:41
  • @PM2Ring Thanks! My logic is: The line "for s in slist:" has that variable "slist." "slist" will eventually contain the list of all unique string permutations. In addition, there are n! permutations of the input string "s" (mathematical property of factorial). Therefore, slist (the list of unique permutations) increases with O(n!). Thoughts? – Evan L Sep 26 '18 at 00:05
  • @KennyOstrom That is a really amazing solution! Thanks, I will look into it! – Evan L Sep 26 '18 at 00:05
  • That's correct, but as you say, it will eventually contain n! items, but its average size over the course of the execution of the algorithm is less than that. – PM 2Ring Sep 26 '18 at 00:12
  • Note that my code I linked earlier also implements the permutation algorithm of Narayana Pandita. – PM 2Ring Sep 26 '18 at 00:16
  • Yes, both of those links are the same underlying algorithm. For the complexity of this, it looks like a single pass through for each permutation, so n!, followed by another n! to make a set, then another n! to make a list. But they happen in sequence, so O(3n!) is O(n!). Internally, to perm, which I asserted must be O(n!), the slist approaches n! but when it gets there the O(n) steps reach a trivial base case, and are O(1), so it's (n-1)!(n+n) at worst, which is basically a fancy way of saying O(n!). – Kenny Ostrom Sep 26 '18 at 12:45
  • I'm no expert, but it looks like you are O(n!) time and space, and you differ by a small constant factor from the Narayana Pandita algorithm, in worst case time complexity. But high space hurts performance for its own reasons, if you're lucky enough not to run out of memory, and you always run worst case, never benefiting from repeats. – Kenny Ostrom Sep 26 '18 at 13:12
  • @PM2Ring True, the average size is lower. However, as I understand it, big O notation has little to do with average size/time and more with how the code scales. From what I am seeing, that slist (regardless of how far along the execution is) is increasing proportional to n!. Therefore, it scales as O(n!). I think... – Evan L Sep 26 '18 at 22:33
  • @KennyOstrom I understand everything you said up until you said that the O(n) steps become O(1) steps. From what I understand, as the execution goes on, those O(n) steps start iterate from 1 char in the first pass through to n chars in the final pass through, making it scale by O(n). Can you elaborate? Also, yeah my space efficiency seems really bad. I am seeing that while looking through Narayana Pandita algorithm. – Evan L Sep 26 '18 at 22:39
  • When you have n! candidates and then do an O(n) step of adding the next character into each ... there are no more characters to add. "for i in range(0+1)" – Kenny Ostrom Sep 27 '18 at 12:38
  • @KennyOstrom OH I see. I was under the impression that you were saying the complexity of that loop is O(1) instead of O(n!), but you are actually saying it is O((n-1)!). Okay so here's my understanding: total time complexity = n * (n-1)! * n * n = (n-1)! * n^3. Explanation: n [for i in reversed...] * (n-1)![for s in slist ] * n[for i in range ] * n[rstr = ...] = (n-1)!*n^3 – Evan L Sep 28 '18 at 21:58
  • I don't think you should count the outer loop in permWrap, because that contributes to generating n! items in slist, for inside perm. So I think it's O(cn! + (n-1)!*n*n), which would reduce to O(n * n!), but I don't have a proof, and thus have not posted an answer. That was really a hasty analysis, and I often make mistakes on hasty looks. Furthermore, that's basically the same as O(n!), and the O(n!) space complexity is a bigger problem. – Kenny Ostrom Sep 29 '18 at 00:54
  • @KennyOstrom I kind of see what you are saying. Huh this is tricky. Okay thanks :) – Evan L Oct 08 '18 at 17:38

0 Answers0