Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- `[[[[]]]], [[[][]]], [[[]][]], [[][[]]], [[[]]][], [[][][]], [][[[]]],
- [[][]][], [[]][[]], [][[][]], [[]][][], [][[]][], [][][[]], [][][][]`
- nest[n_] :=
- DeleteCases[Quiet[ToExpression /@ (StringReplace[#, "}{" -> "},{"] & /@
- StringJoin /@ Permutations[Flatten@Array[{"{", "}"} &, n], {2 n}])], $Failed]
- DyckWordQ[ s_String ] := With[
- {
- f = StringReplace[
- {
- Shortest[ "[" ~~ Whitespace ~~ "]" ] -> "",
- "[]" -> ""
- }
- ]
- },
- If[
- FixedPoint[ f, s ] === "",
- True,
- False,
- False
- ]
- ]
- DyckWord[ n_Integer ] /; EvenQ[n] := With[
- {
- p = Permutations[ ConstantArray[ 0, n/2 ] ~ Join ~ ConstantArray[ 1, n/2]
- },
- p // RightComposition[
- ReplaceAll[ { 0 -> "[", 1 -> "]" } ],
- Map[ StringJoin ],
- Select[#, DyckWordQ] &
- ]
- ]
- DyckWord[8]
- d = 16
- If[EvenQ[d], StringJoin @@@ (Pick[#, Sign@*Min@*Accumulate /@ #, 0] &[
- Permutations[Join[#, -#] &[ConstantArray[1, d/2]]]] /. {-1 -> "]", 1 -> "["})]
- ClearAll[f]
- f[n_] := f[n, 1, 0, "["]
- f[n_, n_, c_, r_] := {r <> ConstantArray["]", n - c]}
- f[n_, o_, c_, r_] /; c < o :=
- f[n, o + 1, c, r <> "["] ~Join~ f[n, o, c + 1, r <> "]"]
- f[n_, o_, c_, r_] := f[n, o + 1, c, r <> "["]
- f[4]
- {"[[[[]]]]", "[[[][]]]", "[[[]][]]", "[[[]]][]",
- "[[][[]]]", "[[][][]]", "[[][]][]", "[[]][[]]",
- "[[]][][]", "[][[[]]]", "[][[][]]", "[][[]][]",
- "[][][[]]", "[][][][]"}
- (* D24 *)
- f[12] // Length // RepeatedTiming
- {1.15, 208012}
- {6.87, 208012}
- f[u : {a_, x___}, v : {b_, y___}, c___] := f[{x}, v, c, a] ⋃ f[u, {y}, c, b]
- f[{x___}, {y___}, c___] := {{c, x, y}}
- f2[a_, b_] := Union @@ (f[#, b] & /@ a)
- d = 8;
- StringJoin /@ Fold[f2, {{}}, Table[{"[", "]"}, {d/2}]]
- {"[[[[]]]]", "[[[][]]]", "[[[]][]]", "[[[]]][]",
- "[[][[]]]", "[[][][]]", "[[][]][]", "[[]][[]]",
- "[[]][][]", "[][[[]]]", "[][[][]]", "[][[]][]",
- "[][][[]]", "[][][][]"}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement