Mimic Permutations Counter

Question

With a given number with no repeating digits, I want to add the correct amount to get to the next number that has no repeating digits it it. This may be as simple as adding 1, or adding hundreds as it gets complex when the given number is high. Examples of numbers with repeating digits in them are 11, 345675, 4335, 24364. Examples of numbers with no repeating digits are 12, 735691, 89, 623490.

An interesting point to make is that there will never be more than 2 repeating digits in a number when caught as soon as it repeats, nor will multiple sets of repeating digits. For example, numbers 1232, 654334, 765661 will never come up.

Some conditions I do not want to occur. I do not want there to be loops counting up and just returning numbers that have no repeating digits. I want the program to be able to take a number with no repeating digits and know how many to add by dissecting and evaluating the number.

An example of what I do not want. This just loops until it detects a number with no repeating digits.

start = 532461 # given number

while True:
    start += 1

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

This will print 532467, the next number with no repeating digits.

This program should (in my thought of it, that may be wrong) pass the given number into a function, do whatever is needed to know how much to add to the given number to get to the next number with no repeating digits, or add as it figures out what is needed but preferably added in one shot, and end. The program may iterate through the place values of the number, or change the number to a string, or dissect it in a list or whatever is needed. The same algorithm will need to work from single digits to 10 digit numbers.

An example without the function. (the most important part)

number = 231
mimicPermutations(number)
print(number)

>> 234

This very well may not be possible or be really really complicated, but I'm not looking for the fastest or most practical way to do this. Please ask clarifying questions or comment if you don't know what I'm trying to explain and if possible what you don't understand about it and I will edit my explanation accordingly.

There are 3 rules that come closest to what I want to do. Using the given number plus 1 to detect repeating digits:

If there are no conflicts, add 1.
If a non-zero conflict in digits is detected, determine the lowest place value in which the conflict occurs.
If there are no other conflicts in digits, but there is a conflict with zeros, add 1.

The input 5850 will detect to add 1 to the tens place. 91235264 will detect to add 1 to the hundreds place, giving 91235364, then again to give 91235464, then again to give 91235564, then again to give 91235664, then again to finally give 91235764.

The input 6598, plus one is 6599, which has repeating digits. Taking the lowest value place digit of where the non-zero conflict occurs, which is the ones place, the program adds 1. Then the output is 6600. The program then sees that there is a non-zero conflict with the thousands place and the hundreds place, and 1 to the hundreds place. The output is 6700. Then, there being no non-zero conflicts, the program adds 1, to finally give 6701. This method only adds 1 to a determined value place at a time, and as the example shows, does not skip all repeating digit numbers at once.

This question is not about using the most efficient method or way of accomplishing the desired output.

Hrishikesh · Accepted Answer

First, you increment the number by 1. If this number has no repeating digits, you are done. Else, you can follow the following algorithm.

(We look at the number as a string.)

Locate the first repeated digit.
Mark it as a "location to change" (change_at_location in the code).
At a location to change, increment the digit to the next highest "available" digit (i.e. a digit that is not repeated till that point in the number). [Note: Such a digit might not always be available, since all the higher digits might already be used.]
IF such a digit is available,
- Increment the digit at the location to change.
- After that location, look at all the available (i.e. unused up to that point) digits in the increasing order, and insert them one by one.
ELSE
- Move the location to change back by 1

Note: If location to change reaches -1, insert a dummy '0' at the start, and update the location to 0, and redo the whole thing.

Following are two snippets, one with the loop, the solution you don't want, but is simple to convince ourselves that it "works", and second without loop using the above algorithm.

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))

If you want to empirically convince yourself (as opposed to by following the logic),

You can do so as follows,

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)

The list bad remains empty thereby "proving" the correctness.

Word of caution, however, that this loop will take a long long time to run, since the loop-y way is actually quite inefficient as can be seen by the following comparison,

%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

So the non-loop variant is actually much faster, thereby also justifying the need for looking for such variant beyond purely academic curiosity.

Note 1: This function does not care for the restriction of "no repeated digits in the original number" or "only one set of repeated digits" etc, given any number it will find the next non-repeating number whenever possible.

Note 2: Code can be cleaned up etc a bit. It is written so purposefully to make it easy to follow the thought process.

Mimic Permutations Counter

Answers (2)

Related Questions