9

^{Herausforderung Von hier und auch hier genommen}

Eine Sequenz in n Klammern besteht aus ns ( und ns ) .

Eine gültige Klammerfolge ist wie folgt definiert:

Sie können das Löschen benachbarter Klammerpaare "()" wiederholen, bis es leer wird.

Ist beispielsweise (())eine gültige Klammer, können Sie das Paar an der 2. und 3. Position löschen und es wird (), dann können Sie es leer machen. )()(ist keine gültige Klammer, nachdem Sie das Paar an der 2. und 3. Position )(gelöscht haben , wird es und Sie können nicht mehr löschen

Aufgabe

Wenn Sie eine Zahl n angeben, müssen Sie alle korrekten Klammern in lexikografischer Reihenfolge generieren

Die Ausgabe kann ein Array, eine Liste oder eine Zeichenfolge sein (in diesem Fall eine Sequenz pro Zeile).

Sie können ein anderes Paar von Klammern wie verwenden {}, [], ()oder jede open-close Zeichen

Beispiel

n = 3

((()))    
(()())    
(())()    
()(())    
()()()

n = 2
```
(())
()()
```

code-golf balanced-string Luis felipe De jesus Munoz
quelle

@JoKing Ja natürlich. Ich gehe davon aus, dass das Hauptkonzept der Herausforderung sowieso keinen Unterschied macht.

Luis Felipe De Jesus Munoz

Eh, ich kann mir ein paar Sprachen vorstellen, in denen eval sie zum Beispiel anders interpretieren würde

Jo King

1

Verwandte: Katalanische Zahlen (Ergebnis dieser Herausforderung = Anzahl der Zeilen des Ergebnisses dieser Herausforderung)

user202729

3

Praktisch das gleiche , aber mit einigen seltsamen Einschränkungen wie "Sie dürfen keine rekursiven Funktionen schreiben". /// Eine Obermenge dieser Herausforderung (alle Brain-Flak-Klammern zulassen)

user202729

Bedeutet "ein Array, eine Liste oder eine Zeichenfolge" "von Sequenzen" eines "Open-Close-Zeichens", dass wir eine Liste von Listen mit zwei ganzen Zahlen (wie 1s und -1s) ausgeben können ?

Jonathan Allan

8

Perl 6 , 36 Bytes

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

Probieren Sie es online aus!

Finds alle lexographically Kombinationen sortiert s und filtert diejenigen , die korrekt. Beachten Sie, dass alle gültigen Kombinationen (auch solche wie ) ausgewertet werden (was falsch ist, aber wir es ( ), um von der Rückgabe zu unterscheiden ). $2n$ []EVAL[][][]not!tryNil

Erläuterung:

{                                  }  # 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

Scherzen
quelle

3

Wenn jemand neugierig ist, [][]ist das Zen-Stück eines leeren Arrays, das das Array selbst ergibt. Das Slice kann mehrmals angewendet werden, wird also [][][][]...ausgewertet []. Außerdem wird [[]]aufgrund der Regel mit nur einem Argument kein verschachteltes Array, sondern ein leeres Array erstellt (Sie müssten [[],]für ein verschachteltes Array schreiben ). Jede ausgeglichene Folge von []Klammern führt zu einem leeren Array, das zu false boolifiziert wird.

Nwellnhof

6

R , 112 107 99 Bytes

Nicht rekursiver Ansatz. Wir verwenden "<" und ">", weil dadurch Escapezeichen in der Regex vermieden werden. Um eine kürzere Spezifikation für einen ASCII-Bereich verwenden zu können, generieren wir 3 ^ 2n 2n-Zeichenfolgen von "<", "=" und ">" mit expand.grid(über ihre ASCII-Codes 60, 61 und 62) und grep to Sehen Sie, welche Kombinationen ausgewogene Klammern zum Öffnen und Schließen ergeben. Die "=" - Möglichkeiten werden natürlich ignoriert.

Über 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))

Probieren Sie es online aus!

Erläuterung

"^(<(?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 Bytes

Üblicher rekursiver Ansatz.

-1 danke @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))

Probieren Sie es online aus!

J.Doe
quelle

1

Ah, ich habe versucht, einen MapGolf zu finden , konnte aber meinen Kopf nicht darum wickeln. Ich bin nicht davon überzeugt, dass parse+ evalseitdem funktionieren wird ()()und dergleichen Fehler werfen.

Giuseppe

4

C (gcc) , 114 Bytes

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;}

Probieren Sie es online aus!

Sollte für n <= 15 funktionieren.

Erläuterung

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
quelle

4

Python 2 , 91 88 84 81 Bytes

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

Probieren Sie es online aus!

