Function to check if an array is a permutation-CodePudding

I have to write a function which accepts an int array parameter and checks to see if it is a permutation.

I tried this so far:

bool permutationChecker(int arr[], int n){
    for (int i = 0; i < n; i  ){
        //Check if the array is the size of n
        if (i == n){
            return true;
        }
        if (i == arr[n]){
            return true;
        }
    }
    return false;
}

but the output says some arrays are permutations even though they are not.

CodePudding user response：

When you write i == arr[n], that doesn't check whether i is in the array; that checks whether the element at position n is i. Now, that's even worse here, as the array size is n, so there's no valid element at position n: it's UB, array is overindexed.

If you'd like to check whether i is in the array, you need to scan each element of the array. You can do this using std::find(). Either that, or you might sort (a copy of) the array, then check if i is at position i:

bool isPermutation(int arr[], int n){
    int* arr2 = new int[n]; // consider using std::array<> / std::vector<> if allowed
    std::copy(arr, arr   n, arr2);
    std::sort(arr2, arr2   n);
    for (int i = 0; i < n; i  ){
        if (i != arr2[i]){
            delete[] arr2;
            return false;
        }
    }
    delete[] arr2;
    return true;
}

CodePudding user response：

One approach to checking that the input contains one of each value is to create an array of flags (acting like a set), and for each value in your input you set the flag to true for the corresponding index. If that flag is already set, then it's not unique. And if the value is out of range then you instantly know it's not a permutation.

Now, you would normally expect to allocate additional data for this temporary set. But, since your function accepts the input as non-constant data, we can use a trick where you use the same array but store extra information by making values negative.

It will even work for all positive int values, since as of C 20 the standard now guarantees 2's complement representation. That means for every positive integer, a negative integer exists (but not the other way around).

bool isPermutation(int arr[], int n)
{
    // Ensure everything is within the valid range.
    for (int i = 0; i < n; i  )
    {
        if (arr[i] < 1 || arr[i] > n) return false;
    }

    // Check for uniqueness. For each value, use it to index back into the array and then
    // negate the value stored there. If already negative, the value is not unique.
    int count = 0;
    while (count < n)
    {
        int index = std::abs(arr[count]) - 1;
        if (arr[index] < 0)
        {
            break;
        }
        arr[index] = -arr[index];
        count  ;
    }

    // Undo any negations done by the step above
    for (int i = 0; i < count; i  )
    {
        int index = std::abs(arr[i]) - 1;
        arr[index] = std::abs(arr[index]);
    }

    return count == n;
}

Let me be clear that using tricky magic is usually not the kind of solution you should go for because it's inevitably harder to understand and maintain code like this. That should be evident simply by looking at the code above. But let's say, hypothetically, you want to avoid any additional memory allocation, your data type is signed, and you want to do the operation in linear time... Well, then this might be useful.