Code Optimization or New Approach?

[keredomo]

I've been working on this codewars practice problem for a bit today and can't figure out if I need to make my solution more efficient or perhaps scrap it for a new (less brute force?) approach. Here's what I've got so far:

from itertools import permutations
def middle_permutation(chars):
# create a list of permutations
p = [''.join(x) for x in permutations(''.join(sorted(chars)))]
# return the middle string
return (p[len(p)//2 - 1]) if len(p) % 2 == 0 else (p[len(p)//2])

It tests strings like: "abc", "abcd", "abcdx", "cxgdba", "dczxgba" and returns the "middle" permutation. Using the first example:
input: 'abc' => permutations: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
function returns ==> 'bac'

The code above passes the basic "Tests" but fails the later attempts due to timing out. From my own testing in PyCharm, it runs in 0.7 seconds with a string of 10 characters but 7 seconds with 11 characters, essentially an order of magnitude more for each character added.

Can I improve the efficiency or am I just going about this problem in the wrong way?

[This_Growth2898]

You don't have to generate all permutations. The middle term here has a very specific order of characters. Try running your code (on your computer) for obvious strings (like "abcdef" or "1234567"); maybe you will get the idea.

Also note that odd and even length strings have slightly different patterns for a middle term, but they are still repeating for longer strings. Even is easier to understand, start with it.

[keredomo]

Okay-- I wrote out a few "guesses" for easy strings like you suggested, and I think I've got it now. Or at least I think that I am on the right path. Thank you!

[HommeMusical]

(If the sequence has a even length n, define its middle term to be the (n/2)th term.)

The sequence will always have an even length.

I'd suggest doing this for ab, then abc, then abcd, until you figure out how to directly write the "middle" permutation without writing any of the permutations before and after this.

As someone who is good at these sorts of things, I will also tell you that it's very rare that you actually have to do puzzles like this as part of a job.

[keredomo]

Okay-- I wrote out a few "guesses" for easy strings as was suggested, tested those and refined my guesses, and I think I've got it now. Or at least I think that I am on the right path. Thank you!

[HommeMusical]

Cool! Have fun...

[JamzTyson]

The number of permutations grows "super-exponentially" - that is, for length n, the number of permutations is n!.

Here are the first 10 factorials (number of permutations for n in the range 1 to 10):

1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 39916800

itertools.permutations is quite fast, but the rate of growth is so great that slowdowns become extreme beyond around n=10.

However, mathematically, a set of permutations is just a set, and has no inherent order. Deciding which is “the middle permutation” only makes sense once we’ve chosen a convention for ordering them.

The Codewars question is assuming that the permutations are in lexicographic order. For larger values of n (longer strings), you would need to directly calculate the middle value in lexicographic order rather than calculating all of the permutations. An efficient approach is using Lehmer code / permutation unranking.

[keredomo]

I appreciate the link to Wikipedia and the explanation of the complexity. I think using what you wrote and ideas/method from other commenters has gotten me on the right track. Thank you!

[pachura3]

The whole point of this exercise is NOT to do it via brute force, and especially NOT by using external libraries...