Checking whether two numbers are permutation of each other?_问答_开发者

Given two numbers a, b such that 1 <= a , b <= 10000000000 (10^10). My problem is to check whether the digits in them are permutation of each other or not. What is the fastest way of doing it? I was thinks of using hashing but unable to find any suitable hash function. Any suggestions?

For e.g - 开发者_JS百科 123 is a valid permutation of 312

Also I don't want to sort the digits in the numbers.

If you mean the characters of the numbers (such as 1927 and 9721), there are (at least) a couple of approaches.

If you were allowed to sort, one approach is to simply sprintf them to two buffers, sort the characters in the buffers, then see if the strings are equal.

However, given your desire to not sort the digits, another alternative is to set up a ten-element array, with all elements initially set to zero, then process each digit in the first number, incrementing the relevant element.

Then do the same with the second number but decrementing.

If, at the end, it's still all zeros, the numbers were a permutation of each other.

This is efficient in that it's an O(n) algorithm where n is the number of digits in the two numbers. The pseudo-code for such a beast would be something like:

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, the following complete program illustrates how this can be done:

#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 pass it two (positive) numbers and, assuming they fit in a long, it'll tell you whether they have the same digit counts.

a and b are anagrams if they have the same number of each digit. So basically the fastest way seems to be, counting the digits for a and 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");

Is it homework?

Calculate number of appearances of each digit and compare them, if they are same then one number can be converted to other using permutation.

Create an array:

int digitOccurances[2][10];

In digitOccruances[X][N] store the number of times that the digit N appears in the number X. So if you were comparing 8675309 to 9568733, the array would end up looking like:

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

If the two arrays are equal, then the numbers are permutations.

This is an O(n) algorithm, so asymptotically speaking this is the most efficient it's going to get (you can't solve this problem without examining all of the digits at least once.

You can immediately return false if the numbers have different lengths, so assume that both of are of length n. It will take 2n operations to fill the array, and then exactly 10 comparisons to read the array. 2n + 10 is O(n).

I've found this rather efficient solution on rossetacode.org. I hope you'll forgive me for writing it in Java (I'm not comfortable with C) but the syntax should be more or less the same.

The code first checks to see if the numbers have the same number of digits, then sums up the digits by bit shifting them into a total. Except the shift distance is multiplied by a factor 6. This makes it impossible for smaller digits to compose the same value as a larger digit. For instance one '9' would require 64 times '8' to match its value, which obviously isn't possible.

This code assumes non-negative input.

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

If what i understood from your question correctly a permutation is a combination of the elements, which do not repeat. So if 123 is a valid permutation of 312 then so does

123,
213,
132,
321,
213,

and so on.

So based on this assumption lets say you got two integers 123456789 and 129837456. (For simplicity i am also assuming that both numbers have equal length). If you understood the point then you might be able to check for different permutations and combination as well.

for that all you need to do is to get the integers of units out of the given number, e.g:

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)

i have literally given you algorithmic hint of how to do that so this can easily be done. once done you will end up with separate integers (better save these values in an array)

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

Now

do the same for the other given integer so you will end up with another array of integers

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

so now all you need to check is that if all of the integers of the second array are present in the first array of integers, if yes then they are a permutation of the integers of the first array or the first number.

I hope this helps.

Well if you can build an 80GB table, you could always do:

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

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

{Edited to add additional test)

Assuming you are in the domain of digits, how about

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

Not sure why you don't want to sort, unless that was a condition of your homework assignment. For anyone stumbling on this question just looking for the fastest (and most pythonic!) way to test if two integers are permutations in Python:

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

This solution runs slightly faster in Python, relying, of course, on the numbers tested to be relatively small integers. It works quite well for Project Euler problem 52.