Encuentra el siguiente número mayor con el mismo conjunto de dígitos

Dado un número n, encuentre el número más pequeño que tenga el mismo conjunto de dígitos que n y sea mayor que n. Si n es el mayor número posible con su conjunto de dígitos, imprima «no es posible».

Ejemplos: 
Para simplificar la implementación, hemos considerado el número de entrada como una string. 

Input:  n = "218765"
Output: "251678"

Input:  n = "1234"
Output: "1243"

Input: n = "4321"
Output: "Not Possible"

Input: n = "534976"
Output: "536479"

A continuación se presentan algunas observaciones sobre el siguiente número mayor. 

1. Si todos los dígitos están ordenados en orden descendente, la salida siempre es «No posible». Por ejemplo, 4321. 
2. Si todos los dígitos están ordenados en orden ascendente, entonces necesitamos intercambiar los dos últimos dígitos. Por ejemplo, 1234. 
3. Para otros casos, necesitamos procesar el número del lado derecho (¿por qué? Porque necesitamos encontrar el menor de todos los números mayores)

Ahora puede intentar desarrollar un algoritmo usted mismo. 

El siguiente es el algoritmo para encontrar el siguiente número mayor. 

1. Recorra el número dado desde el dígito más a la derecha, siga recorriendo hasta que encuentre un dígito que sea más pequeño que el dígito recorrido anteriormente. Por ejemplo, si el número de entrada es «534976», nos detenemos en 4 porque 4 es más pequeño que el siguiente dígito 9. Si no encontramos ese dígito, la salida es «No posible».
2. Ahora busque en el lado derecho del dígito anterior ‘d’ el dígito más pequeño mayor que ‘d’. Para “53 4 976″, el lado derecho de 4 contiene “976”. El dígito más pequeño mayor que 4 es 6 .
3. Intercambie los dos dígitos encontrados arriba, obtenemos 53 6 97 4 en el ejemplo anterior.
4. Ahora ordene todos los dígitos desde la posición junto a ‘d’ hasta el final del número. El número que obtenemos después de ordenar es la salida. Para el ejemplo anterior, ordenamos los dígitos en negrita 536 974 . Obtenemos «536 479 «, que es el siguiente número mayor para la entrada 534976.

A continuación se muestra la implementación del enfoque anterior. 

// C++ program to find the smallest number which greater than a given number
// and has same set of digits as given number
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
// Utility function to swap two digits
void swap(char *a, char *b)
{
    char temp = *a;
    *a = *b;
    *b = temp;
}
 
// Given a number as a char array number[], this function finds the
// next greater number.  It modifies the same array to store the result
void findNext(char number[], int n)
{
    int i, j;
 
    // I) Start from the right most digit and find the first digit that is
    // smaller than the digit next to it.
    for (i = n-1; i > 0; i--)
        if (number[i] > number[i-1])
           break;
 
    // If no such digit is found, then all digits are in descending order
    // means there cannot be a greater number with same set of digits
    if (i==0)
    {
        cout << "Next number is not possible";
        return;
    }
 
    // II) Find the smallest digit on right side of (i-1)'th digit that is
    // greater than number[i-1]
    int x = number[i-1], smallest = i;
    for (j = i+1; j < n; j++)
        if (number[j] > x && number[j] < number[smallest])
            smallest = j;
 
    // III) Swap the above found smallest digit with number[i-1]
    swap(&number[smallest], &number[i-1]);
 
    // IV) Sort the digits after (i-1) in ascending order
    sort(number + i, number + n);
 
    cout << "Next number with same set of digits is " << number;
 
    return;
}
 
// Driver program to test above function
int main()
{
    char digits[] = "534976";
    int n = strlen(digits);
    findNext(digits, n);
    return 0;
}

// Java program to find next greater
// number with same set of digits.
import java.util.Arrays;
 
public class nextGreater
{
    // Utility function to swap two digit
    static void swap(char ar[], int i, int j)
    {
        char temp = ar[i];
        ar[i] = ar[j];
        ar[j] = temp;
    }
 
