few problems, approaches and solutions

Beust Sequence! aka sequence of numbers without repeating digits.

Original statement for the problem is here . The problem asks to generate a sequence of increasing numbers with no digits repeating in same number. The problem is quite similar to generating permutations, except for the part that number couldn’t start with 0. Here is my take over the problem. There are three basic things to take care of. First, generating permutations. Second, taking care of the initial 0 problem. And third, not going beyond the limit.

If we are given a list and asked to produce all permutations, all we have to do is, for each entry in the list, consider permutation of rest of the entries(this applies recursively). To generate permutations in lexical order, we just have to select the elements in increasing order.
In the code lst stores the lexically arranged digits. Each recursion chooses one element from the list, and passes rest to the next recursive call.

The second problem is to not count initial 0’s. This problem is handled by left and the associated recursive call. left essentially takes care of whether all the entries to left are 0. If all the left entries are 0, and the current choice is also 0, then we pass the whole choice list to the next recursive call.

The third is to not cross the limit. This is the part which convolutes my solution. Variables atmax, rnge, chldmaxd, maxd all work towards solving this part. The idea is to keep track from the left, of the digits which have reached the maximum. Similar to the case of left before, atmax lets know whether all choices to the left have reached there maximum. This is used to restrict the choices for the next recursive call. ex: if the limit is 1245, and the choice so far is 12, then the choice for next level will be restricted till 0-4. But if its 11, then the next choice could be between 0-9.

sol = []
def seq(inp):
digits = tuple([i for i in range(10)])
maxd = [int(i) for i in str(inp)]
# number in reverse, with the first element always 0
# ex: the maxd would be [0, 5, 2, 1] for limit of 125

srep = tuple([str(i) for i in range(10)])

def seq_gen(n, atmax, lst, s, left):
if n==1:
for i in lst:

rnge = (atmax and [maxd[n]] or [9])[0]

chldmaxd = False
for i in range(len(lst)):
if lst[i] <= rnge: if atmax and lst[i]==rnge: chldmaxd = True if left and lst[i] == 0: seq_gen(n-1, chldmaxd, lst, s, True) else: seq_gen(n-1, chldmaxd, lst[:i]+lst[i+1:]\ , s+srep[lst[i]], False) else: break; seq_gen(len(maxd)-1, 1, digits, "", True) [/sourcecode] The above code's performance could be improved with simple change in termination condition. [sourcecode language='python'] if n==1: for i in lst: sol.append(s+srep[i]) return [/sourcecode] Timing analysis for the solution. real 0m29.297s user 0m28.762s sys 0m0.344s As approaches in Java performed quite faster than this, I tried my own implementation in C/C++, with Bob’s idea of using integers rather than string to save the sequence. Takes about 230ms($time ./a.out) to generate the whole sequence, on my system.

The code is available here

On the other hand, if we just want the count of such numbers possible (8877690), then here is a one approach. The numbers range from 1 digit to 10 digits, because there are only 10 digits and we cant go beyond that without repetition. So considering each such case(ex: 3 digit numbers), the most significant digit can’t be 0, because otherwise it just becomes a 2 digit number(which we account for separately). So there are 9 options for first number [1-9]. Second number onwards, we just have to count the permutation of the remaining digits. In our example of 3 digit numbers, this turns out to be 9*(9*8), written better as 9*(9!/7!).
Doing this for all 1, 2, …, 10 digits gives us the answer.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: