Contar números naturales cuyas permutaciones sean mayores que ese número

Hay algún número natural cuya permutación total es mayor o igual a ese número, por ejemplo. 123, cuyas permutaciones (123, 231, 321) son mayores o iguales a 123. 
Dado un número natural n , la tarea es contar todos esos números de 1 a n. 

Ejemplos: 

Entrada: n = 15.
Salida: 14

Explicación:
1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 
13, 14, 15 son los números cuya 
permutación total es mayor que el número
mismo. Entonces, salida 14.

Entrada: n = 100.
Salida: 54

Una solución simple es ejecutar un ciclo de 1 a n y para cada número verificar si sus dígitos están en orden no decreciente o no.

Una solución eficiente se basa en las siguientes observaciones.

• Observación 1: Del 1 al 9, todos los números tienen esta propiedad. Entonces, para n <= 9, genera n. 
• Observación 2: El número cuya permutación es mayor o igual a ese número tiene todos sus dígitos en orden creciente.

La idea es empujar todos los números del 1 al 9. Ahora, saque el elemento superior, diga topel e intente hacer un número cuyos dígitos estén en orden creciente y el primer dígito sea topel . Para hacer tales números, el segundo dígito puede ser de topel%10 a 9. Si este número es menor que n , incremente el conteo y empuje el número en la pila, de lo contrario, ignórelo.

A continuación se muestra la implementación de este enfoque: 

// C++ program to count the number less than N,
// whose all permutation is greater
// than or equal to the number.
#include <bits/stdc++.h>
using namespace std;
 
// Return the count of the number having all
// permutation greater than or equal to the number.
int countNumber(int n)
{
    int result = 0;
 
    // Pushing 1 to 9 because all number from 1
    // to 9 have this property.
    stack<int> s;
    for (int i = 1; i <= 9; i++)
    {
         
        if (i <= n)
        {
            s.push(i);
            result++;
        }
 
        // take a number from stack and add
        // a digit smaller than or equal to last digit
        // of it.
        while (!s.empty())
        {
            int tp = s.top();
            s.pop();
            for (int j = tp % 10; j <= 9; j++)
            {
                int x = tp * 10 + j;
                if (x <= n)
                {
                    s.push(x);
                    result++;
                }
            }
        }
    }
 
    return result;
}
 
// Driven Code
int main()
{
    int n = 15;
    cout << countNumber(n) << endl;
    return 0;
}

// Java program to count the number less than N,
// whose all permutation is greater
// than or equal to the number.
import java.util.Stack;
 
 
class GFG
{
    // Return the count of the number having all
    // permutation greater than or equal to the number.
 
    static int countNumber(int n)
    {
        int result = 0;
 
        // Pushing 1 to 9 because all number from 1
        // to 9 have this property.
        Stack<Integer> s = new Stack<>();
        for (int i = 1; i <= 9; i++)
        {
 
            if (i <= n)
            {
                s.push(i);
                result++;
            }
 
            // take a number from stack and add
            // a digit smaller than or equal to last digit
            // of it.
            while (!s.empty())
            {
                int tp = s.pop();
                
                for (int j = tp % 10; j <= 9; j++)
                {
                    int x = tp * 10 + j;
                    if (x <= n) {
                        s.push(x);
                        result++;
                    }
                }
            }
        }
 
        return result;
    }
 
    // Driven Code
    public static void main(String[] args)
    {
        int n = 15;
        System.out.println(countNumber(n));
    }
}
 
// this code contributed by Rajput-Ji

# Python3 program to count the number less
# than N, whose all permutation is greater
# than or equal to the number.
 
# Return the count of the number having
# all permutation greater than or equal
# to the number.
 
 
def countNumber(n):
    result = 0
 
    # Pushing 1 to 9 because all number
    # from 1 to 9 have this property.
    s = []
    for i in range(1, 10):
         
        if (i <= n):
            s.append(i)
            result += 1
 
        # take a number from stack and add
        # a digit smaller than or equal to last digit
        # of it.
        while len(s) != 0:
            tp = s[-1]
            s.pop()
            for j in range(tp % 10, 10):
                x = tp * 10 + j
                if (x <= n):
                    s.append(x)
                    result += 1
 
    return result
 
 
# Driver Code
if __name__ == '__main__':
 
    n = 15
    print(countNumber(n))
 
# This code is contributed by PranchalK

// C# program to count the number less than N,
// whose all permutation is greater than
// or equal to the number.
using System;
using System.Collections.Generic;
 
class GFG {
 
    // Return the count of the number
    // having all permutation greater than
    // or equal to the number.
    static int countNumber(int n)
    {
        int result = 0;
 
        // Pushing 1 to 9 because all number from 1
        // to 9 have this property.
        Stack<int> s = new Stack<int>();
        for (int i = 1; i <= 9; i++)
        {
             
            if (i <= n)
            {
                s.Push(i);
                result++;
            }
 
            // take a number from stack and add
            // a digit smaller than or equal to last digit
            // of it.
            while (s.Count != 0)
            {
                int tp = s.Peek();
                s.Pop();
                for (int j = tp % 10; j <= 9; j++)
                {
                    int x = tp * 10 + j;
                    if (x <= n) {
                        s.Push(x);
                        result++;
                    }
                }
            }
        }
 
        return result;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int n = 15;
        Console.WriteLine(countNumber(n));
    }
}
 
// This code is contributed by Rajput-Ji

  <script>
 
        // JavaScript program for the above approach
 
        // Return the count of the number having all
        // permutation greater than or equal to the number.
        function countNumber(n)
        {
            let result = 0;
 
            // Pushing 1 to 9 because all number from 1
            // to 9 have this property.
            let s = [];
            for (let i = 1; i <= 9; i++)
            {
 
                if (i <= n)
                {
                    s.push(i);
                    result++;
                }
 
                // take a number from stack and add
                // a digit smaller than or equal to last digit
                // of it.
                while (s.length != 0)
                {
                    let tp = s[s.length - 1];
                    s.pop();
                    for (let j = tp % 10; j <= 9; j++)
                    {
                        let x = tp * 10 + j;
                        if (x <= n)
                        {
                            s.push(x);
                            result++;
                        }
                    }
                }
            }
 
            return result;
        }
 
        // Driven Code
 
        let n = 15;
        document.write(countNumber(n));
 
// This code is contributed by Potta Lokesh
    </script>

14

Complejidad de tiempo: O(x) donde x es el número de elementos impresos en la salida.

Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.