Comprobando si dos números son permutaciones entre sí?

Question

Dados dos números a, b tales que 1 < = a, b < = 10000000000 (10^10). Mi problema es verificar si los dígitos en ellos son permutación uno del otro o no. ¿Cuál es la forma más rápida de hacerlo? Se pensó en usar hash pero no en encontrar ninguna función hash adecuada. ¿Alguna sugerencia?

Para por ejemplo - 123 es una permutación válido de 312

Además no quiero ordenar los dígitos de los números.

Answer 1

Si se refiere a los caracteres de los números (como 1927 y 9721), hay (al menos) un par de enfoques.

Si se le permitió ordenar, un enfoque es simplemente sprintf en dos búfers, ordenar los caracteres en los búferes, luego ver si las cadenas son iguales.

Sin embargo, dada su deseo de no Ordenar los dígitos, otra alternativa es la creación de un conjunto de diez elementos, con todos los elementos establecidos inicialmente a cero, entonces el proceso cada dígito en el primer número, incrementando el elemento relevante .

Luego haga lo mismo con el segundo número pero decrementando.

Si, al final, sigue siendo todo ceros, los números eran una permutación entre sí.

Esto es eficiente ya que es un algoritmo O(n) donde n es el número de dígitos en los dos números. El pseudo-código para una bestia tan sería algo así como:

def arePermutations (num1, num2): 
    create array count, ten elements, all zero. 
    for each digit in num1: 
     increment count[digit] 
    for each digit in num2: 
     decrement count[digit] 
    for each item in count: 
     if item is non-zero: 
      return false 
    return true 

En C, el siguiente programa completo ilustra cómo se puede hacer esto:

#include <stdio.h> 
#include <stdlib.h> 

#define FALSE (1==0) 
#define TRUE (1==1) 

int hasSameDigits (long num1, long num2) { 
    int digits[10]; 
    int i; 

    for (i = 0; i < 10; i++)  // Init all counts to zero. 
     digits[i] = 0; 

    while (num1 != 0) {   // Process all digits. 
     digits[num1%10]++;  // Increment for least significant digit. 
     num1 /= 10;    // Get next digit in sequence. 
    } 

    while (num2 != 0) {   // Same for num2 except decrement. 
     digits[num2%10]--; 
     num2 /= 10; 
    } 

    for (i = 0; i < 10; i++) 
     if (digits[i] != 0)  // Any count different, not a permutation. 
      return FALSE; 

    return TRUE;     // All count identical, was a permutation. 
} 

 

int main (int c, char *v[]) { 
    long v1, v2; 

    if (c != 3) { 
     printf ("Usage: %s <number1> <number2>\n", v[0]); 
     return 1; 
    } 

    v1 = atol (v[1]); 
    v2 = atol (v[2]); 
    if (hasSameDigits (v1, v2)) { 
     printf ("%d and %d are permutations\n", v1, v2); 
    } else { 
     printf ("%d and %d are not permutations\n", v1, v2); 
    } 

    return 0; 
} 

Simplemente pase dos números (positivos) y, suponiendo que encajen en un long, le dirá si tienen el mismo número de dígitos.

Answer 2

¿Es la tarea?

Calcula el número de apariciones de cada dígito y compáralos, si son iguales, un número se puede convertir a otro utilizando la permutación.

Answer 3

crear una matriz:

int digitOccurances[2][10]; 

En digitOccruances[X][N] tienda el número de veces que el dígito N aparece en el número X. Así que si estás comparando 8675309 a 9568733, la matriz terminaría pareciéndose:

{ { 1, 0, 0, 1, 0, 1, 1, 1, 1, 1 } , { 0, 0, 0, 2, 0, 1, 1, 1, 1, 1 } } 

Si los dos conjuntos son iguales, entonces los números son permutaciones.

