Smallest permutation of given number

Question

I've got a number as a string and I want to find the smallest number composed of original number digits, i.e.

56340902138765401345 -> 10001233344455566789

I'm converting the string to list and sorting it.

num = '56340902138765401345'
a = list(num)
a.sort()

As a number can't start with a zero (but I need to use zeros from the original number) I'm looking for the first nonzero element and put it in front:

inext = next(i for i, x in enumerate(a) if x != '0')
a.insert(0, a.pop(inext))

Then I'm converting list back to string and displaying it.

num2 = ''.join(map(str, a))
print(num2)

It works but it doesn't seem very pythonic or elegant to me. Is there a better way?

Answer 1

We can count the zeroes. Then we remove the zeroes from the number, we sort it and reassemble it. To reassemble we use the first digit, then we add back our zeroes and then the rest of our sorted number.

num = '56340902138765401345'

nzeros = num.count('0')
num = ''.join(sorted(num.replace('0', '')))
print num[0] + ('0' * nzeros) + num[1:]

Result:

 10001233344455566789

Answer 2

There are a couple of minor things that could be improved.

a = list(num)
a.sort()

can be replaced with

a = sorted(num)

The string can be reconstituted from the list with ''.join(sorted(num).

Putting that together you could use a regular expression to move the leading zeroes behind the first non-zero digit:

import re
a = re.sub(r'^(0+)(.)', r'\2\1', ''.join(sorted(num)))

I wouldn't argue that this is more Pythonic, but it is pretty succinct, and possibly more elegant (depending on the beholder, that is).