Controllare se due numeri sono permutazione l'uno dell'altro?

Question

Dato due numeri a, b tale che 1 < = a, b < = 10000000000 (10^10). Il mio problema è di verificare se le cifre in esse sono permutazioni l'una dell'altra o no. Qual è il modo più veloce per farlo? Stavo pensando di usare l'hashing ma non riesco a trovare alcuna funzione di hash adatta. Eventuali suggerimenti?

Per es - 123 è una permutazione valida di 312

Anche io non voglio ordinare le cifre nei numeri.

Answer 1

Se si intende i caratteri dei numeri (come 1927 e 9721), ci sono (almeno) un paio di approcci.

Se ti è stato permesso di ordinare, un approccio è semplicemente quello di aggiungere sprintf a due buffer, ordinare i caratteri nei buffer, quindi verificare se le stringhe sono uguali.

Tuttavia, dato il tuo desiderio di non ordinare le cifre, un'altra alternativa è impostare un array di dieci elementi, con tutti gli elementi inizialmente impostati su zero, quindi elaborare ogni cifra nel primo numero, incrementando l'elemento pertinente .

Quindi fare lo stesso con il secondo numero ma decrementare.

Se, alla fine, sono ancora tutti zeri, i numeri erano una permutazione reciproca.

Ciò è efficiente in quanto è un algoritmo O(n) in cui n è il numero di cifre nei due numeri. Lo pseudo-codice per una bestia sarebbe qualcosa di simile:

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 

In C, il seguente programma completo illustra come questo può essere fatto:

#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; 
} 

Semplicemente passare due numeri (positivi) e, supponendo che si adattino a un long, ti dirà se hanno lo stesso numero di cifre.

Answer 2

È compito?

Calcola il numero di aspetti di ciascuna cifra e confrontali, se sono uguali, un numero può essere convertito in altro utilizzando la permutazione.

Answer 3

creare una matrice:

int digitOccurances[2][10]; 

Nel digitOccruances[X][N] negozio il numero di volte che la cifra N appare nel numero X. Quindi, se di comparare 8.675.309-9.568.733, l'array finirebbe per assomigliare:

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

Se i due array sono uguali, allora i numeri sono permutazioni.

Questo è un algoritmo O (n), in modo asintoticamente parlando questo è il più efficiente che sta per arrivare (non è possibile risolvere questo problema senza esaminare tutte le cifre, almeno una volta.

si può immediatamente restituisce false se i numeri hanno lunghezze diverse, quindi presume che entrambi siano di lunghezza n. Prenderanno 2n operazioni per riempire l'array e quindi esattamente 10 confronti per leggere l'array. 2n + 10 è O (n)

Answer 4

a e b sono anagrammi se hanno lo stesso numero di ciascuna cifra, quindi in pratica il modo più veloce sembra essere, contando le cifre per aeb:

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

Beh, se si può costruire una tabella di 80GB, si può sempre fare:

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

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

Answer 6

{A cura di aggiungere ulteriore test)

Dando per scontato che nel dominio di cifre, come su

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

Answer 7

Se quello che ho capito dalla tua domanda correttamente una permutazione è una combinazione degli elementi, che non si ripetono. Quindi se 123 è una permutazione valida di 312 allora lo fa anche

123, 
213, 
132, 
321, 
213, 

e così via.

Quindi, in base a questa ipotesi, diciamo che hai due numeri interi 123456789 e 129837456. (Per semplicità, suppongo anche che entrambi i numeri abbiano la stessa lunghezza). Se hai compreso il punto, potresti essere in grado di verificare anche permutazioni e combinazioni diverse.

per che tutto quello che dovete fare è quello di ottenere i numeri interi di unità rispetto al numero dato, ad esempio:

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) 

ho letteralmente dato accenno algoritmico di come per farlo, questo può essere fatto facilmente. Una volta fatto si finirà con interi separati (meglio salvare questi valori in un array)

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

Ora

fare lo stesso per l'altro dato intero in modo da finire con un altro array di interi

quindi ora tutto ciò che è necessario controllare è che se tutti gli interi del secondo array sono presenti nel primo array di numeri interi, se sì, allora sono una permutazione degli interi del primo array o del primo numero .

Spero che questo aiuti.

Answer 8

Ho trovato questa soluzione piuttosto efficiente su rossetacode.org. Spero che mi perdonerai per averlo scritto in Java (non mi sento a mio agio con C) ma la sintassi dovrebbe essere più o meno la stessa.

Il codice prima controlla se i numeri hanno lo stesso numero di cifre, quindi riassume le cifre per bit spostandole in un totale.Tranne che la distanza di spostamento è moltiplicata per un fattore 6. Ciò rende impossibile per le cifre più piccole comporre lo stesso valore di una cifra più grande. Ad esempio, un "9" richiederebbe 64 volte "8" per corrispondere al suo valore, il che ovviamente non è possibile.

Questo codice presuppone input non negativi.

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

Non certo perché non si desidera ordinare, a meno che quella era una condizione per l'assegnazione di compiti a casa. Per chiunque inciampare su questa questione solo in cerca di il modo più veloce (! E la maggior parte divinatorio) per verificare se due interi sono permutazioni in Python:

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

Questa soluzione è leggermente più veloce in Python, affidandosi, naturalmente, sui numeri testati per essere interi relativamente piccoli. Funziona abbastanza bene per il problema di Project Euler 52.