If I have two different arrays and all I can do is check whether two elements in the arrays are equal (in other words, there is no comparison function (beyond equals) for the elements to sort them), is there any efficient way to check whether one array is a permutation of the other?

• arrays
• algorithm
• permutation

Words Like Jared's brute force solution should work, but it is O(n^2).

If the elements are hashable, you can achieve O(n).

def isPermutation(A, B):
    """
    Computes if A and B are permutations of each other.
    This implementation correctly handles duplicate elements.
    """
    # make sure the lists are of equal length
    if len(A) != len(B):
        return False

    # keep track of how many times each element occurs.
    counts = {}
    for a in A:
        if a in counts: counts[a] = counts[a] + 1
        else: counts[a] = 1

    # if some element in B occurs too many times, not a permutation
    for b in B:
        if b in counts:
            if counts[b] == 0: return False
            else: counts[b] = counts[b] - 1
        else: return False

    # None of the elements in B were found too many times, and the lists are
    # the same length, they are a permutation
    return True

Depending on how the dictionary is implemented (as a hashset vs a treeset), this will take either O(n) for hashset or O(n log n) for treeset.

This implementation might be wrong, but the general idea should be correct. I am just starting python, so this may also be an unconventional or non-pythonic style.

def isPermutation(list1, list2):
    # make sure the lists are of equal length
    if (len(list1) is not len(list2)):
        return False

    # keep track of what we've used
    used = [False] * len(list1)

    for i in range(len(list1)):
        found = False

        for j in range(len(list1)):
            if (list1[i] is list2[j] and not used[j]):
                found = True
                used[j] = True
                break

        if (not found):
            return False

    return True

If hashing for your object type makes sense, you could use a temp hash set to insert all the items from array A. Then while iterating over array B, make sure each item is already in the temp hash set.

This should be faster ( O(n) ) than a naive nested O(n^2) loop. (Except for small or trivial data sets, where a simpler naive algo might outperform it)

Note that this will take O(n) extra memory, and that this approach will only work if you dont have duplicates (or dont want to count them as part of the comparison)

Assuming the two arrays are equal length and an element could be appearing the arrays more than once, you could create another array of the same length of type boolean initialized to false.

Then iterate though one of the arrays and for each element check whether that element appears in the other array at a poistion where the corresponding boolean is false -- if it does, set the corresponding boolean to true. If all elements in the first array can be accounted for this way, the two arrays are equal, otherwise not (and you found at least one difference).

The memory requirement is O(n), the time complexity is O(n^2)

Because I can't comment yet (not enough rep), I'll just mention this here as a reply to one of the other answers: Python's set() doesn't work all that well with objects.

If you have objects that are hashable, this code should work for you:

def perm(a, b):
        dicta = {}; dictb = {}
    for i in a:
            if i in dicta: dicta[i] += 1
            else: dict[i] = 1
    for i in b:
        if i in dictb: dictb[i] += 1
        else: dict[i] = 1
    return dicta == dictb

Construct a hashmap of objects in a and the number of times they occur. For each element in b, if the element is not in the hashmap or the occurrences don't match, it is not a permutation. Otherwise, it is a permutation.

>>> perm([1,2,4], [1,4,2])
True
>>> perm([1,2,3,2,1], [1,2,1,2,3])
True
>>> perm([1,2,4], [1,2,2])
False