"Красивые перестановок тара" вызов


Я использую мои навыки кодирования с помощью Python, чтобы ответить на средний сложных проблем на сайтах, как HackerRank.

Вот это вызов. Дан массив целых чисел, где каждое число может появляться в более чем два раза, посчитать количество перестановок, в которых нет одинаковых цифр, появляются последовательно.

Мое решение решает базовый тест, но не другим, потому что это слишком медленно. Это нормально (я считаю, что само решение трудно понять, но я сначала хотела бы отзывы на мое собственное решение).

Сегодня мои вопросы:

  1. В чем сложность моего алгоритма? Я прокомментировала то, что я делаю, лучше начинать снизу вверх.

    Я думаю, учитывая n элементов в массиве, у меня два for петли и кажется n*n! решение для одного массива, но я был бы очень благодарен за четкое объяснение здесь, на Большой О, этот конкретный кусок кода.

  2. Я новичок в Питон yield и я на самом деле есть в этой части решение от другой так пост. Я просто хочу знать, я использовал yield эффективно? Какое время/эффективность бы это изменило, если бы я не использовал yield в этом случае и просто составил список perm_lst тогда и там, чтобы держать все уникальные перестановки?

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


Комментарии
1 ответ

Ну, первое и самое очевидное улучшение, как вы удалите дубликаты. В настоящее время вы переберете все красивые перестановок (по крайней мере \$\mathcal{о}(н)\$) и для каждого проверить, если он уже есть в списке (\$\mathcal{о}(н)\$ снова). Это уже \$\mathcal{О}(П^2)\$.

Если вы использовали set вместо того, что in проверить будет \$\mathcal{О,} (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))

В map(tuple, ...) это необходимо потому, что списки не hashable в Python.

Я также переименовал свои функции, следовать PEP8, в Python официального стиля-руководство и переделанной строкой документации немного больше соответствовать конвенции, изложенных в PEP257.

Вы должны также положить свой основной код по if __name__ == "__main__" охранник позволит импортировать функции из другого скрипта без его выполнения:

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)

Я также использовал _ как ненужные переменной цикла, как это принято.

Я бы также попробовать использовать другой способ проверить, если перестановка красива и использовать 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))

Конечно, это также время, потому что itertools.permutations также \$\mathcal{о}(н!)\$.

2
ответ дан 18 марта 2018 в 10:03 Источник Поделиться