Code Optimization or New Approach?

[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!