“Tara's Beautiful Permutations” challenge

Question

I'm practising my coding skills using Python to answer medium to difficult problems on sites like HackerRank.

Here is the challenge. Given an array of integers, where each number can appear at most twice, count the number of permutations in which no identical numbers appear consecutively.

My solution solves the base test but not the others because it is too slow. That's okay for now (I find the actual solution difficult to understand, but I first would like feedback to my own solution).

My questions today are:

1. What is the time complexity of my algorithm? I have commented on what I am doing, best to start from the bottom up.

   I think, given n elements in the array, I have two for loops and it seems like a n*n! solution for one array, but I would really appreciate a clear explanation here on Big O for this particular piece of code.

2. I am new to Python's yield and I actually got this part of the solution from another SO post. I just want to know, have I used yield efficiently? What time/efficiency difference would it have made if I didn't use yield in this case and just made a list perm_lst then and there, to hold all unique permutations?

# Enter your code here. Read input from STDIN. Print output to STDOUT

def getBeautifulPerms(arr, arrlen):

    if (arrlen==1): yield arr
    else:
        for perm in getBeautifulPerms(arr[1:], arrlen-1):
            for i in range(arrlen):
                arr_before = perm[:i]
                arr_after = perm[i:]

                if ( (not(arr_before) or arr_before[-1] != arr[0])) and (not(arr_after) or arr_after[0] != arr[0]):
                    yield perm[:i] + [arr[0]] + perm[i:]

def printBeautifulPerms(arr, n):
    '''
    @param arr array of integers (not null)
    @param n length of array arr
    post: prints the number of good permutations mod (10**9 + 7)
    '''

    perm_lst = []
    for perm in getBeautifulPerms(arr, n):
        if perm not in perm_lst: 
            perm_lst.append(perm) # remove duplicates    

    print(len(perm_lst) % (10**9 + 7))

# main code - the problem states we'll receive this input:  
q = int(input()) # no of queries (arrays)

for i in range(q):
    n = int(input()) # no of elements in array
    arr = input () # space separated array of n integers
    arr = arr.split()
    printBeautifulPerms(arr, n)

Answer 1

Well, the first and most obvious improvement is how you remove duplicates. Currently you iterate over all beautiful permutations (at least \$\mathcal{O}(n)\$) and for each check if it is already in the list (\$\mathcal{O}(n)\$ again). This is already \$\mathcal{O}(n^2)\$.

If you used a set instead, that in check would be \$\mathcal{O}(1)\$:

def print_beautiful_perms(arr, n):
    """
    Prints the number of beautiful permutations mod (10**9 + 7)

    arr: array of integers (not null)
    n: ?
    """
    permutations = set(map(tuple, get_beautiful_perms(arr, n)))
    print(len(permutations) % (10**9 + 7))

The map(tuple, ...) is needed because lists are not hashable in Python.

I also renamed your functions to adhere to PEP8, Python's official style-guide and reworked the docstring a bit to conform more to the conventions laid out in PEP257.

You should also put your main code under a if __name__ == "__main__" guard to allow importing your functions from another script without executing it:

if __name__ == "__main__":
    # main code - the problem states we'll receive this input:  
    q = int(input())    # no of queries (arrays)

    for _ in range(q):
        n = int(input())    # no of elements in array
        arr = input().split()    # space separated array of n integers
        print_beautiful_perms(arr, n)

I also used _ as the unneeded loop variable, as is the convention.

I would also use try a different way to check if a permutation is beautiful and use itertools.permutations:

from itertools import permutations

def is_beautiful(arr):
    return all(x != y for x, y in zip(arr, arr[1:]))

def get_beautiful_perms(arr, arrlen):
    return filter(is_beautiful, permutations(arr))

Of course this also times out, because itertools.permutations is also \$\mathcal{O}(n!)\$.