6
\$\begingroup\$

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()
\$\endgroup\$
1
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Josiah
    May 20, 2020 at 11:11

3 Answers 3

10
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – chris_st
    May 20, 2020 at 14:50
  • \$\begingroup\$ 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. \$\endgroup\$ May 20, 2020 at 16:41
1
\$\begingroup\$

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))
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Won't this modify the input for the caller? \$\endgroup\$
    – slepic
    May 20, 2020 at 4:16
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Alex Povel
    May 20, 2020 at 6:55
  • \$\begingroup\$ @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]. \$\endgroup\$ May 20, 2020 at 16:42
  • \$\begingroup\$ @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. \$\endgroup\$
    – Alex Povel
    May 20, 2020 at 17:23
  • \$\begingroup\$ @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. \$\endgroup\$
    – Manuel
    Apr 18, 2021 at 17:47
1
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.