0
\$\begingroup\$
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.

\$\endgroup\$
0

2 Answers 2

0
\$\begingroup\$

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?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I see, thanks it gave me a new idea to implement this \$\endgroup\$ May 3, 2021 at 23:31
1
\$\begingroup\$

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.

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.