模拟排列计数器

Question

对于没有重复数字的给定数字，我想添加正确的金额以获得下一个没有重复数字的数字。这可能就像加 1 一样简单，或者加百，因为当给定数字很高时它会变得复杂。包含重复数字的数字示例有 11、345675、4335、24364。没有重复数字的示例有 12、735691、89、623490。

有趣的一点是，一个号码一旦重复就被抓到，永远不会有超过 2 个重复数字，也不会有多组重复数字。比如1232、654334、765661永远不会出现。

有些情况我不想发生。我不希望有循环计数并只返回没有重复数字的数字。我希望程序能够获取一个没有重复数字的数字，并通过剖析和评估数字知道要添加多少。

一个我不想要的例子。这只是循环，直到它检测到一个没有重复数字的数字。

start = 532461 # given number

while True:
    start += 1

    if len(set(str(start))) >= len(str(start)):
        print(start)
        break

这将打印 532467，下一个没有重复数字的数字。

这个程序应该（在我看来，这可能是错误的）将给定的数字传递给一个函数，做任何需要知道要添加多少给定的数字才能得到下一个数字的数字重复数字，或添加它找出需要的内容，但最好一次性添加，然后结束。该程序可能会遍历数字的位置值，或将数字更改为字符串，或将其分解为列表或任何需要的东西。相同的算法需要从一位数到 10 位数字。

没有函数的例子。（最重要的部分）

number = 231
mimicPermutations(number)
print(number)

>> 234

这很可能是不可能的，或者真的很复杂，但我并不是在寻找最快或最实用的方法来做到这一点。如果您不知道我要解释的内容以及您不了解的内容，请提出澄清问题或发表评论，我将相应地编辑我的解释。

有 3 条规则最接近我想做的事情。使用给定数字加 1 检测重复数字：

如果没有冲突，加1。
如果检测到数字非零冲突，确定发生冲突的最低位值。
如果其他数字没有冲突，但与零有冲突，加1。

输入5850会检测十位加1。 91235264会检测到百位加1，得到91235364，然后再给91235464，再给91235564，再给91235664，再给91235764。

输入6598，加一是6599，有重复数字。取非零冲突的最低位，也就是个位，程序加1，则输出为6600，程序看到千位有非零冲突，百位，以及 1 到百位。输出为6700，然后，没有非零冲突，程序加1，最后得到6701。该方法每次只在确定值的地方加1，如例子所示，不跳过所有重复一次数字。

这个问题不是关于使用最有效的方法或方式来完成所需的输出。

Answer 1

首先，您将数字加 1。如果这个数字没有重复数字，你就完成了。否则，您可以遵循以下算法。

（我们把数字看成一个字符串。）

找到第一个重复的数字。
将其标记为“要更改的位置”（代码中的change_at_location）。
在要更改的位置，将数字递增到下一个最高的“可用”数字（即直到数字中的那个点才重复的数字）。 [注意：这样的数字可能并不总是可用，因为所有更高的数字可能已经被使用。]
如果有这样的数字，
- 增加要更改的位置的数字。
- 在该位置之后，按升序查看所有可用（即到该点未使用）的数字，然后一一插入。
其他
- 将要改回的位置移动 1

注意：如果要更改的位置达到-1，则在开头插入一个虚拟'0'，并将位置更新为0，然后重做。

以下是两个片段，一个带有循环，您不想要的解决方案，但很容易让我们相信它“有效”，第二个没有使用上述算法的循环。

def next_non_repeating(x):
    x = int(x) + 1
    x_int = int(x)
    x_str = str(x)
    while True:
        if len(set(str(x_int))) == len(str(x_int)):
            return x_int
        x_int += 1

def next_non_repeating_no_loop(x):
    x = int(x) + 1

    def next_digit(c):
        if int(c) >= 9:
            return None
        return str(int(c) + 1)

    x_str = str(x)
    x_digits = list(x_str)

    locations = {}
    digits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
    repeated = False
    repeated_digit = None
    for idx, c in enumerate(x_str):
        if c in locations:
            repeated = True
            repeated_digit = c
            locations[c].append(idx)
            break
        else:
            locations[c] = [idx]

    if not repeated:
        return int(x_str)

    change_at_location = locations[repeated_digit][-1]
    while True:
        if change_at_location == -1:
            x_digits.insert(0, '0')
            change_at_location = 0

        answer_digits = x_digits.copy()
        change_digit = x_digits[change_at_location]
        next_available_digit = None
        _n = change_digit
        while True:
            _n = next_digit(_n)
            if _n is None:
                break

            if _n not in x_digits[:change_at_location]:
                next_available_digit = _n
                break

        if next_available_digit is not None:
            available_digits = digits.copy()
            answer_digits[change_at_location] = next_available_digit
            for d in answer_digits[:change_at_location + 1]:
                available_digits.remove(d)
            for idx in range(change_at_location + 1, len(x_digits)):
                answer_digits[idx] = available_digits.pop(0)
            break
        else:
            change_at_location -= 1

    return int(''.join(answer_digits))

如果您想凭经验说服自己（而不是遵循逻辑），

您可以按如下方式进行，

bad = []
invalid = []
for i in range(9876543211):
    if len(str(i)) > len(set(str(i))) + 1:
        invalid.append(i)
        continue
    if next_non_repeating(i) != next_non_repeating_no_loop(i):
        bad.append(i)

列表bad仍然是空的，从而“证明”了正确性。

但是请注意，这个循环将花费很长时间到运行，因为 loop-y 方式实际上效率很低，从下面的比较可以看出，

%time next_non_repeating(987654322)
CPU times: user 42.5 s, sys: 91.8 ms, total: 42.6 s
Wall time: 42.6 s
Out[107]: 1023456789

%time next_non_repeating_no_loop(987654322)
CPU times: user 52 µs, sys: 0 ns, total: 52 µs
Wall time: 55.3 µs
Out[108]: 1023456789

所以非循环变体实际上要快得多，因此也证明了除了纯粹的学术好奇之外寻找这种变体的必要性。

注1：该函数不关心“原数无重复数字”或“只有一组重复数字”等限制，给定任何数字它会尽可能找到下一个非重复号码。

注2：代码可以稍微清理一下。它是有目的的编写，以便于遵循思维过程。

Answer 2

找到最低有效数字，您可以将其增加到不是较高数字之一的数字。将该数字更改为该值，然后将剩余的每个数字替换为尚未使用的最低数字。

带有测试用例的示例代码：

def next_nonrepeating(n):
    digits = [int(x) for x in ('0' + str(n))[::-1]]
    for i in range(0, len(digits)):
        higher = set(d for d in digits[i+1:-1])
        d = min((x for x in range(digits[i]+1, 10) if x not in higher), default=None)
        if d is not None:
            digits[i] = d
            higher.add(d)
            for j in range(i-1, -1, -1):
                m = min(x for x in range(10) if x not in higher)
                digits[j] = m
                higher.add(m)
            return int(''.join(str(x) for x in reversed(digits)))


test_cases = [
    (6598, 6701),
    (987654321, 1023456789),
    (1234, 1235),
    (1239, 1240),
    (9876, 10234),
]

for x, want in test_cases:
    got = next_nonrepeating(x)
    if got != want:
        print('next_nonrepeating(%d) = %s, want %d' % (x, got, want))

模拟排列计数器

Mimic Permutations Counter

python

algorithm

permutation