<p>标题上写着“使用置换”,但你不需要为此使用置换</p>
<p>定义了发出的元组<a href="https://docs.python.org/3/library/itertools.html#itertools.permutations" rel="nofollow noreferrer">itertools.permutations</a>的顺序;但不幸的是,当组合起来时,它并不总是以递增的顺序生成数字。此外,如果位数非常大,计算所有排列将花费非常长的时间</p>
<p>重新表述这个问题:对于任何给定的<code>N</code>,最小的数字(<code>N2</code>)是多少</p>
<ol>
<li><code>0 <= N < N2</code>,以及</li>
<li>每个数字在<code>N</code>和<code>N2</code>中出现的次数相同</li>
</ol>
<p>(如果<code>N2</code>不存在,则返回<code>None</code>)</p>
<p>我们可以从<code>N</code>开始执行<code>N+=1</code>,直到满足条件2为止,或者直到条件2不再满足为止,因为<code>N</code>中的总位数增加了。(Python3中的<code>int</code>没有定义它可以得到多大的限制,所以我们不会得到溢出。)如果<code>N</code>非常大,这仍然(平均)非常慢,但是理论上它最终会返回</p>
<p>以下是我将如何解决这个问题:</p>
<pre class="lang-py prettyprint-override"><code>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
</code></pre>
<p>首先将<code>N</code>转换为数字列表(同时保留顺序)。这将使<code>N</code>更容易操作</p>
<p>做两个标记<code>i_l</code>和<code>i_r</code><code>i_l</code>和<code>i_r</code>将始终分别位于左侧和右侧。它们将从<code>N</code>的最低有效(即右侧)开始</p>
<p>他们将通过<code>N</code>这样的过程,例如:</p>
<pre><code>4321 4321 4321 4321 4321 4321
lr l r l r lr l r lr
</code></pre>
<p>当<code>i_l < i_r</code>时,交换这些数字以生成一个更大的数字,这满足条件1。由于<code>i_l</code>和<code>i_r</code>从<code>N</code>的最低有效侧开始,因此该新数是满足条件2的最小数。如果该数字不存在,则函数返回<code>None</code></p>
<p>(实际上,<code>return None</code>是不必要的,因为默认情况下函数返回<code>None</code>,但是明确声明它会更清楚地表明这是预期的行为。)</p>
<p>使用此解决方案,即使<code>N</code>为10000位,函数也将在合理的时间内返回</p>