{PatternSequence [1, PatternSequence [2, 3 ..] ..] ..} के लिए तेज़ विकल्प बनाना

Question

मुझे एक पैटर्न में सुधार करने या एक दृष्टिकोण बदलने की आवश्यकता है।

यह सबसे अच्छा एक उदाहरण द्वारा वर्णित है

सूची द्वारा दिए गए पदानुक्रम / आदेश के लिए जैसे:

order = {1, 2, 3} 

और एक सूची:

list = {
  1, 2, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3,
   3, 3, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3
  }

मुझे यह सत्यापित करने की आवश्यकता है कि इसके listद्वारा परिभाषित अनुक्रम से मेल खाता है order:

MatchQ[list, {PatternSequence[1, PatternSequence[2, 3 ..] ..] ..}]

यह पैटर्न बहुत खराब तरीके से लागू होता है, पहले से ही एक का मूल्यांकन खत्म नहीं होगा।

फ़ंक्शन को केवल listतर्क के रूप में लेना चाहिए , ऑर्डर को स्थिर मानें। पैटर्न को स्वचालित रूप से निर्माण करने की आवश्यकता नहीं है।

Answer 1

निम्नलिखित मेरे लिए काम करता है, जब तक कि मुझे कुछ याद न हो:

ClearAll[match]
match[{}][{}] := True;
match[{fst_, rest___}][l_List] :=
  And @@ Map[
    Replace[
      match[{rest}][#], 
      False :> Return[False, Map]
    ]&,
    Replace[
      ReplaceList[
        l, 
        {
          {___, fst, middle : Except[fst] ..., fst, ___} :> {middle}, 
          {___, fst, r : Except[fst] ...} :> {r}
        }
      ],
      {} -> False
    ]
 ]

(भाग Replace[match[{rest}][#], False :> Return[False, Map]]&वैकल्पिक है और सिद्धांत रूप में बस के साथ बदला जा सकता है match[{rest}])।

उदाहरण:

match[{1, 2, 3}][list] // AbsoluteTiming
match[{1, 2, 3}][Append[list, 1]] // AbsoluteTiming

(* {0.00038, True} *)

(* {0.000383, False} *)

Answer 2

यह समाधान एक प्रकार के तत्वों की सूची में सूची को कम करने की कोशिश करता है, अगर यह सफल होता है तो सूची निर्धारित पैटर्न का पालन कर रही है।

MatchQ[
  SequenceReplace[
   SequenceReplace[list, {2, 3 ..} :> x],
   {1, x ..} :> y
   ],
  {y ..}
  ] // AbsoluteTiming

{0.0019598, True}

यह स्टेट मशीन पर एक टिप्पणी है जिसे डैनियल ने एक टिप्पणी में सुझाया है:

f[1, 2] = 2;
f[2, 3] = 3;
f[3, 2] = 2;
f[3, 1] = 1;
f[3, 3] = 3;
f[_, _] := Throw[False]

And[
  First[list] == 1 && Last[list] == 3,
  Catch[Fold[f, list]; True]
] // AbsoluteTiming

{0.0000455, True}