[algorithm] 숫자가 주어지면 원래 숫자와 정확히 같은 자릿수가있는 다음 높은 숫자를 찾으십시오.

다음 과 같이 (자릿수는 O(n)어디에 있습니까? n)

오른쪽부터 시작하여 왼쪽 숫자가 오른쪽 숫자보다 작도록 첫 번째 숫자 쌍을 찾습니다. “digit-x”로 왼쪽 숫자를 참조합시다. digit-x의 오른쪽에있는 digit-x보다 작은 숫자를 찾아 digit-x의 바로 왼쪽에 배치하십시오. 마지막으로 남은 자릿수는 오름차순으로 정렬합니다. 이미 내림차순 이므로 숫자를 뒤집기 만하면됩니다 (digit-x의 올바른 위치에 배치 할 수 있음 O(n)) .

예를 들어 이것을 더 명확하게 만들 수 있습니다.

123456784987654321
숫자로 시작하다

123456784 987654321
         ^ 왼쪽 숫자가 오른쪽보다 작은 오른쪽에서 첫 번째 위치
         숫자 "x"는 4

123456784 987654321
              ^ 오른쪽으로 4보다 큰 가장 작은 숫자를 찾습니다.

123456785 4 98764321
        ^ 4의 왼쪽에 놓으십시오

123456785 4 12346789
123456785123446789
         ^ 5의 오른쪽으로 숫자를 정렬합니다.
         '4'는 이미 내림차순입니다. 우리가해야 할 일은
         순서를 바꾸고 '4'에 대한 올바른 장소를 찾으십시오.

정확성 증명 :

대문자를 사용하여 숫자 문자열과 숫자의 소문자를 정의합시다. 구문 AB수단 “문자열 연결 A및 B“ . <lexicographical ordering은 자릿수 문자열의 길이가 동일한 경우 정수 순서와 동일합니다.

우리의 원래 숫자 N의 형식은 AxB, x한 자리이며, B정렬 내림차순입니다.
알고리즘에서 찾은 숫자는 가장 작은 자릿수 (AyC 여기서 선택한 방식 으로 존재해야 함 , 위 참조) 이며 오름차순으로 정렬됩니다.y ∈ B> x xC

같은 숫자를 사용하는 숫자가 있다고 가정 N'합니다 AxB < N' < AyC. N'로 시작 A하거나 그렇지 않으면 그들 사이에 빠질 수 없으므로 양식으로 작성할 수 있습니다 AzD. 이제 우리의 불평등은입니다 AxB < AzD < AyC. xB < zD < yC세 자리 문자열이 모두 같은 자리를 포함하는 것과 같습니다.

그것이 사실이 되려면, 우리는 반드시 있어야합니다 x <= z <= y. 때문에 y작은 숫자입니다 > x, z그래서 하나, 그들 사이가 될 수 없습니다 z = x나 z = y. 말해봐 z = x. 그리고 우리의 불평등은 xB < xD < yC의미하는 B < D곳 모두 B와 D같은 자리가 있습니다. 그러나 B는 내림차순으로 정렬되므로 해당 자릿수보다 큰 문자열 은 없습니다. 따라서 우리는 가질 수 없습니다 B < D. 동일한 단계를 수행하면을 z = y가질 수 없다는 것을 알 수 있습니다 D < C.

따라서 N'존재할 수 없으므로 알고리즘이 다음으로 큰 숫자를 올바르게 찾습니다.

답변

34722641

34722 641

3472(2) 641

3472(2) 6(4)1

3472(2) 6(4)1
->
3472(4) 6(2)1
->
34724 621

34724 126

34724126

def findnext(ii): return min(v for v in (int("".join(x)) for x in
    itertools.permutations(str(ii))) if v>ii)

def findnext(ii):
    iis=list(map(int,str(ii)))
    for i in reversed(range(len(iis))):
        if i == 0: return ii
        if iis[i] > iis[i-1] :
            break
    left,right=iis[:i],iis[i:]
    for k in reversed(range(len(right))):
        if right[k]>left[-1]:
           right[k],left[-1]=left[-1],right[k]
           break
    return int("".join(map(str,(left+sorted(right)))))

function foo(num){
 sortOld = num.toString().split("").sort().join('');
 do{
    num++;
   sortNew = num.toString().split("").sort().join('');
 }while(sortNew!==sortOld);
 return num;
}

1234675
    ^

1234756

local number = 564321;

function split(str)
    local t = {};
    for i = 1, string.len(str) do
        table.insert(t, str.sub(str,i,i));
    end
    return t;
end

local res = number;
local i = 1;
while number >= res do
    local t = split(tostring(res));
    if i == 1 then
        i = #t;
    end
    t[i], t[i-1] = t[i-1], t[i];
    i = i - 1;
    res = tonumber(table.concat(t));
end

print(res);