scramble prime challenge

[Albert Chan]

I tried building the primes first, but it turns out very slow.

Instead, I loop over permutations, but only the digits sorted cases.
This reduces the permutations to manageable size.

Code:

digits  permutations to check
2       10
3       20
4       35
5       56
6       84
7       120
8       165
9       220
10      286

Another benefit is there is no big list to handle, with space complexity = O(digits)

Code:

from gmpy2 import is_prime, mpz

def unique_permute(lst, i, n):          # update in-place !
    if i >=n : yield lst                # reference only !
    for j in xrange(i, n):
        if lst[j] in lst[i:j]: continue # unique only
        lst[i],lst[j] = lst[j],lst[i]   # swap
        for x in unique_permute(lst,i+1,n): yield x
        lst[i],lst[j] = lst[j],lst[i]   # restore

def scramble_primes(digits):
    lst = ['0']*digits
    idx = range(digits-1,-1,-1)
    next = '1307000901'
    while lst[0] != '9':
        for i in idx:
            x = lst[i] = next[ord(lst[i])-48]
            if x == '1': continue                   # do carry
            for j in xrange(i+1,digits): lst[j]=x   # force sorted
            break
        if is_prime(mpz(''.join(lst))):
            gen = unique_permute(lst[:],0,digits)
            gen.next()                              # first case checked
            if all(is_prime(mpz(''.join(y))) for y in gen):
                yield int(''.join(lst))             # scramble prime found!

Note: I did not add the trivial test to return 2,5 as 1-digit scramble primes.

>>> for d in xrange(2,21): print d, list(scramble_primes(d))
...
2 [11, 13, 17, 37, 79]
3 [113, 199, 337]
4 []
5 []
6 []
7 []
8 []
9 []
10 []
11 []
12 []
13 []
14 []
15 []
16 []
17 []
18 []
19 [1111111111111111111L]       # see http://oeis.org/A004022
20 []

Above take 0.3 seconds on my laptop