2

Вечер добрый.Такой вопрос, программа должна выводить все скобочные выражения без повторений. На ввод идут 3 числа: первое обозначает количество пар скобок () второе количество пар скобок [] третье количество пар скобок {}

и на вывод должен вывести все варианты правильной расстановки этих скобок (т.е

[({})]
{()[]}
{()}[]
{[()]}
{[]()}
{[]}()
{}([])
{}()[]

, но не {][()} )

def variants(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return


def permutations(count_round, count_square, count_braces):
    create_round = lambda s: '(%s)' % s
    create_square = lambda s: '[%s]' % s
    create_braces = lambda s: '{%s}' % s
    result = set()
    for lf in variants(((create_round,) * count_round) +
                        ((create_square,) * count_square) +
                        ((create_braces,) * count_braces)):
        s = ''
        for f in lf:
            s = f(s)
        result.add(s)
    return result


count_round = int(input()) #()
count_square = int(input()) #[]
count_braces = int(input()) #{}
print('\n'.join(permutations(count_round, count_square, count_braces)))

так он выводит только:

([{}])
[{()}]
{([])}
({[]})
{[()]}
[({})]

но не выводит подобные скобки:

{[]()}
{[]}()
{}([])
{}()[]
{()[]}
{()}[]
3

2 ответа 2

4
BRACKET_MAP = {
  '[': ']',
  '(': ')',
  '{': '}'
}

def brackets(Q,W,E, stack=[], opened=[]):
  if (Q,W,E) == (0,0,0) and not opened:
    yield ''.join(stack)
  else:
    if opened:
      yield from brackets(Q,W,E, stack + [BRACKET_MAP[opened[0]]], opened[1:])
    if Q:
      yield from brackets(Q-1, W, E, stack + ['('], ['('] + opened)
    if W:
      yield from  brackets(Q, W-1, E, stack + ['['], ['['] + opened)
    if E:
      yield from  brackets(Q, W, E-1, stack + ['{'], ['{'] + opened)

Q = int(input())
W = int(input())
E = int(input())
if Q >= 0 and W >= 0 and E >= 0:
    for combo in brackets(Q,W,E):
      print(combo)
else:
    print("ERROR")
3
  • спасибо большое, а как можно осуществить проверку на повторение одних и тех же строк? например: {}{} {{}} {}{} {{}} 3 и 4 это повтор двух первых
    – shiroi
    1 дек 2017 в 13:20
  • внес изменение в решение, убрал циклы заменив их на if
    – godva
    1 дек 2017 в 13:36
  • я уже тоже попробовал поменять for на if и получилось, спасибо большое
    – shiroi
    1 дек 2017 в 13:38
3

Вы можете это оптимизировать:

import itertools


def permutations(count_round, count_square, count_braces):
    create_round = lambda s: '(%s)' % s
    create_square = lambda s: '[%s]' % s
    create_braces = lambda s: '{%s}' % s
    result = set()
    for lf in itertools.permutations(((create_round,) * count_round) +
                                     ((create_square,) * count_square) +
                                     ((create_braces,) * count_braces)):
        s = ''
        for f in lf:
          s = f(s)
        result.add(s)
    return result


count_round = 2 #()
count_square = 2 #[]
count_braces = 2 #{}
print('\n'.join(permutations(count_round, count_square, count_braces)))
0

Ваш ответ

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

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