Advertisement
Guest User

Untitled

a guest
Mar 27th, 2017
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.94 KB | None | 0 0
  1. `[[[[]]]], [[[][]]], [[[]][]], [[][[]]], [[[]]][], [[][][]], [][[[]]],
  2. [[][]][], [[]][[]], [][[][]], [[]][][], [][[]][], [][][[]], [][][][]`
  3.  
  4. nest[n_] :=
  5. DeleteCases[Quiet[ToExpression /@ (StringReplace[#, "}{" -> "},{"] & /@
  6. StringJoin /@ Permutations[Flatten@Array[{"{", "}"} &, n], {2 n}])], $Failed]
  7.  
  8. DyckWordQ[ s_String ] := With[
  9. {
  10. f = StringReplace[
  11. {
  12. Shortest[ "[" ~~ Whitespace ~~ "]" ] -> "",
  13. "[]" -> ""
  14. }
  15. ]
  16. },
  17. If[
  18. FixedPoint[ f, s ] === "",
  19. True,
  20. False,
  21. False
  22. ]
  23. ]
  24.  
  25. DyckWord[ n_Integer ] /; EvenQ[n] := With[
  26. {
  27. p = Permutations[ ConstantArray[ 0, n/2 ] ~ Join ~ ConstantArray[ 1, n/2]
  28. },
  29. p // RightComposition[
  30. ReplaceAll[ { 0 -> "[", 1 -> "]" } ],
  31. Map[ StringJoin ],
  32. Select[#, DyckWordQ] &
  33. ]
  34. ]
  35.  
  36. DyckWord[8]
  37.  
  38. d = 16
  39. If[EvenQ[d], StringJoin @@@ (Pick[#, Sign@*Min@*Accumulate /@ #, 0] &[
  40. Permutations[Join[#, -#] &[ConstantArray[1, d/2]]]] /. {-1 -> "]", 1 -> "["})]
  41.  
  42. ClearAll[f]
  43.  
  44. f[n_] := f[n, 1, 0, "["]
  45.  
  46. f[n_, n_, c_, r_] := {r <> ConstantArray["]", n - c]}
  47.  
  48. f[n_, o_, c_, r_] /; c < o :=
  49. f[n, o + 1, c, r <> "["] ~Join~ f[n, o, c + 1, r <> "]"]
  50.  
  51. f[n_, o_, c_, r_] := f[n, o + 1, c, r <> "["]
  52.  
  53. f[4]
  54.  
  55. {"[[[[]]]]", "[[[][]]]", "[[[]][]]", "[[[]]][]",
  56. "[[][[]]]", "[[][][]]", "[[][]][]", "[[]][[]]",
  57. "[[]][][]", "[][[[]]]", "[][[][]]", "[][[]][]",
  58. "[][][[]]", "[][][][]"}
  59.  
  60. (* D24 *)
  61.  
  62. f[12] // Length // RepeatedTiming
  63.  
  64. {1.15, 208012}
  65.  
  66. {6.87, 208012}
  67.  
  68. f[u : {a_, x___}, v : {b_, y___}, c___] := f[{x}, v, c, a] ⋃ f[u, {y}, c, b]
  69.  
  70. f[{x___}, {y___}, c___] := {{c, x, y}}
  71.  
  72. f2[a_, b_] := Union @@ (f[#, b] & /@ a)
  73.  
  74. d = 8;
  75.  
  76. StringJoin /@ Fold[f2, {{}}, Table[{"[", "]"}, {d/2}]]
  77.  
  78. {"[[[[]]]]", "[[[][]]]", "[[[]][]]", "[[[]]][]",
  79. "[[][[]]]", "[[][][]]", "[[][]][]", "[[]][[]]",
  80. "[[]][][]", "[][[[]]]", "[][[][]]", "[][[]][]",
  81. "[][][[]]", "[][][][]"}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement