Check if two lists are permutations of the one another ( Improvement)

Question

Task: . Complete the following function that determines if two lists contain the same elements, but not necessarily in the same order. The function would return true if the first list contains 5, 1, 0, 2 and the second list contains 0, 5, 2, 1. The function would return false if one list contains elements the other does not or if the number of elements differ. This function could be used to determine if one list is a permutation of another list. The function does not affect the contents of either list.

My code:

def permutation(a,b):
    if len(a) != len(b):
        return False
    n = len(a)
    count = 0
    for i in range(n):
        for j in range(n):
            if b[j] == a[i]:
                count += 1
    return count == n

def main():
    lst_1 = [1,2,3,4]
    lst_2 = [2,4,3,1]
    lst_3 = [2,4,4,5,4,5]
    lst_4 = [2,3,4,4,4,4]
    print(permutation(lst_1,lst_2))
    print(permutation(lst_2,lst_3))
    print(permutation(lst_3,lst_4))
main()

Answer 1

You can also do:

from collections import Counter

def compare_lists(list1, list2): 
    return Counter(list1) == Counter(list2)

While list.sort / sorted has O(n log n) time complexity, constructing a Counter (which is a dict internally) is O(n). This is also an improvement over the solution in the question, which is O(n ^ 2).

There is also a more efficient memory allocation involved if you do not want to mutate list1 and list2. Constructing the sorted list has O(n) space complexity, while constructing the Counter is O(k), where k is the number of unique elements.

If you wanted to make this function scalable to an arbitrary number of lists, you could do:

from collections import Counter

def compare_lists(*lists):
    counters = map(Counter, lists)

    try:
        first_counter = next(counters)
    except StopIteration:
        return True

    return all(first_counter == counter for counter in counters)

Now compare_lists takes a variable number of arguments, and would return True if all of the arguments are permutations of each other.

Answer 2

Just sort both lists and compare them:

lst1=[5,1,0,2]
lst2=[0,5,2,1]

def comparelists(list1, list2):
    return(list1.sort()==list2.sort())

print(comparelists(lst1, lst2))

Answer 3

This might be totally over engineered compared to what you need.

Depending on what you input data actually is there are fast or faster metodes to find the difference.

Untested pseudo code ahead

All tests should start with a size comparison as that is a fast way to find out that they are not equal. If you have large data structures and small keys you want to compare then make a new list with just the values you want to compare. Using a kind of metode IntroSort a variant of QuickSort to quickly find out if they are equal. Depth is 2 times the Log2(size A).

bool IntroEqual (A,B, depth)
  if (size A != size B) // different size so not equal
    return false 

  if (size A <= 16)
    insertion_sort(A)
    insertion_sort(B)
    return A == B

  if (dictionary size is small)
    return count_sort(A) == count_sort(B)

  pivot = cleverly selected
  PA = partition(A, pivot)
  PB = partition(B, pivot)

  depth = depth - 1;
  if (depth == 0) // using introspection we now know that we selected bad pivots.
    return sort(A) == sort(B)

  return IntroEqual (PA low, PB low) && IntroEqual (PA high, PB high)