배열 문제
제목:
배열을 지정하여 배열의 모든 배열을 출력합니다.예를 들어 수조가 [1, 2, 3]이면 최종 출력은 다음과 같다.
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
수조의 모든 순서를 출력할 수 있는 것이다.
문제 풀이 사고방식
1. 귀속 해법
생각
귀착의 취지 사상은 문제를 한 개 또는 몇 개의 더 작은 규모의 하위 문제로 바꾸는 것이다. 예를 들어 [1,2,3]의 전체 배열이 처리하기 어렵다. 그러면 우리는 첫 번째 배열을 1로 고정한 다음에 [2,3]의 전체 배열을 구한 다음에 첫 번째 배열을 2로 고정하고 [1,3]의 전체 배열을 구한다. 마지막으로 첫 번째 배열을 3, [1,2]의 전체 배열로 고정한다.이렇게 층층이 추론하면 제목을 길이가 1인 수조의 전체 배열로 바꿀 수 있어 분명히 답을 얻을 수 있다.
진일보한 해석
위의 사상은 기본적으로 아무런 문제가 없다. 그러나 어떻게 고정 1위를 실현할 수 있겠는가. 여기에 비교적 교묘한 방법이 있다. 바로 첫 번째 자리와 두 번째 자리를 교환하는 것이다. 이렇게 하면 모든 숫자는 첫 번째 자리에 한 번 고정된 다음에 다음 다음 순서로 돌아가 조작을 한다. 현재의 수조를 복용하기 위해 매번 값 복사를 하지 않고 매번 순서가 끝나면 이전의 순서를 바꾸어야 한다.이렇게 하면 한 부모 문제가 여러 개의 하위 문제를 처리할 때 어떤 하위 문제로 인해 수조의 순서가 바뀌지 않고 다음 하위 문제를 처리할 수 없게 된다. 구체적으로 다음 코드를 보자.
def _all_sort(arr: list, start: int, _len: int):
"""
:param arr:
:param start: start
:param _len:
"""
for i in range(start, _len):
# ，
if start == _len - 1:
print(arr)
else:
# start
arr[i], arr[start] = arr[start], arr[i]
# start 1，
_all_sort(arr, start+1, _len)
# ， ，
arr[i], arr[start] = arr[start], arr[i]
def all_sort(arr: list):
# 0
start = 0
_len = len(arr)
_all_sort(arr, start, _len)
if __name__ == '__main__':
arr = [1, 2, 4]
all_sort(arr)
# [1, 2, 4]
# [1, 4, 2]
# [2, 1, 4]
# [2, 4, 1]
# [4, 2, 1]
# [4, 1, 2]
중복 문제 발생
위의 코드는 수조에 중복 요소가 없을 때 운행하는 것이 정상적이지만 중복이 있으면 작은 문제가 발생할 수 있습니다. arr가 [1,2,2]인 실행 결과를 보겠습니다.
# [1, 2, 2]
# [1, 2, 2]
# [2, 1, 2]
# [2, 2, 1]
# [2, 2, 1]
# [2, 1, 2]
발견, 일부 조합은 중복된다. 이런 상황에 대해 필터를 해야 한다. [1,2,2]로 예를 들어 1과 첫 번째 2가 교환될 때 정상적으로 교환되지만 1과 두 번째 2가 교환될 때 이전에 2와 교환한 적이 있는지 판정해야 한다. 이를 바탕으로 코드를 업그레이드하자.
def _all_sort(arr: list, start: int, _len: int):
for i in range(start, _len):
if start == _len - 1:
print(arr)
#
elif i == start:
_all_sort(arr, start + 1, _len)
else:
#
is_mutil = False
for j in range(start, i):
if arr[j] == arr[i]:
is_mutil = True
break
# ，
if is_mutil is True:
continue
arr[i], arr[start] = arr[start], arr[i]
_all_sort(arr, start+1, _len)
arr[i], arr[start] = arr[start], arr[i]
def all_sort(arr: list):
start = 0
_len = len(arr)
_all_sort(arr, start, _len)
if __name__ == '__main__':
arr = [1, 2, 2]
all_sort(arr)
print()
arr = [1, 1, 2, 2]
all_sort(arr)
위의 코드를 실행하여 결과를 얻습니다.
# [1, 2, 2]
# [2, 1, 2]
# [2, 2, 1]
#
# [1, 1, 2, 2]
# [1, 2, 1, 2]
# [1, 2, 2, 1]
# [2, 1, 1, 2]
# [2, 1, 2, 1]
# [2, 2, 1, 1]
이렇게 하면 중복 데이터가 있는 문제를 성공적으로 해결했지만 시간의 복잡도를 향상시켰다. nn에서 n(n+1)으로 올라가면 집합을 통해 중복 데이터가 있는지 판정할 수 있다. 그러나 이렇게 하면 프로그램의 공간 복잡도를 높이고 더 많은 메모리를 소모할 수 있으며 귀속 층수가 증가함에 따라 이 공간의 복잡도도 증가할 것이다.
1. 비귀속 해법
왜 비귀속 알고리즘을 써야 합니까
많은 언어들이 코드 오류로 인해 귀속이 출구가 없는 문제를 해결하기 위해 귀속 층수에 대해 엄격한 제한을 가진다. 예를 들어python은 귀속 층수가 1000을 초과할 때 프로그램이 오류가 발생한다. 예를 들어 위의 귀속 방법은 길이가 1001인 그룹의 전체 배열 문제를 해결할 수 없다.
생각
수조를 하나의 숫자로 삼아 작은 것부터 큰 것까지의 순서에 따라 찾는다. 예를 들어 수조[1,2,3]. 우리는 작은 것부터 큰 것까지 모두 배열한다. 우리는 가장 작은 숫자를 123으로 찾았고 그 다음은 132이다. 그리고 213, 321, 312, 321을 찾았다. 그러면 수조의 모든 배열을 찾았다.위의 사고방식은 어떻게 실현됩니까?우선, 정렬을 통해 수조를 승순으로 배열하면 수조가 표시하는 수조는 틀림없이 가장 작은 숫자일 것이다. 왜냐하면 어떤 두 개의 위치가 교환되든지 고위숫자가 커지고 저위숫자가 작아지며 최종적으로 전체 숫자가 커지기 때문이다.다음에 우리는 기본 수조가 질서정연하고 현재 숫자보다 조금 큰 숫자를 찾기 시작한다. 예를 들어 지금은 123이다. 그러면 일정한 방식으로 132를 얻어야 한다. 그러면 우리는 어떻게 해야 하는가. 먼저 방법을 보고 원인을 설명한다.
1. 뒤에서 앞으로 찾으면 현재 숫자가 뒤에 있는 숫자보다 크면 검색을 멈추고 현재 index를 기록한다. 예를 들어 2, 4, 3, 1이 뒤에서 앞으로 가면 2, 4를 찾을 때 조건에 부합된다. 2라는 숫자를curr_num, 2의 위치를curr_index.
2,curr_ 찾기index 뒤에 있는curr_보다 큰 숫자num의 숫자 중 최소수, large_min_num,large_min_num의 위치는 large_min_index, 그리고curr_index 및 large_min_index 숫자를 교환합니다.예를 들어 2, 4, 3, 1, 이럴 때 숫자 2가curr_index, 그 뒤에 있는 3, 4는 모두 2보다 크다. 그 중에서 가장 작은 값을 취하면 3이기 때문에large_min_num은 3입니다. 그리고 2와 3을 교환하면 서열 3, 4, 2, 1을 얻을 수 있습니다.
3、curr_index 이후의 수조 역순 배열은 위에서 3, 4, 2, 1, 3의 위치를 얻은 후의 4, 2, 1 역순으로 얻어진 결과는 3, 1, 2, 4이다. 이 서열은 2, 4, 3, 1보다 큰 서열이다. 이렇게 계속 현재 서열에서 교체되고 큰 서열을 찾게 된다. 최종적으로 현재 서열보다 더 큰 서열을 찾지 못하면 검색을 멈추고 모든 배열을 찾게 된다.
위의 몇 걸음은 서술이 편리하도록 아래의 문장은 단계 1, 2, 3이라고 약칭한다.우리는 이 몇 가지 절차를 통해 1, 2, 3 서열의 모든 배열을 찾아내려고 한다.
def all_sort(arr: list):
tmp_arr = arr.copy()
tmp_arr.sort()
_len = len(tmp_arr)
while 1:
is_change = False
print(arr)
for i in range(_len-2, -1, -1):
if arr[i] < arr[i+1]:
swap_num(arr, i)
reverse_arr(arr, i+1)
is_change = True
break
if is_change is False:
break
def swap_num(arr: list, index: int):
length = len(arr)
num = arr[index]
compare_start = index + 1
result = arr[compare_start]
compare_index = compare_start
for i in range(compare_start, length):
if num < arr[i] <= result:
result = arr[i]
compare_index = i
arr[index], arr[compare_index] = arr[compare_index], arr[index]
def reverse_arr(arr: list, start: int):
left, right = start, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
if __name__ == '__main__':
arr = [1, 2, 3, 4]
all_sort(arr)
# [1, 2, 3, 4]
# [1, 2, 4, 3]
# [1, 3, 2, 4]
# [1, 3, 4, 2]
# [1, 4, 2, 3]
# [1, 4, 3, 2]
# [2, 1, 3, 4]
# [2, 1, 4, 3]
# [2, 3, 1, 4]
# [2, 3, 4, 1]
# [2, 4, 1, 3]
# [2, 4, 3, 1]
# [3, 1, 2, 4]
# [3, 1, 4, 2]
# [3, 2, 1, 4]
# [3, 2, 4, 1]
# [3, 4, 1, 2]
# [3, 4, 2, 1]
# [4, 1, 2, 3]
# [4, 1, 3, 2]
# [4, 2, 1, 3]
# [4, 2, 3, 1]
# [4, 3, 1, 2]
# [4, 3, 2, 1]
우리가 보기에 왜 이렇게 하면 현재 숫자보다 조금 큰 수를 찾을 수 있는지 살펴보자. 1, 4, 3, 2 이 서열을 예로 들면 뒤에서 대비하고 1, 4까지 이 서열이 멈추고 1이라는 위치로 위치를 정할 수 있다. 왜냐하면 1 뒤에 있는 몇 개의 숫자는 큰 것부터 작은 것까지 정렬하기 때문에 이 서열은 1로 시작하는 최대값이기 때문에 이 값을 높이려면 1보다 조금 큰 숫자로 시작하고 그 뒤에 있는 숫자가 올라가서 정렬하는 것을 고려해야 한다.좀 큰 숫자를 찾을 수 있을 거예요.예를 들어 이때 1과 2를 바꾸면 서열이 2, 4, 3, 1이 된다. 발견했느냐, 바꾸면 2 뒤에 있는 숫자 순서는 여전히 강서열이다. 왜냐하면 자신보다 조금 큰 숫자와 바꾸면 뒤에 있는 서열의 순서가 바뀌지 않기 때문이다. 이때 4, 3, 1을 역서열하면 자연히 승서열이 배열된다. 이 순서는 1, 4, 3, 2보다 조금 큰 2, 1, 3, 4를 찾게 된다. 이렇게 계속 교체하면 매번 큰 서열을 찾게 된다.결국 4, 3, 2, 1이 멈추면 수조의 전체 배열이 완성된다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
