2 lists permutations in python

Question

Doing a course it asks this but done anything that covers something like this I am stumpped. question follows. explanation with answer would be appreciated so that understand.

Write a Python function that takes in two lists and calculates whether they are permutations of each other. The lists can contain both integers and strings. We define a permutation as follows:

• the lists have the same number of elements

• list elements appear the same number of times in both lists

If the lists are not permutations of each other, the function returns False. If they are permutations of each other, the function returns a tuple consisting of the following elements:

• the element occuring the most times

• how many times that element occurs

• the type of the element that occurs the most times

If both lists are empty return the tuple (None, None, None). If more than one element occurs the most number of times, you can return any of them.

def is_list_permutation(L1, L2):

    '''

    L1 and L2: lists containing integers and strings
    Returns False if L1 and L2 are not permutations of each other. 
            If they are permutations of each other, returns a 
            tuple of 3 items in this order: 
            the element occurring most, how many times it occurs, and its type
    '''

    # Your code here

For example,

• if L1 = ['a', 'a', 'b'] and L2 = ['a', 'b'] then is_list_permutation returns False

• if L1 = [1, 'b', 1, 'c', 'c', 1] and L2 = ['c', 1, 'b', 1, 1, 'c'] then is_list_permutation returns (1, 3, ) because the integer 1 occurs the most, 3 times, and the type of 1 is an integer (note that the third element in the tuple is not a string).

Answer 1

I'm learning dictionary comprehension, its very useful for this kind of problem:

def is_list_permutation(L1, L2):
    '''
    L1 and L2: lists containing integers and strings
    Returns False if L1 and L2 are not permutations of each other. 
            If they are permutations of each other, returns a 
            tuple of 3 items in this order: 
            the element occurring most, how many times it occurs, and its type
    '''
    C1 = L1[:]
        try:
            for e in L2:
                L1.remove(e)
            if len(L1) != 0:
                return False
            elif len(C1) == 0:
                return (None, None, None)
        except:
            return False
        else:
            D = {C1.count(e): e for e in C1} # Dictionary comprehension
            key = max([x for x in D.keys()]) # List comprehension
            return (D[key], key, type(D[key])) # voilà!

Answer 2

Here is the code with comments as explanation line by line:

Use isPermutation as a helper method in your is_list_permutation function. This makes the code easier to read and cleaner.

L1 = [1, 'b', 1, 'c', 'c', 1]
L2 = ['c', 1, 'b', 1, 1, 'c']


def isPermutation(list1,list2):
 if len(list1) != len(list2):
   return False;  #two list does not have same length so impossible being permutation of each other
 for i in range(0, len(list1)):
   if list1.count(list1[i]) != list2.count(list1[i]):
     return False

def is_list_permutation(list1,list2):
  if (isPermutation(list1,list2) == False): #use the above method isPermutation to check if they are permutation of each other
    return False #if not return false
  elif not list1:
    return (None, None, None)
  else:
    mostOccurItem = max(set(list1), key=list1.count)  
    numberOfTimes = list1.count(mostOccurItem)
    theType = type(mostOccurItem)
    return (mostOccurItem, numberOfTimes, theType)

print(is_list_permutation(L1,L2))

Hope this helps

Answer 3

Not sure if terms of your assignment allow use of any modules, but if so, with collections it becomes quite trivial:

from collections import Counter
def is_list_permutation(l1,l2):
    c1 = Counter(l1)
    c2 = Counter(l2)
    if c1 != c2:
        return False
    elif len(c1) == 0:
        return (None, None, None)
    else:
        t = c1.most_common(1)[0]
        return t + (type(t[0]),)

Answer 4

The problem boils down to comparing multisets, Python multiset implementation is called collections.Counter():

from collections import Counter

def is_perm(L1, L2):
    c = Counter(L1)
    if c != Counter(L2):
        return False
    if not c:
        return (None, None, None)
    value, count = c.most_common(1)[0]
    return value, count, type(value)

>>> L1 = [1, 'b', 1, 'c', 'c', 1]
>>> L2 = ['c', 1, 'b', 1, 1, 'c']
>>> is_perm(L1, L2)
(1, 3, int)
>>> is_perm([], [])
(None, None, None)
>>> is_perm(L1, [])
False

Answer 5

You can use dictionary (dict) to store the occurance of items in the list. The following is O(n) algorithm.That is the best one can do

Here is how you may do it

1. First do basic checks like if the two lists have same length,empty list check etc

2. Use a hash map to store the item to count mapping of first list

3. Check the second list with the hash of first list items

Code

def is_permutation(l1,l2):
    if len(l1) != len(l2):
        return False
    if len(l1) == 0:
        return (None,None,None)
    max_item = None
    max_count = 0
    d = dict()
    for i in l1:
        d[i] = d.get(i,0) + 1
        if d[i] > max_count:
            max_count += 1
            max_item = i
    for i in l2:
        d[i] = d.get(i,0) - 1
        if d[i] == -1:
            return False
    return (max_item,max_count,type(max_item))

print ([1,2,2,"34"],["34",2,1]),is_permutation([1,2,2,"34"],["34",2,1])
print ([],["34",2,1]),is_permutation([],["34",2,1])
print ([],[]),is_permutation([],[])
print ([1,2,2,"34",2],["34",2,2,2,1]),is_permutation([1,2,2,"34",2],["34",2,2,2,1])