Sprawdzanie, czy dwie liczby są wzajemnie permutacyjne?

Question

Podano dwie liczby a, b takie, że 1 < = a, b < = 10000000000 (10^10). Moim problemem jest sprawdzenie, czy cyfry w nich są permutacyjne, czy nie. Jaki jest najszybszy sposób na zrobienie tego? Myślałem o używaniu hashowania, ale nie mogłem znaleźć żadnej odpowiedniej funkcji skrótu. Jakieś sugestie?

Na przykład - 123 jest prawidłowym permutacją 312

Również nie chcę, aby posortować cyfr w liczbie.

Answer 1

Jeśli chodzi o postacie liczb (takie jak 1927 i 9721), istnieje (przynajmniej) kilka podejść.

Jeśli pozwolono ci sortować, jednym podejściem jest po prostu sprintf je do dwóch buforów, posortuj znaki w buforach, a następnie sprawdź, czy łańcuchy są równe.

Jednak biorąc pod uwagę chęć nie rodzaju cyfr, inną alternatywą jest utworzenie tablicy dziesięciu elementów, ze wszystkimi elementami początkowo ustawionych na zero, a następnie przetworzyć każdą cyfrę w pierwszym szeregu, zwiększając danego elementu .

Następnie wykonaj to samo z drugą liczbą, ale zmniejszaj.

Jeśli na końcu nadal są wszystkie zera, liczby były wzajemną permutacją.

Jest to efektywny algorytm, ponieważ n to liczba cyfr w dwóch liczbach. Pseudo-kod dla takiego zwierzęcia byłoby coś takiego:

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 

W C, po kompletny program ilustruje, w jaki sposób można to zrobić:

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

Simply podaj dwie liczby (dodatnie) i, zakładając, że pasują one do long, powie Ci, czy mają taką samą liczbę cyfr.

Answer 2

Czy to praca domowa?

Oblicz liczbę występów każdej cyfry i porównaj je, jeśli są one takie same, wtedy jedna liczba może zostać przekonwertowana na inną przy użyciu permutacji.

Answer 3

Tworzenie tablicy:

int digitOccurances[2][10]; 

W digitOccruances[X][N] sklepie liczbę razy, że cyfra N pojawia się numer X. Więc jeśli były porównując 8675309 do 9568733, tablica będzie w końcu wygląda tak:

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

Jeśli dwie tablice są równe, to numery są permutacje.

Jest to algorytm O (n), więc asymptotycznie mówiąc jest to najbardziej efektywny to się dostać (nie można rozwiązać ten problem bez rozpatrywania wszystkie cyfry co najmniej raz.

można od razu return false, jeśli liczby mają różne długości, załóżmy, że obie mają długość n. Operacja 2n zajmie wypełnienie tablicy, a następnie dokładnie 10 porównań, aby odczytać tablicę 2n + 10 to O (n).

Answer 4

a i b są anagramami, jeśli mają taką samą liczbę każdej cyfry, więc wydaje się, że najszybszy sposób, licząc cyfry dla aib:

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

Dobrze, jeśli można zbudować tabelę 80GB, zawsze można zrobić:

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

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

Answer 6

{Edytowane dodać dodatkowy test)

Zakładając, że są w domenie cyfr, jak o

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

Answer 7

Jeśli to, co zrozumiałem z twojego pytania poprawnie, permutacja jest kombinacją elementów, które się nie powtarzają. Więc jeśli 123 jest poprawną permutacją 312, to tak samo jest

123, 
213, 
132, 
321, 
213, 

i tak dalej.

Więc na podstawie tego założenia powiedzmy, że masz dwie liczby całkowite 123456789 i 129837456. (Dla uproszczenia zakładam również, że obie liczby mają jednakową długość). Jeśli zrozumiałeś ten punkt, możesz również sprawdzić różne kombinacje i permutacje.

za to wszystko, co musisz zrobić, to aby uzyskać całkowite jednostek z danego numeru, np:

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

lub

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) 

mam dosłownie wam algorytmicznego podpowiedź jak Aby to zrobić, więc można to łatwo zrobić. raz zrobić skończy się z oddzielnych liczb całkowitych (lepiej zapisać te wartości w tablicy)

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

Teraz

zrobić to samo dla drugiej podanej liczby całkowitej tak skończy się z inną tablicę liczb całkowitych

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

więc teraz wszystko, co musisz sprawdzić, to to, że jeśli wszystkie liczby całkowite drugiej tablicy są obecne w pierwszej tablicy liczb całkowitych, jeśli tak, to są permutacją liczb całkowitych pierwszej tablicy lub pierwszej liczby .

Mam nadzieję, że to pomoże.

Answer 8

Znalazłem to dość skuteczne rozwiązanie na rossetacode.org. Mam nadzieję, że mi wybaczycie, że napisałem to w Javie (nie czuję się dobrze z C), ale składnia powinna być mniej więcej taka sama.

Kod najpierw sprawdza, czy liczby mają tę samą liczbę cyfr, a następnie sumuje cyfry po bitach zmieniając je w łączną.Z wyjątkiem tego, że odległość zmiany jest mnożona przez współczynnik 6. To sprawia, że ​​mniej cyfr nie może tworzyć tej samej wartości, co większa cyfra. Na przykład jeden "9" wymagałby 64 razy "8", aby dopasować jego wartość, co oczywiście nie jest możliwe.

Kod ten zakłada wejście nieujemną.

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

Nie wiem, dlaczego nie chcesz uporządkować, chyba że był to warunek odrabianie zadania. Dla każdego, potykając na to pytanie po prostu patrząc na najszybciej (! I najbardziej pythonic) sposób na sprawdzenie, czy dwie liczby są permutacje w Pythonie:

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

To rozwiązanie biegnie nieco szybciej w Pythonie, powołując się, oczywiście, na liczbach przetestowanych jako stosunkowo małe liczby całkowite. Działa to całkiem dobrze w przypadku problemu z projektem Eulera 52.