使用排列查找下一个最大数

Question

Create a function that takes a positive integer and returns the next bigger number that can be formed by rearranging its digits.

为此，我使用了以下代码：

使用的逻辑：

1. 编写一个脚本，完成数字的所有排列，例如123->；132,321,231,...
2. 从可能的组合中选择最大的数字
3. 如果该数字大于原始数字，则返回该数字，否则返回-1

代码块：

import itertools
def next_bigger(n):
    # [int(x) for x in str(n)] ex: convert 123 to array [1,2,3]
    # list(set(itertools.permutations... gives you a list of permutation e.g. [[1,3,2],[3,2,1],[2,3,1],...]
    # [int(''.join(map(str,x))) for x in ...  converts each permuted list into a number e.g. convert [2,3,1] -> 231
    # for num in sorted(...if num>n: --> if 321 is bigger than 123, return it
    
     for num in sorted([int(''.join(map(str,x))) for x in list(set(itertools.permutations([int(x) for x in str(n)])))]):
        if num>n:
            return num
        else:
            return -1

预期产出：

nextBigger(num: 12)   // returns 21
nextBigger(num: 513)  // returns 531
nextBigger(num: 2017) // returns 2071
nextBigger(num: 9)   // returns nil
nextBigger(num: 111) // returns nil
nextBigger(num: 531) // returns nil

实际输出：Test results fail

解决方案尝试#2：

import itertools
def next_bigger(n):
    # [int(x) for x in str(n)] ex: convert 123 to array [1,2,3]
    # list(set(itertools.permutations... gives you a list of permutation e.g. [[1,3,2],[3,2,1],[2,3,1],...]
    # [int(''.join(map(str,x))) for x in ...  converts each permuted list into a number e.g. convert [2,3,1] -> 231
    # for num in sorted(...if num>n: --> if 321 is bigger than 123, return it
    
    a = []
    results = 0
    for num in sorted([int(''.join(map(str,x))) for x in list(set(itertools.permutations([int(x) for x in str(n)])))]):
        if num>n:
            a.append(num)
    results = a[0]
            
    return results

预期输出：通过除长数字外的所有测试用例

我的代码怎么了

Answer 1

标题上写着“使用置换”，但你不需要为此使用置换

定义了发出的元组itertools.permutations的顺序；但不幸的是，当组合起来时，它并不总是以递增的顺序生成数字。此外，如果位数非常大，计算所有排列将花费非常长的时间

重新表述这个问题：对于任何给定的N，最小的数字（N2）是多少

1. 0 <= N < N2，以及
2. 每个数字在N和N2中出现的次数相同

（如果N2不存在，则返回None）

我们可以从N开始执行N+=1，直到满足条件2为止，或者直到条件2不再满足为止，因为N中的总位数增加了。（Python3中的int没有定义它可以得到多大的限制，所以我们不会得到溢出。）如果N非常大，这仍然（平均）非常慢，但是理论上它最终会返回

以下是我将如何解决这个问题：

def main(N):
    n=list(map(int,str(N)))
    for i_r in reversed(range(len(n))):
        for i_l in reversed(range(i_r)):
            if n[i_l]<n[i_r]:
                t_l=n[i_l]
                t_r=n[i_r]
                n[i_l]=t_r
                n[i_r]=t_l
                return int(''.join(map(str,n)))
    return None

首先将N转换为数字列表（同时保留顺序）。这将使N更容易操作

做两个标记i_l和i_ri_l和i_r将始终分别位于左侧和右侧。它们将从N的最低有效（即右侧）开始

他们将通过N这样的过程，例如：

4321    4321    4321    4321    4321    4321
  lr     l r    l  r     lr     l r     lr  

当i_l < i_r时，交换这些数字以生成一个更大的数字，这满足条件1。由于i_l和i_r从N的最低有效侧开始，因此该新数是满足条件2的最小数。如果该数字不存在，则函数返回None

（实际上，return None是不必要的，因为默认情况下函数返回None，但是明确声明它会更清楚地表明这是预期的行为。）

使用此解决方案，即使N为10000位，函数也将在合理的时间内返回

Answer 2

您需要下一个最大的数字，但当前选择的any置换数大于输入数You should be the picking the minimum among such numbers

还要注意，例如对于输入9或111；没有其他排列；因此，您可能只想返回next biggest-permutation or None

你可以考虑修改：

import itertools
def next_bigger(n):
    # [int(x) for x in str(n)] ex: convert 123 to array [1,2,3]
    # list(set(itertools.permutations... gives you a list of permutation e.g. [[1,3,2],[3,2,1],[2,3,1],...]
    # [int(''.join(map(str,x))) for x in ...  converts each permuted list into a number e.g. convert [2,3,1] -> 231
    # for num in sorted(...if num>n:  > if 321 is bigger than 123, return it
    
     minval = -1
     for num in sorted([int(''.join(map(str,x))) for x in list(set(itertools.permutations([int(x) for x in str(n)])))]):
        if num>n:
            if minval == -1 or minval > num:
                minval = n
     return minval

适当的测试用例：

nextBigger(num: 1176) //should return 1617