_{-3 Bytes dank pizzapants184}

TFeld
quelle

Funktioniert auch in Python 3, denke ich

SuperStormer

Sie können durch set(...)ein festgelegtes Verständnis ( {...}) für -3 Bytes ersetzen. Probieren Sie es online aus!

Pizzapants184

@ Pizzapants184 Danke :)

TFeld

3

05AB1E , 13 Bytes

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

Probieren Sie es online aus oder überprüfen Sie weitere Testfälle .

Erläuterung:

„()            # 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
quelle

3

Ruby , 70 Bytes

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

Probieren Sie es online aus!

GB
quelle

3

Japt, 15 13 Bytes

ç>i<)á Ôke/<>

Versuch es

Erläuterung

ç                 :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 /<>/

Zottelig
quelle

3

K (ngn / k) , 36 35 Bytes

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

Probieren Sie es online aus!

+!2|&2*x alle binären Vektoren der Länge 2 * n

(x=+/)# nur diejenigen, die zu n summieren

(&/-1<+\1-2*)# Nur diejenigen, deren Teilsummen 0/1 als 1 / -1 behandeln, sind nirgends negativ

"()" Verwenden Sie 0/1 als Indizes in dieser Zeichenfolge

ngn
quelle

2

Perl 5 `-n` , 41 39 Bytes

-2 Bytes mit spitzen Klammern

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

Probieren Sie es online aus!

Port meiner Perl 6 Antwort.

nwellnhof
quelle

2

Perl 6 , 42 Bytes

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

Probieren Sie es online aus!

Verwendet einen rekursiven regulären Ausdruck. Alternative Substitution:S/[$<~~>$]*//

38 Bytes mit 0 und 1 als Öffnungs- / Schließsymbolen:

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

Probieren Sie es online aus!

Erläuterung

{                                        }  # 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
quelle

2

Retina 0,8,2 , 50 Bytes

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

Probieren Sie es online aus! Verwendet <>s. Erläuterung:

.+
$*

In unary konvertieren.

1
11

Verdoppeln Sie das Ergebnis.

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

Zählen Sie alle 2²ⁿ 2n-Bit-Binärzahlen auf und ordnen Sie die Ziffern zu <>.

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

Halten Sie nur ausgewogene Sequenzen. Dies verwendet einen von @MartinEnder entdeckten Trick mit ausgewogenen Klammern.

Neil
quelle

2

JavaScript (ES6), 112 102 Byte

Dies basiert stark auf der C-Antwort von nwellnhof .

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)

Probieren Sie es online aus!

Arnauld
quelle

2

Rot , 214, 184, 136 Bytes

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]

Probieren Sie es online aus!

Verwendet Jo Kings Ansatz. Findet alle möglichen Anordnungen von Klammern mithilfe der Rekursion (sie werden in lexikografischer Reihenfolge generiert) und druckt sie aus, wenn die Anordnung als gültiger Block ausgewertet wird.

Galen Ivanov
quelle

1

Gelee , 19 Bytes

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

Probieren Sie es online aus!

Ausgabe über TIO geklärt.

Erik der Outgolfer
quelle

Klammern Sequenzen in lexikographischer Reihenfolge

Antworten:

Perl 6 , 36 Bytes

Erläuterung:

R , 112 107 99 Bytes

Erläuterung

R , 107 Bytes

C (gcc) , 114 Bytes

Erläuterung

Python 2 , 91 88 84 81 Bytes

05AB1E , 13 Bytes

Ruby , 70 Bytes

Japt, 15 13 Bytes

Erläuterung

K (ngn / k) , 36 35 Bytes

Perl 5 `-n` , 41 39 Bytes

Perl 6 , 42 Bytes

Erläuterung

Retina 0,8,2 , 50 Bytes

JavaScript (ES6), 112 102 Byte

Rot , 214, 184, 136 Bytes

Gelee , 19 Bytes

Klammern Sequenzen in lexikographischer Reihenfolge

Antworten:

Perl 6 , 36 Bytes

Erläuterung:

R , 112 107 99 Bytes

Erläuterung

R , 107 Bytes

C (gcc) , 114 Bytes

Erläuterung

Python 2 , 91 88 84 81 Bytes

05AB1E , 13 Bytes

Ruby , 70 Bytes

Japt, 15 13 Bytes

Erläuterung

K (ngn / k) , 36 35 Bytes

Perl 5 -n , 41 39 Bytes

Perl 6 , 42 Bytes

Erläuterung

Retina 0,8,2 , 50 Bytes

JavaScript (ES6), 112 102 Byte

Rot , 214, 184, 136 Bytes

Gelee , 19 Bytes

Perl 5 `-n` , 41 39 Bytes