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?
给定两个数字a,b使得1 <= a,b <= 10000000000(10 ^ 10)。我的问题是检查它们中的数字是否是彼此的排列。这样做的最快方法是什么?我想到使用散列但无法找到任何合适的散列函数。有什么建议?
For e.g - 123 is a valid permutation of 312
例如,123是312的有效排列
Also I don't want to sort the digits in the numbers.
另外,我不想对数字中的数字进行排序。
9 个解决方案
#1
31
If you mean the characters of the numbers (such as 1927 and 9721), there are (at least) a couple of approaches.
如果你的意思是数字的字符(例如1927和9721),那么(至少)有两种方法。
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.
如果允许排序,一种方法是简单地将它们sprintf到两个缓冲区,对缓冲区中的字符进行排序,然后查看字符串是否相等。
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:
这是有效的,因为它是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
In C, the following complete program illustrates how this can be done:
在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;
}
Simply pass it two (positive) numbers and, assuming they fit in a long, it'll tell you whether they have the same digit counts.
简单地传递两个(正数)数字,假设它们适合长,它会告诉你它们是否具有相同的数字计数。
#2
17
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:
a和b是anagrams,如果它们具有相同数量的每个数字。所以基本上最快的方式似乎是,计算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");
#3
3
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.
计算每个数字的出现次数并进行比较,如果它们相同则可以使用排列将一个数字转换为其他数字。
#4
1
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:
在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 } }
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.
这是一个O(n)算法,所以渐近地说这是最有效的算法(如果不至少检查一次所有数字,就无法解决这个问题。
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).
如果数字具有不同的长度,则可以立即返回false,因此假设两者的长度均为n。填充数组需要2n次操作,然后完成10次比较才能读取数组。 2n + 10是O(n)。
#5
1
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.
我在rossetacode.org上找到了这个相当有效的解决方案。我希望你能原谅我用Java编写它(我对C不满意),但语法应该或多或少相同。
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.
代码首先检查数字是否具有相同的位数,然后通过将它们转换为总数来对数字求和。除了移位距离乘以因子6.这使得较小的数字不可能与较大的数字组成相同的值。例如,一个'9'将需要64次'8'来匹配其值,这显然是不可能的。
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;
}
#6
0
Well if you can build an 80GB table, you could always do:
好吧,如果你可以构建一个80GB的表,你可以随时做:
int64 table[10000000000] = {0, blah blah..., 9999999999};
if (table[a] == table[b]) ...
#7
0
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是312的有效排列,那么也是如此
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.
所以基于这个假设,假设你有两个整数123456789和129837456.(为简单起见,我也假设两个数字的长度相等)。如果您理解了这一点,那么您也可以检查不同的排列和组合。
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
or
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.
我希望这有帮助。
#8
-1
{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";
}
#9
-1
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:
不确定为什么你不想排序,除非这是你的家庭作业的条件。对于任何在这个问题上磕磕绊绊的人来说,只是寻找最快(最pythonic!)的方法来测试两个整数是否是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.
这个解决方案在Python中的运行速度稍快,当然,依赖于测试的数字是相对较小的整数。它对Project Euler问题52非常有效。
#1
31
If you mean the characters of the numbers (such as 1927 and 9721), there are (at least) a couple of approaches.
如果你的意思是数字的字符(例如1927和9721),那么(至少)有两种方法。
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.
如果允许排序,一种方法是简单地将它们sprintf到两个缓冲区,对缓冲区中的字符进行排序,然后查看字符串是否相等。
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:
这是有效的,因为它是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
In C, the following complete program illustrates how this can be done:
在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;
}
Simply pass it two (positive) numbers and, assuming they fit in a long, it'll tell you whether they have the same digit counts.
简单地传递两个(正数)数字,假设它们适合长,它会告诉你它们是否具有相同的数字计数。
#2
17
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:
a和b是anagrams,如果它们具有相同数量的每个数字。所以基本上最快的方式似乎是,计算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");
#3
3
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.
计算每个数字的出现次数并进行比较,如果它们相同则可以使用排列将一个数字转换为其他数字。
#4
1
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:
在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 } }
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.
这是一个O(n)算法,所以渐近地说这是最有效的算法(如果不至少检查一次所有数字,就无法解决这个问题。
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).
如果数字具有不同的长度,则可以立即返回false,因此假设两者的长度均为n。填充数组需要2n次操作,然后完成10次比较才能读取数组。 2n + 10是O(n)。
#5
1
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.
我在rossetacode.org上找到了这个相当有效的解决方案。我希望你能原谅我用Java编写它(我对C不满意),但语法应该或多或少相同。
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.
代码首先检查数字是否具有相同的位数,然后通过将它们转换为总数来对数字求和。除了移位距离乘以因子6.这使得较小的数字不可能与较大的数字组成相同的值。例如,一个'9'将需要64次'8'来匹配其值,这显然是不可能的。
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;
}
#6
0
Well if you can build an 80GB table, you could always do:
好吧,如果你可以构建一个80GB的表,你可以随时做:
int64 table[10000000000] = {0, blah blah..., 9999999999};
if (table[a] == table[b]) ...
#7
0
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是312的有效排列,那么也是如此
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.
所以基于这个假设,假设你有两个整数123456789和129837456.(为简单起见,我也假设两个数字的长度相等)。如果您理解了这一点,那么您也可以检查不同的排列和组合。
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
or
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.
我希望这有帮助。
#8
-1
{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";
}
#9
-1
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:
不确定为什么你不想排序,除非这是你的家庭作业的条件。对于任何在这个问题上磕磕绊绊的人来说,只是寻找最快(最pythonic!)的方法来测试两个整数是否是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.
这个解决方案在Python中的运行速度稍快,当然,依赖于测试的数字是相对较小的整数。它对Project Euler问题52非常有效。