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

이것은 Daniel이 코멘트에서 추천 한 상태 머신에 대한 것입니다.

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}