Get the next bigger number by rearranging the digits of the input integer

Question

from itertools import permutations
def next_bigger(n):
    nlist = list(str(n))
    perm = permutations(nlist,len(str(n)))
    perm = set(perm)
    listofperm = []
    nlist = int("".join(nlist))
    for x in perm:
        form = int("".join(x))
        if form < nlist:
            continue
        else:
            listofperm.append(form)
    listofperm = sorted(listofperm)

    if (listofperm.index(n) + 1) == len(listofperm):
        indexofn = listofperm.index(n)
    else:
        indexofn = listofperm.index(n) + 1 
    return listofperm[indexofn]

I'm trying to get the next bigger number by rearranging the digits of n but my code is very inefficient can you suggest ways to make my code more efficient and faster?

Inputs would be any integer.

Answer 1

Since this is asking for a new algorithm, I will try to provide some hints. Look at the output of

from itertools import permutations
sorted([a*1000 + x*100 + y*10 + z for a,x,y,z in permutations([1,2,3,4])])

Which digits are most likely to be different between consecutive members of this list?

Look at the elements that start with 4. Can you see a pattern in the rest of their digits? If so, how do the rest of the digits have to change when the first changes?

Does the same pattern hold for digits a,b,c,d in place of 1,2,3,4?

Answer 2

It's not so much the implementation.

With problems like these (typical coding competition ones) it's always the same, that you have to find a clever algorithm instead of writing down as code a straightforward implementation of the problem description.

I haven't myself analyzed the problem, but I'd try to answer some questions:

• Of all possible permutations, might it be enough to just exchange 2 digits? Or: Can you be sure that including a third digit into the exchange is irrelevant (result below the original number, result identical to the 2-digit case, or result higher than the 2-digit result, but not between the original number and the 2-digit result)?
• If you can prove two digits to be enough, which are the two digits that give the smallest result (greater than the original number)?

Maybe it helps to do some examples by hand and see some pattern.