    // Given a number as a char array number[],
    // this function finds the next greater number.
    // It modifies the same array to store the result
    static void findNext(char ar[], int n)
    {
        int i;
         
        // I) Start from the right most digit
        // and find the first digit that is smaller
        // than the digit next to it.
        for (i = n - 1; i > 0; i--)
        {
            if (ar[i] > ar[i - 1]) {
                break;
            }
        }
         
        // If no such digit is found, then all
        // digits are in descending order means
        // there cannot be a greater number with
        // same set of digits
        if (i == 0)
        {
            System.out.println("Not possible");
        }
        else
        {
            int x = ar[i - 1], min = i;
             
            // II) Find the smallest digit on right
            // side of (i-1)'th digit that is greater
            // than number[i-1]
            for (int j = i + 1; j < n; j++)
            {
                if (ar[j] > x && ar[j] < ar[min])
                {
                    min = j;
                }
            }
 
            // III) Swap the above found smallest
            // digit with number[i-1]
            swap(ar, i - 1, min);
 
            // IV) Sort the digits after (i-1)
            // in ascending order
            Arrays.sort(ar, i, n);
            System.out.print("Next number with same" +
                                    " set of digits is ");
            for (i = 0; i < n; i++)
                System.out.print(ar[i]);
        }
    }
 
    public static void main(String[] args)
    {
        char digits[] = { '5','3','4','9','7','6' };
        int n = digits.length;
        findNext(digits, n);
    }
}

# Python program to find the smallest number which
# is greater than a given no. has same set of
# digits as given number
 
# Given number as int array, this function finds the
# greatest number and returns the number as integer
def findNext(number,n):
      
     # Start from the right most digit and find the first
     # digit that is smaller than the digit next to it
     for i in range(n-1,0,-1):
         if number[i] > number[i-1]:
             break
              
     # If no such digit found,then all numbers are in
     # descending order, no greater number is possible
     if i == 1 and number[i] <= number[i-1]:
         print ("Next number not possible")
         return
          
     # Find the smallest digit on the right side of
     # (i-1)'th digit that is greater than number[i-1]
     x = number[i-1]
     smallest = i
     for j in range(i+1,n):
         if number[j] > x and number[j] < number[smallest]:
             smallest = j
          
     # Swapping the above found smallest digit with (i-1)'th
     number[smallest],number[i-1] = number[i-1], number[smallest]
      
     # X is the final number, in integer datatype
     x = 0
     # Converting list upto i-1 into number
     for j in range(i):
         x = x * 10 + number[j]
      
     # Sort the digits after i-1 in ascending order
     number = sorted(number[i:])
     # converting the remaining sorted digits into number
     for j in range(n-i):
         x = x * 10 + number[j]
      
     print ("Next number with set of digits is",x)
 
 
# Driver Program to test above function
digits = "534976"        
 
# converting into integer array,
# number becomes [5,3,4,9,7,6]
number = list(map(int ,digits))
findNext(number, len(digits))
 
# This code is contributed by Harshit Agrawal

// C# program to find next greater
// number with same set of digits.
using System;
                     
public class nextGreater
{
    // Utility function to swap two digit
    static void swap(char []ar, int i, int j)
    {
        char temp = ar[i];
        ar[i] = ar[j];
        ar[j] = temp;
    }
 
