0

Ввожу с экрана числа 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()
6
  • Но приведены же пары символов
    – MBo
    20 ноя 2021 в 14:41
  • @Khimer, ваша программа работает. Что вы ещё от неё хотите? 20 ноя 2021 в 14:49
  • хочу увеличить скорость, из-за того что я отправляю все элементы массива на другой массив, для больших чисел программа работает слишком долго. Хотел бы узнать как лучше оптимизировать
    – Khimer
    20 ноя 2021 в 14:51
  • Но вы же понимаете что число перестановок огромно? 20 ноя 2021 в 14:53
  • да, понимаю, вот и обращаюсь из-за этого
    – Khimer
    20 ноя 2021 в 14:53

2 ответа 2

2

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

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


([[
[([
[[(
12
  • Каждый символ из пары должен использоваться по одиночку
    – Khimer
    20 ноя 2021 в 14:48
  • @Khimer А где это описано в задаче? Может, ещё и правильная скобочная последовательность должна образовываться?
    – MBo
    20 ноя 2021 в 15:07
  • @Stanislav Volodarskiy Я посчитал пары неразрывными ради факта того, что можно посчитать а не генерировать. Надеюсь на уточнение условия.
    – MBo
    20 ноя 2021 в 15:08
  • По задаче даны пары символов, но использовать мы должны каждый символ из пары. Понимаю, что размеры например для четырех пар уже огромны, но тестируют до 7 пар, а там уже 14 символов. Для 14 символов у меня код проводит слишком много операции, даже памяти не хватает, вот и хотел узнать каким образом решить это с меньшим количеством операции
    – Khimer
    20 ноя 2021 в 15:18
  • 1
    Я классический код привёл
    – MBo
    20 ноя 2021 в 16:05
1

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.