检查两个数字是否相互排列?

如果您是指数字的字符(如1927和9721),那么至少有两种方法。

如果允许您进行排序,一种方法是 sprintf 将它们分成两个缓冲区,对缓冲区中的字符进行排序,然后查看字符串是否相等。

然而,鉴于你的愿望 不 对数字排序,另一种选择是设置一个十元素数组,所有元素最初都设置为零,然后处理第一个数字中的每个数字,使相关元素递增。

然后对第二个数字执行相同的操作,但要递减。

如果在最后,它仍然是0,那么这些数字是相互排列的。

这是有效的,因为它是 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 ,它将告诉您它们是否具有相同的数字计数。

如果每个数字的数目相同,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");

是作业吗?

计算每个数字的出现次数并进行比较,如果它们相同,则可以使用排列将一个数字转换为另一个数字。

创建数组:

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

不知道为什么你不想排序,除非这是你作业的一个条件。对于任何在这个问题上犹豫不决的人 最快的(也是最多的蟒蛇!)测试python中是否有两个整数是排列的方法 :

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

这个解决方案在python中运行得稍快,当然依赖于被测试为相对较小整数的数字。对于项目Euler问题52来说,它工作得相当好。