Проверка того, являются ли две цифры перестановкой друг друга?

Question

Для двух чисел a, b таких, что 1 < = a, b < = 10000000000 (10^10). Моя проблема - проверить, являются ли цифры в них перестановкой друг друга или нет. Каков самый быстрый способ сделать это? Я думал об использовании хеширования, но не смог найти подходящую хеш-функцию. Какие-либо предложения?

Для например - 123 является действительной перестановкой 312

Кроме того, я не хочу, чтобы отсортировать цифры в числах.

Answer 1

Если вы имеете в виду символы чисел (например, 1927 и 9721), есть (по крайней мере) несколько подходов.

Если вам разрешили сортировать, один подход состоит в том, чтобы просто sprintf их на два буфера, сортировать символы в буферах, а затем посмотреть, равны ли строки.

Однако, учитывая ваше желание не сортировать цифры, другой альтернативой является создание десятиэлементного массива со всеми элементами, первоначально установленными на ноль, а затем обрабатывать каждую цифру в первом числе, увеличивая соответствующий элемент ,

Затем сделайте то же самое со вторым номером, но уменьшающимся.

Если в конце все еще есть нули, числа были перестановкой друг друга.

Это эффективно в том, что это алгоритм O(n), где n - это количество цифр в двух числах. Псевдо-код для такого зверя будет что-то вроде:

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 

В C, следующая полная программа показывает, как это можно сделать:

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

Просто передайте ему два (положительных) номера и, предположив, что они вписываются в long, он скажет вам, имеют ли они одинаковые цифры.

Answer 2

Это домашнее задание?

Рассчитайте количество появлений каждой цифры и сравните их, если они одинаковы, то один номер можно преобразовать в другое с помощью перестановки.

Answer 3

Создать массив:

int digitOccurances[2][10]; 

В digitOccruances[X][N] магазине количество раз, что цифра N появляется в числе X. Так что, если вы сравнивали 8675309 до 9568733, массив будет в конечном итоге выглядит как:

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

Если два массива равны, то числа являются перестановками.

Это алгоритм O (п), так асимптотически говоря, это является наиболее эффективным он собирается получить (вы не можете решить эту проблему без изучения всех цифр, по крайней мере один раз.

Вы можете сразу return false, если числа имеют разную длину, поэтому предположим, что оба из них имеют длину n. Для заполнения массива потребуется 2n операций, а затем ровно 10 сравнений для чтения массива. 2n + 10 - это O (n).

Answer 4

a и b являются анаграммами, если они имеют одинаковое количество каждой цифры. Таким образом, самый быстрый способ, по-видимому, состоит в подсчете цифр для a и b:

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

Ну, если вы можете построить таблицу 80GB, вы всегда можете сделать:

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

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

Answer 6

{Отредактированный, чтобы добавить дополнительный тест)

Предполагая, что вы находитесь в области цифр, как о

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

Answer 7

Если я правильно понял ваш вопрос, перестановка - это комбинация элементов, которые не повторяются. Поэтому, если 123 является допустимой перестановкой 312, то и так

123, 
213, 
132, 
321, 
213, 

и так далее.

Итак, исходя из этого предположения, можно сказать, что у вас есть два целых числа 123456789 и 129837456. (Для простоты я также предполагаю, что оба числа имеют одинаковую длину). Если бы вы поняли этот момент, вы могли бы также проверить разные перестановки и комбинацию.

для этого все, что вам нужно сделать, чтобы получить целые числа единиц из данного числа, например:

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

или

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) 

я буквально дал вам алгоритмической намек как сделать это, чтобы это можно было легко сделать. когда-то сделано, вы будете в конечном итоге с отдельными целыми числами (лучше сохранить эти значения в массиве)

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

Теперь

сделать то же самое для другого заданного целого числа, так что вы будете в конечном итоге с другой массив целых чисел

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

так что теперь все, что вам нужно проверить, это то, что если все целые числа второго массива присутствуют в первом массиве целых чисел, если да, то они являются перестановкой целых чисел первого массива или первого номера ,

Надеюсь, это поможет.

Answer 8

Я нашел это довольно эффективное решение на rossetacode.org. Надеюсь, вы простите меня за то, что написала его на Java (мне не нравится C), но синтаксис должен быть более или менее одинаковым.

Код сначала проверяет, имеет ли количество цифр одинаковое количество цифр, а затем суммирует цифры по битам, переставляя их в общую сумму.За исключением того, что расстояние сдвига умножается на коэффициент 6. Это делает невозможным, чтобы более мелкие цифры составляли то же самое значение, что и большая цифра. Например, для одного «9» потребуется 64 раза «8», чтобы соответствовать его значению, что, очевидно, невозможно.

Этот код предполагает неотрицательный ввод.

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

Не знаете, почему вы не хотите сортировать, если только это не является условием назначения вашей домашней работы. Для тех, кто наткнуться на этот вопрос просто ищет быстрый (! И самый вещий) способ проверить, если два числа являются перестановками в Python:

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

Это решение выполняется немного быстрее в Python, опираясь, конечно, на числах, проверенных на относительно небольшие целые числа. Он хорошо работает для проблемы Project Euler 52.