CODEWITHSUNDEEP
pythonperformance
SetSlapShot
SetSlapShot

Reputation: 1298

What is the quickest way to get a number with unique digits in python?

Lemme clarify:

What would be the fastest way to get every number with all unique digits between two numbers. For example, 10,000 and 100,000.

Some obvious ones would be 12,345 or 23,456. I'm trying to find a way to gather all of them.

for i in xrange(LOW, HIGH):
  str_i = str(i)
  ...?

Upvotes: 8

Views: 2813

Answers (5)

kisan kumar behera
kisan kumar behera

Reputation: 1

no_list=['115432', '555555', '1234567', '5467899', '3456789', '987654', '444444']
rep_list=[]
nonrep_list=[]
for no in no_list:
    u=[]
    for digit in no:
        # print(digit)
        if digit not in u:
            u.append(digit)
    # print(u)

    #iF REPEAT IS THERE
    if len(no) != len(u):
        # print(no)
        rep_list.append(no)
    #If repeatation is not there
    else:
        nonrep_list.append(no)
print('Numbers which have no repeatation are=',rep_list)
print('Numbers which have repeatation are=',nonrep_list)

Upvotes: 0

ealfonso
ealfonso

Reputation: 7302

Here is an answer from scratch:

def permute(L, max_len):
    allowed = L[:]
    results, seq = [], range(max_len)
    def helper(d):
        if d==0:
            results.append(''.join(seq))
        else:
            for i in xrange(len(L)):
                if allowed[i]:
                    allowed[i]=False
                    seq[d-1]=L[i]
                    helper(d-1)
                    allowed[i]=True
    helper(max_len)
    return results

A = permute(list("1234567890"), 5)
print A
print len(A)
print all(map(lambda a: len(set(a))==len(a), A))

It perhaps could be further optimized by using an interval representation of the allowed elements, although for n=10, I'm not sure it will make a difference. I could also transform the recursion into a loop, but in this form it is more elegant and clear.

Edit: Here are the timings of the various solutions

  • 2.75808000565 (My solution)
  • 8.22729802132 (Sol 1)
  • 1.97218298912 (Sol 2)
  • 9.659760952 (Sol 3)
  • 0.841020822525 (Sol 4)

Upvotes: 2

Tadeck
Tadeck

Reputation: 137320

Use itertools.permutations:

from itertools import permutations

result = [
    a * 10000 + b * 1000 + c * 100 + d * 10 + e
    for a, b, c, d, e in permutations(range(10), 5)
    if a != 0
]

I used the fact, that:

  • numbers between 10000 and 100000 have either 5 or 6 digits, but only 6-digit number here does not have unique digits,
  • itertools.permutations creates all combinations, with all orderings (so both 12345 and 54321 will appear in the result), with given length,
  • you can do permutations directly on sequence of integers (so no overhead for converting the types),

EDIT:

Thanks for accepting my answer, but here is the data for the others, comparing mentioned results:

>>> from timeit import timeit
>>> stmt1 = '''
a = []
for i in xrange(10000, 100000):
    s = str(i)
    if len(set(s)) == len(s):
        a.append(s)
'''
>>> stmt2 = '''
result = [
    int(''.join(digits))
    for digits in permutations('0123456789', 5)
    if digits[0] != '0'
]
'''
>>> setup2 = 'from itertools import permutations'
>>> stmt3 = '''
result = [
    x for x in xrange(10000, 100000)
    if len(set(str(x))) == len(str(x))
]
'''
>>> stmt4 = '''
result = [
    a * 10000 + b * 1000 + c * 100 + d * 10 + e
    for a, b, c, d, e in permutations(range(10), 5)
    if a != 0
]
'''
>>> setup4 = setup2
>>> timeit(stmt1, number=100)
7.955858945846558
>>> timeit(stmt2, setup2, number=100)
1.879319190979004
>>> timeit(stmt3, number=100)
8.599710941314697
>>> timeit(stmt4, setup4, number=100)
0.7493319511413574

So, to sum up:

  • solution no. 1 took 7.96 s,
  • solution no. 2 (my original solution) took 1.88 s,
  • solution no. 3 took 8.6 s,
  • solution no. 4 (my updated solution) took 0.75 s,

Last solution looks around 10x faster than solutions proposed by others.

Note: My solution has some imports that I did not measure. I assumed your imports will happen once, and code will be executed multiple times. If it is not the case, please adapt the tests to your needs.

EDIT #2: I have added another solution, as operating on strings is not even necessary - it can be achieved by having permutations of real integers. I bet this can be speed up even more.

Upvotes: 15

user764357
user764357

Reputation:

List comprehension will work a treat here (logic stolen from nneonneo):

[x for x in xrange(LOW,HIGH) if len(set(str(x)))==len(str(x))]

And a timeit for those who are curious:

> python -m timeit '[x for x in xrange(10000,100000) if len(set(str(x)))==len(str(x))]'
10 loops, best of 3: 101 msec per loop

Upvotes: 4

nneonneo
nneonneo

Reputation: 179392

Cheap way to do this:

for i in xrange(LOW, HIGH):
    s = str(i)
    if len(set(s)) == len(s):
        # number has unique digits

This uses a set to collect the unique digits, then checks to see that there are as many unique digits as digits in total.

Upvotes: 7

Related Questions