### Archives

### Categories

Advertisements

June 30, 2008

Posted by on 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

maxd.append(0)

maxd.reverse()

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

def seq_gen(n, atmax, lst, s, left):

if n==1:

for i in lst:

sol.append(s+srep[i])

return

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.

Advertisements

%d bloggers like this: