Как можно увеличить скорость программы с перестановками?

Question

Ввожу с экрана числа N,M,O которые больше и равны нуля N показывает сколько раз будет использоваться символ '()'. М показывает сколько раз будет использоваться '[]'. O показывает сколько раз будет использоваться '{}'. Нужно найти все перестановки символов.

def permut(arr):
    if len(arr) == 0:
        return [arr]
    res = []
    for i, j in enumerate(arr):
        res += [j+k for k in permut(arr[:i]+arr[i+1:])]
    return res



def main():
    N = int(input())
    M = int(input())
    O = int(input())

    array = []
    if N >= 0 and M >= 0 and O >= 0:
        array.append('()' * N)
        array.append('[]' * M)
        array.append('{}' * O)
    simbols = (''.join(map(str, array)))
    mat = list(set(permut(simbols)))
    print('\n'.join(mat))

main()

Answer 1

Если считать, что заданы одиночные символы в указанном количестве, то количество перестановок будет

 (n + m+o)!/(n!*m!*o!)

Если символы из пар разбиваются, то

 (2*n + 2*m + 2* o)!/((n!)^2*(m!)^2*(o!)^2)

Если нужны сами перестановки (что сомнительно уже при не очень больших параметрах), то стоит нужно использовать алгоритм next_permutation (код с сайта nayuki), не требующий дополнительной памяти. К сожалению, itertool.permutations не учитывает одинаковость элементов, и будет генерировать повторы.

def next_permutation(arr):
    # Find non-increasing suffix
    i = len(arr) - 1
    while i > 0 and arr[i - 1] >= arr[i]:
        i -= 1
    if i <= 0:
        return False
    
    # Find successor to pivot
    j = len(arr) - 1
    while arr[j] <= arr[i - 1]:
        j -= 1
    arr[i - 1], arr[j] = arr[j], arr[i - 1]


    # Reverse suffix
    arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
    return True

Использование:

a = sorted(list('[[(')) #начальная перестановка должна быть лексически наименьшей 
print(''.join(a))
while next_permutation(a):
    print(''.join(a))

или прямо на строке:

a = sorted('[[(')
print(a)
while next_permutation(a):
    print(a)


([[
[([
[[(

Answer 2

Чтобы не тратить память на хранение перестановок надо использовать генератор который будет отдавать перестановку в работу как только она готова. Внизу рекурсивный генератор, порождающий каждую перестановку один раз:

def permutations(seq):
    lst = list(seq)

    def gen(i):
        if i == len(seq):
            yield tuple(lst)
        else:
            used = set()
            for j in range(i, len(seq)):
                if lst[j] not in used:
                    used.add(lst[j])
                    lst[i], lst[j] = lst[j], lst[i]
                    yield from gen(i + 1)
                    lst[i], lst[j] = lst[j], lst[i]

    return gen(0)


def main():
    n = int(input())
    m = int(input())
    o = int(input())

    symbols = '()' * n + '[]' * m + '{}' * o
    for p in permutations(symbols):
        print(''.join(p))
    

main()

$ echo -e "0\n0\n2" | python permutations.py
{}{}
{}}{
{{}}
}{{}
}{}{
}}{{

$ time echo -e "2\n2\n2" | python permutations.py | wc -l
7484400

real  0m22.419s
user  0m22.544s
sys   0m0.088s

БЛОГ НА HUSL

Как можно увеличить скорость программы с перестановками?

Ответы (2 шт):