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()

• Josiah: There's a bug in this code because it allows each character in the first string to be counted against multiple copies of that character in the second. As such it returns False (count==4, n==2) for permutation([2,2], [2,2]) which obviously should be True, and True (count==n==3) for permutation([0,1,2], [1,2,2]) which should be False.

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.

• chris_st: I'm not a Python expert, but generally speaking, I believe inserting n items into a hash table is also O(n log n). The constants are different, of course, between hash inserts and sorting, and sorting moves elements as well. Oddly enough, on a NUMA (Non-Uniform Memory Access) machine, sorting may well be faster than hashing, due to better cache usage.
• Captain Man: Just a reminder that when dealing with big-O for small values for n, it can often be better to use "worse" algorithms. One of my professors had us intentionally think of radix sorting as k O(n) due to the large overhead.

Answer 2

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)

Answer 3

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))

• slepic: Won't this modify the input for the caller?
• Alex Povel: @slepic, Yeah, which is probably unwanted behaviour, or at least surprising. Calling sorted(lst) will get rid of that, but using sets is likely a better approach.
• Captain Man: @AlexPovel I'm unfamiliar with Python, but if sets work same as Java (and math) then they don't allow duplicates -- but OP allows duplicates in their example: [2,3,4,4,4,4].
• Alex Povel: @CaptainMan yes, sets don't allow duplicates in Python either. There was a now-deleted answer in this thread earlier that created sets but also compared the lengths of the initial lists. It seemed to be a valid attempt but did not work on closer inspection. So sets are not the way to go, you are right.
• Manuel: @slepic I'd say the even bigger issue is that it's wrong. It returns True for any two lists, regardless of whether they're permutations of each other.