Making a permutations function more efficient

Question

I'm solving a code wars kata problem but am struggling to figure out how to make my function more efficient because I keep getting stuck on the test cases that involve large numbers.

The instructions for the kata are as follows:

Create a function that takes a positive integer and returns the next bigger number that can be formed by rearranging its digits. For example:
12 ==> 21
513 ==> 531
2017 ==> 2071
nextBigger(num: 12)   // returns 21
nextBigger(num: 513)  // returns 531
nextBigger(num: 2017) // returns 2071
If the digits can't be rearranged to form a bigger number, return -1 (or nil in Swift):
9 ==> -1
111 ==> -1
531 ==> -1

(I'm pretty sure) my code is bug free and the only problem it has is its efficiency:

from itertools import permutations

def next_bigger(n):
    possible_nums = [int(''.join(p)) for p in permutations(str(n))]
    possible_nums = list(dict.fromkeys(possible_nums))
    print(possible_nums)
    if possible_nums.index(n)+1 == len(possible_nums):
        return -1
    else:
        return possible_nums[possible_nums.index(n)+1]

I don't know if the permutation() function is whats causing the issue or the list(dict.fromkeys(possible_nums)) but I can't seem to find a more efficient way to find each permutation of the number, n. Any help on whether I should restructure the entire function or just replace some bits of code to make it more efficient is much appreciated!

user_6671342 · Answer

This is a well-known problem: how to get next lexicographical permutation.

The problem in your algorithm is that you generate all possible permutations (O(m!) where m = len(n)) and also process each permutation with list(dict.fromkeys(possible_nums)) creating some dictionary so overall I think is O(m * m!) (I haven't looked what you're trying to do with the dictionaries so I'm not sure if this is the exact complexity but due to permutations it is for sure at least of O(m!). There is no way this would work for large inputs-i.e many digits number, instead I describe a way that we could skip generating permutations!!!

The below greedy algorithm-implementation is only O(m), m = len(n).

The following answer is based on this link where you can find a nice explanation and sample code.

Lets say that the number we want to compute is: 125330

The algorithm:

1) Find longest non increasing suffix. In our case 5330 is the suffix.
2) Identify pivot i.e the next element after the suffix, here pivot is 2
3) Find rightmost successor to pivot in the suffix, i.e the number in the
   suffix that is greater than pivot, in our example rightmost occurrence of
   number 3 in 5330 is greater than pivot=2.  
4) Swap with pivot, so the number now: 135320
5) Reverse the suffix to get the next smallest permutation: 130235

Example code:

def next_permutation(num):
    # Find non-increasing suffix
    arr = list(str(num))
    i = len(arr) - 1
    while i > 0 and arr[i - 1] >= arr[i]:
        i -= 1
    if i <= 0:
        return -1

    # Find successor to pivot
    j = len(arr) - 1
    while arr[j] <= arr[i - 1]:
        j -= 1
    arr[i - 1], arr[j] = arr[j], arr[i - 1]

    # Reverse suffix
    arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
    return int("".join(arr))

Test cases:

In: 12 Out: 21
In: 513 Out: 531
In: 2017 Out: 2071
In: 9 Out: -1
In: 111 Out: -1
In: 531 Out: -1
In: 144 Out: 414

Making a permutations function more efficient

1 Answers