4
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ @greybeard Thanks, I'd appreciate comments too. I got one downvote first, and then I edited my question to ask downvoters to comment (along with some other edits), and then someone downvoted me again. Someone else kindly updated my question to make it more concise, so I guess my initial question didn't get to the point quickly enough or wasn't concise enough. \$\endgroup\$ – rishijd Mar 17 '18 at 21:05
  • \$\begingroup\$ I believe the downvotes (not mine) are related to the first question. This isn't really the place to ask how does the BigO works. \$\endgroup\$ – IEatBagels Mar 18 '18 at 0:44
  • \$\begingroup\$ @TopinFrassi thanks, where do you suggest I ask for help on Big O? I posted this on Stack Overflow and had a downvote and comment that if my code works, perhaps I should consider posting it here in codereview.stackexchange - would you say the Big O question better belongs in SO, and my question 2 on yield is for here? Little confused, sorry! Just would like to improve my skills for upcoming projects/interviews. \$\endgroup\$ – rishijd Mar 18 '18 at 0:51
  • \$\begingroup\$ Maybe just say you tried to use that and don't ask how it works. Then maybe you'll get an answer showing you how to use it? Sometimes it's weird here. You have a close vote for "not working as intended" so maybe that's it? I can't read it. \$\endgroup\$ – Raystafarian Mar 18 '18 at 1:02
  • \$\begingroup\$ Thanks @Raystafarian - I appreciate your advice :) The question on SO - I deleted it then and there. I have got a response below so I'll first work through this and then maybe post a new question if any further questions appropriate for SO. \$\endgroup\$ – rishijd Mar 19 '18 at 2:10
2
\$\begingroup\$

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!)\$.

\$\endgroup\$
  • \$\begingroup\$ Thank you! Firstly this helps so much in terms of learning best standards for Python. On the complexity, when writing my question I assumed a O(n*n!) complexity, but on re-thinking it (from your answer on itertools.permutations it looks like my code is also O(n!). Do you agree? I mean, after cleaning up the "remove duplicates" portion of the code. And, do you have any comments on my question 2, on the use of yield here? I could have easily made a set then and there in get_beautiful_perms, would it make it any different in efficiency in comparison to using yield? \$\endgroup\$ – rishijd Mar 19 '18 at 2:36
  • 1
    \$\begingroup\$ @rishijd No, the generator has no disadvantage here. In general the biggest advantage of generators is that you can generate one element at a time instead of having to keep them all in memory. Since we consume it into a set right away, this advantage is gone here. But there is still the small advantage that the generating of the permutations are separate which makes for nicer code. \$\endgroup\$ – Graipher Mar 19 '18 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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