Sekwencje w nawiasach w porządku leksykograficznym

9

Wyzwanie Podjęte stąd i również tutaj

N sekwencji nawiasy składa n ( S n ) s.

Prawidłową sekwencję nawiasów definiuje się następująco:

Możesz znaleźć sposób, aby powtórzyć kasowanie sąsiedniej pary nawiasów „()”, aż stanie się pusta.

Na przykład, (())jest prawidłowym nawiasami, możesz usunąć parę na 2. i 3. pozycji i staje się ona (), a następnie możesz ją opróżnić. )()(nie jest prawidłowym nawiasami, po skasowaniu pary na 2. i 3. pozycji staje się ona )(i nie można jej już usunąć

Zadanie

Biorąc pod uwagę liczbę n , musisz wygenerować wszystkie prawidłowe sekwencje nawiasów w porządku leksykograficznym

Dane wyjściowe mogą być tablicą, listą lub łańcuchem (w tym przypadku sekwencją na wiersz)

Można użyć innego parę nawias takie jak {}, [], ()lub jakiegokolwiek otwartego blisko znak

Przykład

  • n = 3

    ((()))    
    (()())    
    (())()    
    ()(())    
    ()()()
    
  • n = 2

    (())
    ()()
    
Luis Felipe De Jesus Munoz
źródło
@JoKing Tak, oczywiście. Zakładam, że i tak nie zmieni to głównej koncepcji wyzwania.
Luis felipe De jesus Munoz
Eh, mogę wymyślić kilka języków, w których eval interpretuje je inaczej, na przykład
Jo King,
1
Powiązane: Liczby katalońskie (wynik tego wyzwania = liczba linii wyniku tego wyzwania)
user202729,
3
Praktycznie to samo , ale z pewnymi dziwnymi ograniczeniami, takimi jak „Nie możesz pisać funkcji rekurencyjnych”. /// Dodatek tego wyzwania (zezwól na wszystkie
zamki
Czy „tablica, lista lub ciąg” „sekwencji” dowolnego „znaku otwarcia-zamknięcia” oznacza, że ​​moglibyśmy wypisać listę dwóch liczb całkowitych (takich jak 1s i -1s)?
Jonathan Allan

Odpowiedzi:

8

Perl 6 , 36 bajtów

{grep {try !.EVAL},[X~] <[ ]>xx$_*2}

Wypróbuj online!

Znajduje wszystkie posortowane leksykograficznie kombinacje 2)n []i filtruje te, które EVALpoprawnie. Zauważ, że wszystkie prawidłowe kombinacje (nawet podobne [][]) oceniają na [](co jest falsey, ale my not( !), aby odróżnić od tryzwracania Nil)

Wyjaśnienie:

{                                  }  # Anonymous code block
                        <[ ]>         # Create a list of ("[", "]")
                             xx$_*2   # Duplicate this 2n times
                   [X~]               # Find all possible combinations
 grep {          },                   # Filter from these
            .EVAL                     # The EVAL'd strings
       try !                          # That do not throw an error
Jo King
źródło
3
Jeśli ktoś jest ciekawy, [][]to kawałek Zen pustej tablicy, która daje tablicę samą w sobie. Plasterek można zastosować wiele razy, więc [][][][]...ocenia []. Poza tym [[]]nie konstruuje tablicy zagnieżdżonej, ale pustą tablicę z powodu reguły pojedynczego argumentu (musisz napisać [[],]dla tablicy zagnieżdżonej). Więc każda zrównoważona sekwencja[] nawiasów powoduje pustą tablicę, która przyjmuje wartość false.
nwellnhof,
6

R , 112 107 99 bajtów

Podejście nierekurencyjne. Używamy „<” i „>”, ponieważ pozwala to uniknąć znaków specjalnych w wyrażeniu regularnym. Aby umożliwić nam użycie krótszej specyfikacji dla zakresu ASCII, generujemy ciągi 3 ^ 2n 2n znaków „<”, „=” i „>” przy użyciuexpand.grid (za pomocą ich kodów ASCII 60, 61 i 62), a następnie grep do zobacz, które kombinacje dają zrównoważone nawiasy otwierające i zamykające. Oczywiście możliwości „=” zostaną zignorowane.

