通过使用递归确定两个数组是否彼此置换 [英] determine whether two arrays are permutation of each other by using recursion

问题描述

我在编写代码时遇到一些困难，该代码通过使用递归确定两个未排序的数组是否彼此置换. 我知道如何通过非递归代码使用排序来确定它-但我不知道如何通过递归来做到这一点.

I have some difficulties in writing a code which determines whether two unsorted arrays are permutation of each other , by using recursion. I know how to determine it by non-recursive code, using sorts - but I dont know how to do it by using recursion.

到目前为止，我还没有任何真正的主意...

So far, I cant get any real idea...

int CheckPermutation(int arr1[], int arr2[], int size) {
    if (size == 0) 
        return 1;
    if (size == 1)   
       return (arr1[0] > arr2[0]);
}   

这就是我尝试过的，我发现从那时开始很难继续

that's what I have tried, I find it difficult to continue from that point

推荐答案

以下是使用递归比较两个未排序数组而不修改它们的实现:

Here is an implementation for comparing 2 unsorted arrays without modifying them that uses recursion:

#include <stdio.h>

// count occurrences of value in an array using recursion
int rcount(int value, const int *a, int size) {
    return size == 0 ? 0 : (value == *a) + rcount(value, a + 1, size - 1);
}

// check if all entries in a have the same number of occurrences in a and b
int check_perm(const int *a, const int *b, int size) {
    for (int i = 0; i < size; i++) {
        if (rcount(a[i], a, size) != rcount(a[i], b, size))
            return 0;
    }
    return 1;
}

int main(void) {
    int a[] = { 1, 2, 3, 3, 4, 4, 4, 5, 6, };
    int b[] = { 1, 3, 2, 4, 5, 4, 4, 6, 3, };
    int c[] = { 1, 3, 2, 4, 5, 4, 4, 6, 6, };

    if (check_perm(a, b, sizeof(a) / sizeof(*a)))
        printf("arrays a and b match\n");

    if (!check_perm(a, c, sizeof(a) / sizeof(*a)))
        printf("arrays a and c do not match\n");

    if (!check_perm(b, c, sizeof(b) / sizeof(*b)))
        printf("arrays b and c do not match\n");

    return 0;
}

这是具有单个递归函数的解决方案.这两个阵列都可能被修改.如果确实check_perm()返回非零值，则两个数组都将被排序:

Here is a solution with a single recursive function. Both arrays are potentially modified. If indeed check_perm() returns non zero, both arrays will have been sorted:

int check_perm(const int *a, const int *b, int size) {
    if (size > 1) {
        for (int i = 1; i < size; i++) {
            if (a[0] > a[i]) {
                int temp = a[0];
                a[0] = a[i];
                a[i] = temp;
            }
            if (b[0] > b[i]) {
                int temp = b[0];
                b[0] = b[i];
                b[i] = temp;
            }
        }
        return (a[0] == b[0]) && check_perm(a + 1, b + 1, size - 1);
    }
    return 1;
}

这篇关于通过使用递归确定两个数组是否彼此置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！