I saw this problem posted as an interview question asked at Bloomberg:

Given an integer N, print numbers from 1 to N in lexicographic order. Restriction. One cannot use strings or characters.

Below is my solution to this problem. Can the algorithm be improved?

#!/usr/bin/env python
import sys
import traceback

def printlexnum(i, tens, number):
    lexnum = i*tens
    for j in range(lexnum,min(number+1,lexnum+tens)):
        print j
    if number>=lexnum:
        printlexnum(i, tens*10, number)

    if len(sys.argv) < 2:
        number = 0
        while number < 0:
            number = int(raw_input('please enter number >0: '))
        if number == 0:
        number = int(sys.argv[1])
        if number <= 0:
            print "Bad argument." + number + " must be greater than zero."
    for i in range(1,min(10,number+1)):
        print i
        printlexnum(i,10, number)
except ValueError, e:
    print sys.argv[1], " Input not an integer"
except Exception, e:
    print sys.argv[1], " Exception thrown"
    a = 1 # dummy line

Okay, let me point out some stylistic things first:

  • Doing traceback.print_exc() in an except block feels somewhat odd. Either you hide the stack trace by printing your own error message—which is actually helpful to the end user—or you leave the exception as it is.
  • Exceptions should be caught locally near to the code which may raise them. So having a big try block with that many lines is not really a good idea. Especially when you are catching all exceptions in the end—you are just hiding stuff that could be totally your fault.
  • The finally is useless? If you want to do nothing in a block, then use pass; but in your case, you can just leave the finally block out.
  • For exceptions your program could actually recover from, you really should do exactly that. When the user gets prompted for a number and enters something else, give him an error but let them try again.
  • In regards to the previous point, you actually have some hint of letting the user try again, with the while number < 0:. However, if the user enters a non-number int() will throw a ValueError and the program will just exit.
  • Using sys.exit(1) is like shutting your computer down by plugging the cable. Provide a better way to shut down your program. Use the existing exception mechanism to shut it down.
  • if number == 0: sys.exit(1) — if you’re not accepting a zero either, why don’t you change the while loops condition to “lower or equals zero”?
  • printlexnum(i, 10, number) — if the second parameter is always a 10, why have it as a parameter?
  • return — No need to explicitely return from a function when that’s the last statement of the function and no value is specified.

Moving on to the algorithm:

  • The order is not correct. For example 100 is being sorted after 19, when it should be sorted after 10 (like 10 is sorted after 1).
  • The for-loop in the “main” program should really be handled by the algorithm too. There should be some high-level printlexnum(n) which just prints all numbers from 1 to n.

The easiest way to get a lexicographic order of numbers is when you sort their string representations because strings are always sorted lexicographically. You can actually do this in a single line:

print('\n'.join(sorted(map(str, range(1, number + 1)))))
  • \$\begingroup\$ Thank you for all the feedback. BTW, a restriction of the problem (which I have edited) is not to use strings. \$\endgroup\$
    – KeithSmith
    Jan 23 '14 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.