[5. 배열] 5.14 임의의 순열 계산하기

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

---

Q 5.14 임의의 순열 계산하기

<0,1,....,n-1>로 이루어진 임의의 순열을 동일한 확률로 만들어 내는 알고리즘을 작성하라.
숫자를 같은 확률로 반환하는 임의의 숫자 생성기가 주어졌다고 가정해도 되며, 이 생성기를 가능하면 적게 호출하도록 하자.

---

문제 5.12 오프라인 데이터 샘플 구하기에서 사용한 방법을 이용하려고 한다.

https://msugi.tistory.com/26

[5. 배열] 5.12 오프라인 데이터 샘플 구하기

문제 5.12를 이용하면 반복마다 배열을 부분 순열과 남아있는 값으로 나눌 수 있다.
반환되는 부분 집합이 항상 같다고 하더라도 모든 n!개의 가능한 순열이 같은 확률로 선택된다.

소스코드와 결과는 다음과 같다.

시간 복잡도 O(n)

main

매번 다른 결과가 나온다.