Search code examples
pythonstringalgorithmpermutation

Smallest permutation of given number

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?

Solution

  • 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