检查两个数字是否相互排列？
给定两个数字a，b使得1 <= a，b <= 10000000000（10 ^ 10）。 我的问题是检查它们中的数字是否是彼此的排列。 这样做的最快方法是什么？ 我想到使用散列但无法找到任何合适的散列函数。 有什么建议？
例如 – 123是312的有效排列
另外，我不想对数字中的数字进行排序。
如果你的意思是数字的字符（例如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 #include #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 \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 ，它会告诉你它们是否具有相同的数字计数。
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");
是作业吗？
计算每个数字的出现次数并进行比较，如果它们相同则可以使用排列将一个数字转换为其他数字。
创建一个数组：
int digitOccurances[2][10];
在digitOccruances[X][N]存储数字N出现在数字X中的次数。 因此，如果您将8675309与9568733进行比较，则arrays最终会如下所示：
{ { 1, 0, 0, 1, 0, 1, 1, 1, 1, 1 } , { 0, 0, 0, 2, 0, 1, 1, 1, 1, 1 } }
如果两个数组相等，那么数字就是排列。
这是一个O（n）算法，所以渐近地说这是最有效的算法（如果不至少检查一次所有数字，就无法解决这个问题。
如果数字具有不同的长度，则可以立即返回false，因此假设两者的长度均为n。 填充数组需要2n次操作，然后完成10次比较才能读取数组。 2n + 10是O（n）。
我在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; }
好吧，如果你可以构建一个80GB的表，你可以随时做：
int64 table[10000000000] = {0, blah blah..., 9999999999}; if (table[a] == table[b]) ...
如果我从你的问题中正确理解了一个排列是元素的组合，这些元素不重复。 因此，如果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
所以现在你需要检查的是，如果第二个数组的所有整数都存在于第一个整数数组中，如果是，则它们是第一个数组或第一个数字的整数的排列。
我希望这有帮助。
{已编辑添加其他测试）
假设你在数字领域，那该怎么样
if ( ('1' ^ '2' ^ '3' == '3' ^ '1' ^ '2') && ('1' + '2' + '3' == '3' + '1' + '2') ) { cout << "Yes\n"; } else { cout << "No\n"; }
不确定为什么你不想排序，除非这是你的家庭作业的条件。 对于任何在这个问题上磕磕绊绊的人来说，只是寻找最快（最pythonic！）的方法来测试两个整数是否是Python中的排列 ：
def arePermutations(a, b): return sorted([d for d in str(a)]) == sorted([d for d in str(b)])
这个解决方案在Python中的运行速度稍快，当然，依赖于测试的数字是相对较小的整数。 它对Project Euler问题52非常有效。