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

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

• 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. – Josiah May 20 '20 at 11:11

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.

• 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. – chris_st May 20 '20 at 14:50
• 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. – Captain Man May 20 '20 at 16:41

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

• Won't this modify the input for the caller? – slepic May 20 '20 at 4:16
• @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. – Alex Povel May 20 '20 at 6:55
• @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]. – Captain Man May 20 '20 at 16:42
• @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. – Alex Povel May 20 '20 at 17:23

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)