Via http://rachbelaid.com/recursive-regular-experession/

function(n)sort(grep("^(<(?1)*>)(?1)*$",apply(expand.grid(rep(list(60:62),2*n)),1,intToUtf8),,T,T))

Wypróbuj online!

Wyjaśnienie

"^(<(?1)*>)(?1)*$" = regex for balanced <> with no other characters
^ # match a start of the string
  ( # start of expression 1
    < # open <>
       (?1)* # optional repeat of any number of expression 1 (recursive)
  # allows match for parentheses like (()()())(()) where ?1 is (\\((?1)*\\))
    > # close <>
  ) # end of expression 1
  (?1)* # optional repeat of any number of expression 1
$ # end of string

function(n)
  sort(
    grep("^(<(?1)*>)(?1)*$", # search for regular expression matching open and close brackets
      apply(
        expand.grid(rep(list(60:62),2*n)) # generate 3^(2n) 60,61,62 combinations
      ,1,intToUtf8) # turn into all 3^(2n) combinations of "<","=",">"
    ,,T,T) # return the values that match the regex, so "=" gets ignored
  ) # sort them

R , 107 bajtów

Zwykłe podejście rekurencyjne.

-1 dzięki @Giuseppe

f=function(n,x=0:1)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))

Wypróbuj online!

J.Doe
źródło
1
ah, próbowałem znaleźć Mapgolfa, ale nie byłem w stanie owinąć wokół niego głowy. Nie jestem przekonany, że parse+ evalbędzie działać odtąd ()()i tym samym zgłaszać błędy.
Giuseppe,
4

C (gcc) , 114 bajtów

f(n,x,s,a,i){char b[99]={};n*=2;for(x=1<<n;x--;s|a<0||puts(b))for(s=a=i=0;i<n;)a|=s+=2*(b[n-i]=41-(x>>i++&1))-81;}

Wypróbuj online!

Powinien działać dla n <= 15.

Wyjaśnienie

f(n,x,s,a,i){
  char b[99]={};   // Output buffer initialized with zeros.
  n*=2;            // Double n.
  for(x=1<<n;x--;  // Loop from x=2**n-1 to 0, x is a bit field
                   // where 1 represents '(' and 0 represents ')'.
                   // This guarantees lexicographical order.
      s|a<0||puts(b))  // Print buffer if s==0 (as many opening as
                       // closing parens) and a>=0 (number of open
                       // parens never drops below zero).
    for(s=a=i=0;i<n;)  // Loop from i=0 to n-1, note that we're
                       // traversing the bit field right-to-left.
      a|=              // a is the or-sum of all intermediate sums,
                       // it becomes negative whenever an intermediate
                       // sum is negative.
        s+=            // s is the number of closing parens minus the
                       // number of opening parens.
                        x>>i++&1   // Isolate current bit and inc i.
                    41-(        )  // ASCII code of paren, a one bit
                                   // yields 40 '(', a zero bit 41 ')'.
             b[n-i]=               // Store ASCII code in buffer.
          2*(                    )-81;  // 1 for ')' and -1 for '(' since
                                        // we're going right-to-left.
}
nwellnhof
źródło
4

Python 2 , 91 88 84 81 bajtów

f=lambda n:n and sorted({a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)})or['']

Wypróbuj online!

-3 bajty dzięki pizzapantom184

TFeld
źródło
Myślę, że działa również w Pythonie 3
SuperStormer
Możesz zastąpić set(...)zestawem zrozumienia ( {...}) dla -3 bajtów Wypróbuj online!
pizzapants184
@ pizzapants184 Thanks :)
TFeld
3

05AB1E , 13 bajtów

„()©s·ãʒ®õ:õQ

Wypróbuj online lub sprawdź więcej przypadków testowych .

Wyjaśnienie:

„()            # Push string "()"
   ©           # Store it in the register without popping
    s·         # Swap to get the (implicit) input, and double it
      ã        # Cartesian product that many times
       ʒ       # Filter it by:
        ®      #  Push the "()" from the register
         õ:    #  Infinite replacement with an empty string
           õQ  #  And only keep those which are empty after the infinite replacement
Kevin Cruijssen
źródło
3

Rubinowy , 70 bajtów

f=->n{n<1?['']:(0...n).flat_map{|w|f[n-1].map{|x|x.insert w,'()'}}|[]}

