Tanda kurung dalam urutan leksikografis

9

Tantangan Diambil dari sini dan juga di sini

Sebuah n urutan kurung terdiri dari n ( dan n ) s.

Urutan tanda kurung yang valid didefinisikan sebagai berikut:

Anda dapat menemukan cara untuk menghapus pasangan kurung yang berdekatan "()" hingga menjadi kosong.

Misalnya, (())adalah tanda kurung yang valid, Anda dapat menghapus pasangan pada posisi ke-2 dan ke-3 dan menjadi (), lalu Anda dapat membuatnya kosong. )()(bukan tanda kurung yang valid, setelah Anda menghapus pasangan pada posisi 2 dan 3, itu menjadi )(dan Anda tidak dapat menghapus lagi

Tugas

Dengan nomor dan Anda perlu membuat semua urutan kurung yang benar dalam urutan leksikografis

Output dapat berupa array, daftar atau string (dalam hal ini urutan per baris)

Anda dapat menggunakan sepasang yang berbeda dari kurung seperti {}, [], ()atau buka-tutup tanda

Contoh

  • n = 3

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

    (())
    ()()
    
Luis felipe De jesus Munoz
sumber
@ Mengajak Ya tentu saja. Saya berasumsi bahwa tidak akan ada bedanya dengan konsep utama tantangan.
Luis felipe De jesus Munoz
Eh, saya bisa memikirkan beberapa bahasa di mana eval akan menafsirkannya secara berbeda misalnya
Jo King
1
Terkait: Bilangan Catalan (hasil dari tantangan itu = jumlah garis hasil dari tantangan ini)
user202729
3
Hampir sama , tetapi dengan beberapa batasan aneh seperti "Anda mungkin tidak menulis fungsi rekursif". /// Superset dari tantangan ini (izinkan semua kurung Brain-Flak)
user202729
Apakah "sebuah array, daftar atau string" "dari urutan" dari "tanda buka-tutup" berarti kita dapat menampilkan daftar daftar dua bilangan bulat (seperti 1s dan -1s)?
Jonathan Allan

Jawaban:

8

Perl 6 , 36 byte

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

Cobalah online!

2n []EVAL[][][]not!tryNil

Penjelasan:

{                                  }  # 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
sumber
3
Jika ada yang penasaran, [][]adalah potongan Zen dari array kosong yang menghasilkan array itu sendiri. Iris dapat diterapkan beberapa kali, jadi [][][][]...dievaluasi untuk []. Selain itu, [[]]tidak membangun array bersarang tetapi array kosong karena aturan argumen tunggal (Anda harus menulis [[],]untuk array bersarang). Jadi setiap urutan []kurung yang seimbang menghasilkan array kosong yang boolify menjadi false.
nwellnhof
6

R , 112 107 99 byte

Pendekatan non-rekursif. Kami menggunakan "<" dan ">" karena itu menghindari karakter melarikan diri di regex. Untuk memungkinkan kami menggunakan spesifikasi yang lebih pendek untuk rentang ASCII, kami menghasilkan string 3 <2n 2n-karakter "<", "=" dan ">" menggunakan expand.grid(melalui kode ASCII mereka 60, 61 dan 62) dan kemudian beralih ke lihat kombinasi mana yang memberikan tanda kurung buka dan tutup seimbang. Kemungkinan "=" akan diabaikan, tentu saja.

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

Cobalah online!

Penjelasan

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

Pendekatan rekursif biasa.

-1 terima kasih @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))

Cobalah online!

J.Apakah
sumber
1
ah, saya sedang berusaha menemukan Mapgolf tetapi tidak bisa membungkus kepala saya. Saya tidak yakin parse+ evalakan bekerja karena ()()dan kesalahan melempar sejenisnya.
Giuseppe
4

C (gcc) , 114 byte

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

Cobalah online!

Harus bekerja untuk n <= 15.

Penjelasan

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
sumber
4

Python 2 , 91 88 84 81 byte

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

Cobalah online!

-3 byte berkat pizzapants184

TFeld
sumber
Juga bekerja di Python 3, saya pikir
SuperStormer
Anda dapat menggantinya set(...)dengan seperangkat pemahaman ( {...}) untuk -3 byte Cobalah secara online!
pizzapants184
@ pizzapants184 Terima kasih :)
TFeld
3

05AB1E , 13 byte

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

Cobalah secara online atau verifikasi beberapa kasus uji lagi .

Penjelasan:

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

Ruby , 70 byte

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

Cobalah online!

GB
sumber
3

Japt, 15 13 byte

ç>i<)á Ôke/<>

Cobalah


Penjelasan

ç                 :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 /<>/
Shaggy
sumber
3

K (ngn / k) , 36 35 byte

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

Cobalah online!

+!2|&2*x semua vektor biner dengan panjang 2 * n

(x=+/)# hanya yang berjumlah n

(&/-1<+\1-2*)# hanya mereka yang jumlah parsialnya, yang memperlakukan 0/1 sebagai 1 / -1, tidak negatif

"()" gunakan 0/1 sebagai indeks dalam string ini

ngn
sumber
2

Perl 5 -n , 41 39 byte

-2 byte dengan kurung sudut

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

Cobalah online!

Port jawaban Perl 6 saya.

nwellnhof
sumber
2

Perl 6 , 42 byte

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

Cobalah online!

Menggunakan regex rekursif. Substitusi alternatif:S/[\(<~~>\)]*//

38 byte dengan 0 dan 1 sebagai simbol buka / tutup:

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

Cobalah online!

Penjelasan

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

Retina 0.8.2 , 50 byte

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

Cobalah online! Penggunaan <>s. Penjelasan:

.+
$*

Konversikan ke unary.

1
11

Gandakan hasilnya.

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

Hitung semua angka biner 2²ⁿ 2n-bit, pemetaan digit <>.

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

Simpan hanya urutan yang seimbang. Ini menggunakan trik kurung seimbang yang ditemukan oleh @MartinEnder.

Neil
sumber
2

JavaScript (ES6), 112 102 byte

Ini sangat didasarkan pada jawaban C 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)

Cobalah online!

Arnauld
sumber
2

Merah , 214, 184 136 byte

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]

Cobalah online!

Menggunakan pendekatan Jo King. Temukan semua pengaturan braket yang memungkinkan menggunakan rekursi (mereka dihasilkan dalam urutan leksikografis) dan cetaklah jika pengaturan dievaluasi sebagai blok yang valid.

Galen Ivanov
sumber
1

Jelly , 19 byte

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

Cobalah online!

Output diklarifikasi atas TIO.

Erik the Outgolfer
sumber