주어진 시작 지점과 끝 지점을 사용하여 모든 경로 생성

Question

이것은 간단한 문제처럼 보였지만 실제로 코드에 구현하면 많은 문제가 발생합니다. 길이가 L 인 모든 가능한 경로를 반복하는 Python 루프를 작성하려고합니다.

이 경로의 첫 번째 노드는 0이어야하며 마지막 노드는 n - 1의 정수 여야합니다. 첫 번째 노드와 마지막 노드 사이의 모든 노드는 [0 , n-1]에있는 모든 정수가 될 수 있지만 앞에있는 한 노드와 그 노드를 이어가는 노드와 구별되어야합니다.

n가 [2, 7]의 정수일 수 있고 L이 될 수있는 임의의 정수> = 3

예를 들어, n = 4 및 L = 3 경우 루프 n = 4 들어

[ 0, 1, 3] 
[ 0, 2, 3] 

을 반복해야하고, L = 4 루프가 반복되어야 함

[ 0, 1, 0, 3] 
[ 0, 1, 2, 3] 
[ 0, 2, 0, 3] 
[ 0, 2, 1, 3] 
[ 0, 3, 0, 3] 
[ 0, 3, 1, 3] 
[ 0, 3, 2, 3] 

이 경로를 생성하기 위해 생각한 프로세스는 다음과 같습니다.

1. 0부터 (n - 1)^(L-3)까지의 모든 숫자를 반복합니다.
2. 숫자를 기본으로 변환합니다. n - 1
3. 길이가 L - 3이 될 때까지 왼쪽으로 0을 추가하여 문자열로 변환합니다.
4. 이 숫자 각각에 대해 [0, n-2] 모든 숫자를 반복하고 그 숫자를 오른쪽에 추가하십시오. 이러한 우리의 path_ids
5. 시작에게 첫 번째 노드로 새로운 경로를 호출 [0] path_id의 각 숫자에
6. 하지만, 마지막에 x[ digit]을 x에서 경로의 이전 노드를 제거하고 추가, 목록 x = range(n)을 만들려면 경로
7. 경로 ID의 마지막 숫자는 x = range(n) 경로의 마지막 노드를 제거하고 n-1을 x에서 x[ digit] 경로에 추가하십시오.
8. n-1 경로 끝에 추가하십시오.

이것은 내 문제에 대해 매우 복잡한 프로세스 인 것 같아서 코드를 사용할 수 없게되는 속도를 늦출 수 있습니다. 나는 이것을 할 수있는 간단한 방법을 찾고있다. 이 프로세스는 가능한 모든 경로 길이의 반복 내에서 수행되며 생성 된 각 경로를 반복하고 특정 조건을 충족하는지 확인합니다. 그렇다면 저장합니다. 그런 다음 조건을 충족시키는 모든 경로를 반복하고 최상의 조건을 확인합니다. 가능성이 많은 '최상의'경로가 있으므로 정렬해야합니다. 상상할 수 있듯이이 기능을 비효율적으로 작성하면 프로그램 전체가 느려질 수 있습니다.

나는 포맷을 도살 한 것에 대해 사과합니다. 잠시 동안 숨어 있었지만, 이것이 제가 스스로에게 묻는 첫 번째 질문입니다.

Answer 1

당신은 itertools.product(range(n-1), repeat=L-2)을 원합니다. 그런 다음 각 조합 모듈 n의 누적 합계를 계산합니다 (1부터 시작).이렇게하면 끝에있는 것을 제외한 모든 중복을 피할 수 있습니다.

의 (a 질문자가 반복되지 않는 임의의 숫자를 원 할 때 나는이 제안 보았다하지만 내가 다시 찾을 수 있는지. 내가 링크를 게시합니다. 여기뿐만 아니라 작동)