Wypróbuj online!

GB
źródło
3

Japt, 15 13 bajtów

ç>i<)á Ôke/<>

Spróbuj


Wyjaśnienie

ç                 :Input times repeat the following string
 >i<              :  ">" prepended with "<"
    )             :End repeat
     á            :Get unique permutations
       Ô          :Reverse
        k         :Remove any that return true (non-empty string)
         e/<>     :  Recursively replace Regex /<>/
Kudłaty
źródło
3

K (ngn / k) , 36 35 bajtów

{"()"(&/-1<+\1-2*)#(x=+/)#+!2|&2*x}

Wypróbuj online!

+!2|&2*x wszystkie wektory binarne o długości 2 * n

(x=+/)# tylko te, które sumują się do n

(&/-1<+\1-2*)# tylko ci, których sumy częściowe, traktując 0/1 jako 1 / -1, nie są nigdzie ujemne

"()" użyj 0/1 jako indeksów w tym ciągu

ngn
źródło
2

Perl 5 -n , 41 39 bajtów

-2 bajty z nawiasami kątowymi

s/<(?R)*>//gr||say for glob'{<,>}'x2x$_

Wypróbuj online!

Port mojej odpowiedzi na Perla 6.

nwellnhof
źródło
2

Perl 6 , 42 bajtów

{grep {!S:g/\(<~~>*\)//},[X~] <( )>xx$_*2}

Wypróbuj online!

Używa wyrażenia regularnego. Alternatywne podstawienie:S/[\(<~~>\)]*//

38 bajtów z 0 i 1 jako symbolami otwarcia / zamknięcia:

{grep {!S:g/0<~~>*1//},[X~] ^2 xx$_*2}

Wypróbuj online!

Wyjaśnienie

{                                        }  # Anonymous block
                              <( )>         # List "(", ")"
                                   xx$_*2   # repeated 2n times
                         [X~]  # Cartesian product with string concat
                               # yields all strings of length 2n
                               # consisting of ( and )
 grep {                },  # Filter strings
        S:g/             # Globally replace regex match
            \(           #   literal (
              <~~>       #   whole regex matched recursively
                  *      #   zero or more times
                   \)    #   literal )
                     //  # with empty string
       !                 # Is empty string?
nwellnhof
źródło
2

Retina 0.8.2 , 50 bajtów

.+
$*
1
11
+%1`1
<$'¶$`>
Gm`^(?<-1>(<)*>)*$(?(1).)

Wypróbuj online! Wykorzystuje <>s. Wyjaśnienie:

.+
$*

Konwertuj na unary.

1
11

Podwój wynik.

+%1`1
<$'¶$`>

Wymień wszystkie 2 inary 2n-bitowe liczby binarne, odwzorowując cyfry na <>.

Gm`^(?<-1>(<)*>)*$(?(1).)

Zachowaj tylko zrównoważone sekwencje. Wykorzystuje to wyważoną sztuczkę w nawiasach odkrytą przez @MartinEnder.

Neil
źródło
2

JavaScript (ES6), 112 102 bajtów

Jest to w dużej mierze oparte na odpowiedzi C. nwellnhofa .

f=(n,i)=>i>>2*n?'':(g=(o,k)=>o[2*n]?s|m<0?'':o:g('()'[m|=s+=k&1||-1,k&1]+o,k/2))(`
`,i,m=s=0)+f(n,-~i)

Wypróbuj online!

Arnauld
źródło
2

Czerwony , 214,184 136 bajtów

func[n][g: func[b n][either n = length? b[if not error? try[load b][print b]return 0][g append copy b"["n g append copy b"]"n]]g""2 * n]

Wypróbuj online!

Wykorzystuje podejście Jo Kinga. Znajduje wszystkie możliwe układy nawiasów za pomocą rekurencji (są one generowane w porządku leksykograficznym) i drukuje je, jeśli układ oceni jako poprawny blok.

Galen Iwanow
źródło
1

Galaretka , 19 bajtów

Ø+xŒ!QÄAƑ>ṪƊ$Ƈ=1ịØ(

Wypróbuj online!

Dane wyjściowe wyjaśnione w odniesieniu do TIO.

Erik the Outgolfer
źródło