순열 패턴 피하기 - 231 스킴이없는 모든 순열 인쇄

Question

입력에서 순열의 크기 인 "n"숫자가 있고 가능한 모든 순열 (n은 1부터) 그러나 나는 "231 계획"에 사람을 거부해야한다

"231 계획은"순열에서 우리는 세 개의 연속 번호 불평등 Z에 적용됩니다 (x, y, z)를 찾을 수 있다는 것을 의미한다 (1 < 2 < 3) .

예를 들어 n = 4 인 경우 4! = 24 순열. 그들은 241

3412, 3421을 가지고 있기 때문에 - -가 (341)을 가지고 있기 때문에 (그리고 그들은 231

2413 , 3241을 가지고 있기 때문에 - 우리는

• 4231, 2431, 2341, 2314
  ... 그들 중 아홉 거부 342)
• 1342 - 그것은 342

을 가지고 ... 그리고 다른 다섯 posibilities를 인쇄하기 때문이다.

좋습니다. 문제가 있습니다. 나는 이미 많은 시간을이 일에 대해 생각해 보았다. 그리고 다음과 같은 것을 알아 냈습니다 :

n = 3, reject 231, 그리고 (n = 4의 경우) 순열을 생성하여 이전에 생성 된 것들을 기반으로 모든 가능성을 생성 할 수 있습니다.

그럼 132 순열을 선택하겠습니다. 이제 우리는 가능한 모든 방법으로 4를 "삽입"합니다. 4132, 1432, 1342, 1324. 첫 번째 및 마지막 순열이 잘되므로 다른 두 가지를 더 자세히 살펴야합니다. 그리고 제 아이디어는 "4"의 왼쪽에있는 숫자에서 가장 높은 숫자를 찾고, "4"의 오른쪽에 서있는 숫자에서 최소값을 찾는 것입니다. 그리고 left_max> right_min이라면 우리는 "231 scheme"을 가지고 있습니다.

예를 들어 순열 1342 : left_max = 3, right_min = 2이므로 올바른 "231"이며 최종 답에서 제외합니다.

의견, 아이디어 및 팁에 대해 매우 감사드립니다. 내 아이디어가 쓸모 없게 될 수도 있다는 것을 알지만, 그것이 내가 가진 최선입니다. 그래서 다른 어떤 (더 똑똑하고/또는 더 복잡한) 방법이 있습니까?

Answer 1

당신은 맞는 생각이 있습니다. 1을 n까지 추가하여 순열을 반복적으로 작성하십시오. i을 추가 할 때 피해야 할 패턴이 이고 i이 아닌지 확인해야합니다.

예를 들어 패턴이 231 인 경우 i의 왼쪽에있는 문자가 i의 오른쪽에있는 문자보다 크지 않은지 확인합니다.

모든 결과를 생성하는 대신 인쇄하지 않으면 (저장 문제를 피할 수 있음) 사전 순열을 수행 할 수 있습니다. 접두사를 스캔하고 패턴이 존재하는 경우 언제든지 (예 : 첫 번째 k 글자에 다음 접두어로 이동하십시오. 이렇게하면 반복 속도가 빨라집니다.