    // Given a number as a char array number[],
    // this function finds the next greater number.
    // It modifies the same array to store the result
    static void findNext(char []ar, int n)
    {
        int i;
         
        // I) Start from the right most digit
        // and find the first digit that is smaller
        // than the digit next to it.
        for (i = n - 1; i > 0; i--)
        {
            if (ar[i] > ar[i - 1])
            {
                break;
            }
        }
         
        // If no such digit is found, then all
        // digits are in descending order means
        // there cannot be a greater number with
        // same set of digits
        if (i == 0)
        {
            Console.WriteLine("Not possible");
        }
        else
        {
            int x = ar[i - 1], min = i;
             
            // II) Find the smallest digit on right
            // side of (i-1)'th digit that is greater
            // than number[i-1]
            for (int j = i + 1; j < n; j++)
            {
                if (ar[j] > x && ar[j] < ar[min])
                {
                    min = j;
                }
            }
 
            // III) Swap the above found smallest
            // digit with number[i-1]
            swap(ar, i - 1, min);
 
            // IV) Sort the digits after (i-1)
            // in ascending order
            Array.Sort(ar, i, n-i);
            Console.Write("Next number with same" +
                                    " set of digits is ");
            for (i = 0; i < n; i++)
                Console.Write(ar[i]);
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        char []digits = { '5','3','4','9','7','6' };
        int n = digits.Length;
        findNext(digits, n);
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program to find the
// smallest number which is greater
// than a given no. has same set of
// digits as given number
 
// Given number as int array, this
// function finds the greatest number
// and returns the number as integer
function findNext(number, n)
{
     
    // Start from the right most digit
    // and find the first digit that is
    // smaller than the digit next to it
    for(var i = n - 1; i >= 0; i--)
    {
        if (number[i] > number[i - 1])
            break;
    }
     
    // If no such digit found,then all
    // numbers are in descending order,
    // no greater number is possible
    if (i == 1 && number[i] <= number[i - 1])
    {
        document.write("Next number not possible");
        return;
    }  
     
    // Find the smallest digit on the
    // right side of (i-1)'th digit
    // that is greater than number[i-1]
    let x = number[i - 1];
    let smallest = i;
     
    for(let j = i + 1; j < n; j++)
    {
        if (number[j] > x &&
            number[j] < number[smallest])
        smallest = j;
    }
     
    // Swapping the above found smallest
    // digit with (i-1)'th
    let temp = number[smallest];
    number[smallest] = number[i - 1];
    number[i - 1] = temp;
     
    // X is the final number, in integer datatype
    x = 0
     
    // Converting list upto i-1 into number
    for(let j = 0; j < i; j++)
        x = x * 10 + number[j];
     
    // Sort the digits after i-1 in ascending order
    number = number.slice(i, number.length + 1);
    number.sort()
     
    // Converting the remaining sorted
    // digits into number
    for(let j = 0; j < n - i; j++)
        x = x * 10 + number[j];
     
    document.write("Next number with " +
                   "set of digits is " + x);
}
 
// Driver code
let digits = "534976"      
 
// Converting into integer array,
// number becomes [5,3,4,9,7,6]
let number = []
for(let i = 0; i < digits.length; i++)
    number[i] = Number(digits[i]);
 
findNext(number, digits.length);
 
// This code is contributed by rohan07
 
</script>

Next number with same set of digits is 536479

Complejidad de tiempo: O(N*logN) Espacio auxiliar: O(1) 

La implementación anterior se puede optimizar de las siguientes maneras. 

1. Podemos usar la búsqueda binaria en el paso II en lugar de la búsqueda lineal. 
2. En el paso IV, en lugar de hacer una clasificación simple, podemos aplicar alguna técnica inteligente para hacerlo en tiempo lineal. Sugerencia: sabemos que todos los dígitos se ordenan linealmente en orden inverso, excepto un dígito que se intercambió.

Con las optimizaciones anteriores, podemos decir que la complejidad temporal de este método es O(n). 

Enfoque optimizado:

1. Aquí, en lugar de ordenar los dígitos después del índice (i-1), estamos invirtiendo los dígitos como se menciona en el punto de optimización anterior.
2. Como estarán en orden decreciente, para encontrar el elemento más pequeño posible de la parte correcta, simplemente los invertimos, reduciendo así la complejidad del tiempo.

A continuación se muestra la implementación del enfoque anterior:

#include <bits/stdc++.h>
using namespace std;
 
vector<int> nextPermutation(int n, vector<int> arr)
{
    // If number of digits is 1 then just return the vector
    if (n == 1)
        return arr;
 
    // Start from the right most digit and find the first
    // digit that is
    // smaller than the digit next to it.
    int i = 0;
    for (i = n - 1; i > 0; i--) {
        if (arr[i] > arr[i - 1])
            break;
    }
 
    // If there is a possibility of a next greater element
    if (i != 0) {
        // Find the smallest digit on right side of (i-1)'th
        // digit that is
        // greater than number[i-1]
        for (int j = n - 1; j >= i; j--) {
            if (arr[i - 1] < arr[j]) {
                // Swap the found smallest digit i.e. arr[j]
                // with arr[i-1]
                swap(arr[i - 1], arr[j]);
                break;
            }
        }
    }
 
    // Reverse the digits after (i-1) because the digits
    // after (i-1) are in decreasing order and thus we will
    // get the smallest element possible from these digits
    reverse(arr.begin() + i, arr.end());
 
    // If i is 0 that means elements are in decreasing order
    // Therefore, no greater element possible then we just
    // return the lowest possible
    // order/element formed from these digits by just
    // reversing the vector
 
    return arr;
}
 
int main()
{
    int n = 6;
    vector<int> v{ 5,3,4,9,7,6 };
    vector<int> res;
    res = nextPermutation(n, v);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
  static int[] nextPermutation(int n, int[] arr)
  {
 
    // If number of digits is 1 then just return the vector
    if (n == 1)
      return arr;
 
    // Start from the right most digit and find the first
    // digit that is
    // smaller than the digit next to it.
    int i = 0;
    for (i = n - 1; i > 0; i--) {
      if (arr[i] > arr[i - 1])
        break;
    }
 
    // If there is a possibility of a next greater element
    if (i != 0)
    {
 
      // Find the smallest digit on right side of (i-1)'th
      // digit that is
      // greater than number[i-1]
      for (int j = n - 1; j >= i; j--)
      {
        if (arr[i - 1] < arr[j])
        {
 
          // Swap the found smallest digit i.e. arr[j]
          // with arr[i-1]
          int temp = arr[j];
          arr[j] = arr[i - 1];
          arr[i - 1] = temp;
          break;
        }
      }
    }
 
    // Reverse the digits after (i-1) because the digits
    // after (i-1) are in decreasing order and thus we will
    // get the smallest element possible from these digits
    int[] res = new int[arr.length];
    int ind = arr.length - 1;
 
    // copying the first i elements of arr
    // into res
    for (int j = 0; j < i; j++)
      res[j] = arr[j];
 
    // copying the rest of the elements
    // in reverse order
    for (int j = i; j< res.length; j++)
      res[j] = arr[ind--];
 
    // If i is 0 that means elements are in decreasing order
    // Therefore, no greater element possible then we just
    // return the lowest possible
    // order/element formed from these digits by just
    // reversing the vector
    return res;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int n = 6;
    int[] v = { 5,3,4,9,7,6 };
    int[] res;
 
    // Function Call
    res = nextPermutation(n, v);
    for (int i = 0; i < res.length; i++) {
      System.out.print(res[i] + " ");
    }
  }
}
 
// This code is contributed by phasing17

# A python program to find the next greatest number
def nextPermutation(arr):
   
      # find the length of the array
    n = len(arr)
     
    # start from the right most digit and find the first
    # digit that is smaller than the digit next to it.
    k = n - 2
    while k >= 0:
        if arr[k] < arr[k + 1]:
            break
        k -= 1
         
    # reverse the list if the digit that is smaller than the
    # digit next to it is not found.
    if k < 0:
        arr = arr[::-1]
    else:
       
          # find the first greatest element than arr[k] from the
        # end of the list
        for l in range(n - 1, k, -1):
            if arr[l] > arr[k]:
                break
 
        # swap the elements at arr[k] and arr[l     
        arr[l], arr[k] = arr[k], arr[l]
         
        # reverse the list from k + 1 to the end to find the
        # most nearest greater number to the given input number
        arr[k + 1:] = reversed(arr[k + 1:])
 
    return arr
 
# Driver code
arr = [5, 3, 4, 9, 7, 6]
print(*nextPermutation(arr))
 
# This code is contributed by Manish Thapa

// C# implementation of the approach
using System;
class GFG {
  static int[] nextPermutation(int n, int[] arr)
  {
 
    // If number of digits is 1 then just return the
    // vector
    if (n == 1)
      return arr;
 
    // Start from the right most digit and find the
    // first digit that is smaller than the digit next
    // to it.
    int i = 0;
    for (i = n - 1; i > 0; i--) {
      if (arr[i] > arr[i - 1])
        break;
    }
 
    // If there is a possibility of a next greater
    // element
    if (i != 0) {
 
      // Find the smallest digit on right side of
      // (i-1)'th digit that is greater than
      // number[i-1]
      for (int j = n - 1; j >= i; j--) {
        if (arr[i - 1] < arr[j]) {
 
          // Swap the found smallest digit i.e.
          // arr[j] with arr[i-1]
          int temp = arr[j];
          arr[j] = arr[i - 1];
          arr[i - 1] = temp;
          break;
        }
      }
    }
 
    // Reverse the digits after (i-1) because the digits
    // after (i-1) are in decreasing order and thus we
    // will get the smallest element possible from these
    // digits
    int[] res = new int[arr.Length];
    int ind = arr.Length - 1;
 
    // copying the first i elements of arr
    // into res
    for (int j = 0; j < i; j++)
      res[j] = arr[j];
 
    // copying the rest of the elements
    // in reverse order
    for (int j = i; j < res.Length; j++)
      res[j] = arr[ind--];
 
    // If i is 0 that means elements are in decreasing
    // order Therefore, no greater element possible then
    // we just return the lowest possible order/element
    // formed from these digits by just reversing the
    // vector
    return res;
  }
 
  // Driver Code
  public static int Main()
  {
    int n = 6;
    int[] v = new int[] { 5, 3, 4, 9, 7, 6 };
    int[] res;
 
    // Function Call
    res = nextPermutation(n, v);
    for (int i = 0; i < res.Length; i++) {
      Console.Write(res[i] + " ");
    }
    return 0;
  }
}
 
// This code is contributed by Taranpreet

<script>
 
function nextPermutation(n, arr)
{
    // If number of digits is 1 then just return the vector
    if (n == 1)
        return arr;
  
    // Start from the right most digit and find the first
    // digit that is
    // smaller than the digit next to it.
    let i = 0;
    for (i = n - 1; i > 0; i--) {
        if (arr[i] > arr[i - 1])
            break;
    }
  
    // If there is a possibility of a next greater element
    if (i != 0)
    {
     
        // Find the smallest digit on right side of (i-1)'th
        // digit that is
        // greater than number[i-1]
        for (let j = n - 1; j >= i; j--)
        {
            if (arr[i - 1] < arr[j])
            {
                // Swap the found smallest digit i.e. arr[j]
                // with arr[i-1]
                 
                let temp = arr[i - 1];
                arr[i - 1] = arr[j];
                arr[j] = temp;
                break;
            }
        }
    }
  
    // Reverse the digits after (i-1) because the digits
    // after (i-1) are in decreasing order and thus we will
    // get the smallest element possible from these digits
    arr = arr.slice(0,i).concat(arr.slice(i,arr.length).reverse());
  
    // If i is 0 that means elements are in decreasing order
    // Therefore, no greater element possible then we just
    // return the lowest possible
    // order/element formed from these digits by just
    // reversing the vector
    return arr;
}
 
let v = [5,3,4,9,7,6];
let n = 6;
let res = nextPermutation(n, v);
for (let i = 0; i < res.length; i++) {
    document.write(res[i] + " ")
}
 
// This code is contributed by avanitrachhadiya2155
</script>

5 3 6 4 7 9 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)