길이 n의 Lyndon 단어를 생성하는 Python 프로그램

이 질문에서 우리는 영숫자 문자 배열을 사용하여 모든 Lyndon 단어를 찾습니다.

시작하기 전에 먼저 Lyndon이라는 단어의 정의를 이해해 보겠습니다.

• 모든 단어는 Lyndon 단어이며 엄격히 말하면 모든 주기보다 사전순으로 더 작습니다.

다음은 Lyndon 단어의 예입니다.

• ab - "ab"는 모든 순열 "ba"보다 엄격히 사전순으로 작습니다.

• 89 - '89'의 회전은 '98'이며, 엄밀히 말하면 사전순으로 '89'보다 큽니다.

• abc - 'abc'의 회전은 'bca'와 'cab'이며 엄밀히 말하면 'abc'보다 큽니다.

다음은 Lyndon이 아닌 단어의 예입니다.

• aaa - aaa는 "aaa"의 모든 회전이 동일하기 때문에 린든이 아닌 단어입니다.

• bca - 'bca'는 비린든 단어입니다. 왜냐하면 'abc'는 그것보다 회전이 더 작기 때문입니다,

문제 설명- 영숫자를 포함하는 길이 K의 문자 배열이 제공됩니다. 추가적으로, 양의 정수를 포함하는 n이 주어졌습니다. 과제는 배열에 주어진 영숫자 문자를 사용하여 길이 n의 모든 Lyndon 단어를 찾아야 한다는 것입니다.

예

들어가세요

으아악

출력

으아악

설명- 배열 문자를 사용하여 길이가 3인 모든 Lydon 단어를 생성합니다.

들어가세요

으아악

출력

으아악

설명- "01"은 0과 1을 사용하여 만들 수 있는 유일한 Lyndon 단어입니다.

들어가세요

으아악

출력

으아악

Explanation- a, c, d 문자를 사용하여 길이 2의 Lyndon 단어를 생성합니다.

방법 1

듀발 알고리즘이라는 린든 단어를 생성하는 특별한 알고리즘이 있습니다.

알고리즘

1단계 - Lyndon 단어의 길이를 나타내는 "n" 값과 Lyndon 단어를 생성할 때 사용할 문자가 포함된 chars 배열을 정의합니다.

2단계 - 목록을 정렬합니다.

3단계 − −1로 "인덱스" 목록을 초기화합니다.

4단계 - 인덱스 목록이 비어 있지 않을 때까지 반복합니다.

5단계 - "색인" 목록의 마지막 요소를 1씩 늘립니다.

6단계− list_size가 n과 같으면 목록 값을 인쇄합니다.

7단계 - 길이가 n과 같도록 인덱스를 목록에 추가합니다.

8단계- 목록의 마지막 요소가 배열의 마지막 인덱스와 같으면 목록에서 해당 요소를 제거합니다.

예

예제 입력을 통해 예를 이해해 봅시다.

• 정렬된 목록은 ['a', 'c', 'd']가 됩니다.

• 인덱스 목록은 첫 번째 반복에서 [-1]에서 [0]으로 업데이트됩니다. 이후 인덱스의 길이는 2가 되어 [0, 0]이 됩니다.

• 두 번째 반복에서는 목록이 [0, 1]로 업데이트되고 첫 번째 Lyndon 단어 "ac"를 찾습니다.

• 세 번째 반복에서는 목록이 [0, 2]가 되고 두 번째 Lyndon 단어는 "ad"가 됩니다. 또한 마지막 요소는 array_len -1과 동일하므로 목록에서 제거됩니다.

• 네 번째 반복에서는 목록이 [1]이 됩니다. [1, 1]은 추후 업데이트될 예정입니다.

• 다음 반복에서는 목록이 [1, 2]가 되고 세 번째 Lyndon wor인 'cd'를 찾습니다.

으아악

출력

으아악

시간 복잡도− O(nlogn) 왜냐하면 "문자" 목록을 먼저 정렬해야 하기 때문입니다.

공간 복잡성− 목록에 n개의 인덱스를 저장하므로 O(n)입니다.

Duval 알고리즘은 길이가 n인 Lyndon 단어를 생성하는 가장 효율적인 방법입니다. 그러나 우리는 배열 문자만 사용하도록 메서드를 사용자 정의했습니다.

위 내용은 길이 n의 Lyndon 단어를 생성하는 Python 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!