1-N의 전체 순열을 비재귀적으로 출력하는 방법에 대한 자세한 설명

다음 편집기는 1-N(권장)을 출력하는 비재귀적 완전 순열 예제를 제공합니다. 에디터가 꽤 좋다고 생각해서 지금 공유해서 참고용으로 올려보겠습니다.

NetEase 게임 작성 테스트의 알고리즘 문제 중 하나는 C++, Java 또는 Python으로 작성할 수 있으므로 Python 코드의 양이 적기 때문에 Python을 선택했습니다. 언어.

알고리즘의 일반적인 아이디어는 1, 2, 3...N의 배열부터 시작하여 N, N-1,...1이 될 때까지 다음 배열을 계속 계산하는 것입니다. 출력

그럼 주어진 순열에 대해 다음 순열을 계산하는 방법은 무엇일까요?

수열 [2, 3, 5, 4, 1]을 고려하여 뒤에서 앞으로 증가하는 인접 숫자의 첫 번째 쌍, 즉 3, 5를 찾습니다. 그러면 3이 대체 숫자이고, 3의 위치가 대체 지점입니다.

3보다 큰 대체점 다음으로 가장 작은 숫자로 3을 교환합니다. 여기서는 4이므로 [2,4,5,3,1]을 얻습니다. 그런 다음 교체 지점 이후의 첫 번째 숫자와 마지막 숫자를 교환합니다. 즉, 5,1을 교환합니다. 다음 시퀀스 [2, 4, 1, 3, 5]

코드는 다음과 같습니다.

def arrange(pos_int):
  #将1-N放入列表tempList中，已方便处理
  tempList = [i+1 for i in range(pos_int)]
  print(tempList)

  while tempList != [pos_int-i for i in range(pos_int)]:
    for i in range(pos_int-1,-1,-1):
      if(tempList[i]>tempList[i-1]):
        #考虑tempList[i-1]后面比它大的元素中最小的，交换。
        minmax = min([k for k in tempList[i::] if k > tempList[i-1]])
        #得到minmax在tempList中的位置
        index = tempList.index(minmax)
        #交换
        temp = tempList[i-1]
        tempList[i-1] = tempList[index]
        tempList[index] = temp

        #再交换tempList[i]和最后一个元素，得到tempList的下一个排列
        temp = tempList[i]
        tempList[i] = tempList[pos_int-1]
        tempList[pos_int-1] = temp

        print(tempList)
        break
arrange(5)

위 내용은 1-N의 전체 순열을 비재귀적으로 출력하는 방법에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!