>  기사  >  백엔드 개발  >  길이 n의 Lyndon 단어를 생성하는 Python 프로그램

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

PHPz
PHPz앞으로
2023-08-31 21:29:05516검색

길이 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
이 기사는 tutorialspoint.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제