Este es un O (n) algoritmo, de manera asintótica hablando, esto es el más eficiente que va a conseguir (no se puede resolver este problema sin examinar todos los dígitos al menos una vez.

Puede inmediato devuelve falso si los números tienen diferentes longitudes, así que suponga que ambos son de longitud n. Se necesitarán 2n operaciones para llenar el conjunto, y luego exactamente 10 comparaciones para leer el conjunto. 2n + 10 es O (n).

Answer 4

ayb son anagramas si tienen el mismo número de cada dígito. Así que, básicamente, la manera más rápida parece ser, contando los dígitos para ayb:

int c[10]={0,0,0,0,0,0,0,0,0,0} 

while (a) { c[a%10]++; a/=10; } 
while (b) { c[b%10]--; b/=10; } 

int res=1; 
for (int i=0;i<10;i++) res &= c[i]==0; 
printf(res?"yes":"no"); 

Answer 5

bien si se puede construir una tabla de 80 GB, siempre se puede hacer:

int64 table[10000000000] = {0, blah blah..., 9999999999}; 

if (table[a] == table[b]) ... 

Answer 6

{Editado para añadir prueba adicional)

Suponiendo que usted está en el dominio de dígitos, ¿qué hay de

if 
(
    ('1'^'2'^'3' == '3'^'1'^'2') && 
    ('1' + '2' + '3' == '3' + '1' + '2') 
) 
{ 
    cout << "Yes\n"; 
} 
else 
{ 
    cout << "No\n"; 
} 

Answer 7

Si lo que entendí de su pregunta correctamente una permutación es una combinación de los elementos, que no se repiten. Así que si 123 es una permutación válido de 312 entonces también lo hace

123, 
213, 
132, 
321, 
213, 

y así sucesivamente.

Por lo tanto, basándonos en esta suposición digamos que tiene dos enteros 123456789 y 129837456. (Por simplicidad, también estoy asumiendo que ambos números tienen la misma longitud). Si entendiste el punto, entonces también podrías verificar diferentes combinaciones y permutaciones.

para que todo lo que necesita hacer es conseguir los números enteros de unidades con respecto al número dado, por ejemplo:

Number 123456789 is 
1 * 100000000 + 
2 * 10000000 + 
3 * 1000000 + 
4 * 100000 + 
5 * 10000  + 
6 * 1000  + 
7 * 100  + 
8 * 10  + 
9 

o

1 * power(10, 8) + 
2 * power(10, 7) + 
3 * power(10, 6) + 
4 * power(10, 5) + 
5 * power(10, 4) + 
6 * power(10, 3) + 
7 * power(10, 2) + 
8 * power(10, 1) + 
9 * power(10, 0) 

i, literalmente, le he dado indicio algorítmica de cómo hacer eso para que esto pueda hacerse fácilmente. una vez hecho esto se va a terminar con números enteros separados (mejor guardar estos valores en una matriz)

1, 2, 3, 4, 5, 6, 7, 8, 9 

Ahora

hacer lo mismo para el otro entero dado para que el resultado final será con otra matriz de enteros

ahora todo lo que necesita comprobar es que si todos los enteros de la segunda matriz están presentes en la primera matriz de enteros, si es así, son una permutación de los enteros de la primera matriz o el primer número .

Espero que esto ayude.

Answer 8

He encontrado esta solución bastante eficiente en rossetacode.org. Espero que me perdones por escribirlo en Java (no me siento cómodo con C) pero la sintaxis debería ser más o menos la misma.

El código primero verifica si los números tienen el mismo número de dígitos, luego suma los dígitos por bit y los convierte en un total.Excepto que la distancia de desplazamiento se multiplica por un factor 6. Esto hace imposible que los dígitos más pequeños compongan el mismo valor que un dígito más grande. Por ejemplo, un '9' requeriría 64 veces '8' para coincidir con su valor, lo que obviamente no es posible.

Este código asume una entrada no negativa.

boolean haveSameDigits(long n1, long n2) { 
    long nn1 = n1, nn2 = n2; 
    while (nn1 > 0 && nn2 > 0) { 
     nn1 /= 10; 
     nn2 /= 10; 
    } 
    if (nn2 != nn1) // not the same length 
     return false; 

    long total1 = 0, total2 = 0; 
    while (n1 != 0) { 
     total1 += 1L << ((n1 % 10) * 6); 
     total2 += 1L << ((n2 % 10) * 6); 
     n1 /= 10; 
     n2 /= 10; 
    } 
    return total1 == total2; 
} 

Answer 9

No estoy seguro de por qué no desea ordenar, a menos que sea una condición de su tarea. Para cualquiera de tropezar sobre esta cuestión sólo en busca de la manera más rápida (! Y lo más Pythonic) para probar si dos números enteros son permutaciones en Python:

def arePermutations(a, b): 
    return sorted([d for d in str(a)]) == sorted([d for d in str(b)]) 

Esta solución se ejecuta un poco más rápido en Python, dependiendo, por supuesto, en los números probados para ser enteros relativamente pequeños. Funciona bastante bien para el problema 52 de Project Euler.