How to tell if two arrays are permutations of each other (without the ability to sort them)

Question

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?

Answer 1

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.

Answer 2

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