정렬 된 목록을 임의 화하는 방법?

Question

너희들에게 이상한 질문이있다.

난 무작위 화하고자하는 좋은 정렬 목록이있다. 그 일을 어떻게 하죠?

내 응용 프로그램에서 나는 discretized 개체의 윤곽을 설명하는 점 목록을 반환하는 함수가 있습니다. 문제가 해결되는 방식 때문에이 함수는 멋진 정렬 목록을 반환합니다. 수학에 설명 된 두 번째 경계를 가지며 두 객체가 서로 교차하는지 확인하려고합니다. 간단히 포인트를 반복하고 어느 한 포인트가 수학적 경계 안에 있는지 확인합니다.

이 방법은 잘 작동하지만 점 데이터를 무작위로 추출하여 속도를 높이고 싶습니다. 내 수학 경계가 서로 옆에있는 일련의 점으로 겹칠 가능성이 높기 때문에 좋은 정렬 된 항목을 반복하지 않고 무작위 목록을 확인하는 것이 합리적이라고 생각합니다. 교차로를 선언하기 위해 명중).

그럼 어떻게 정렬 목록을 무작위로 만들지에 대한 아이디어가 있습니까?

Answer 1

std::random_shuffle을 사용하십시오. 직접 메서드를 구현하려면 Fisher-Yates shuffle을 봐야합니다. 당신의 "목록"을 가정

는

Answer 2

random_shuffle algorithm을 사용해 볼 수도 있지만 임의 액세스 반복기가 필요하므로 list에서 작동하지 않습니다. 그래도 vector 또는 deque에 사용할 수 있습니다.

Answer 3

std::random_shuffle(thelist.begin(), thelist.end()); 

Answer 4

링크 된 목록을 의미하지만, 대신에 랜덤 액세스를 지원하는 무언가 (예를 들어, 배열, 표준 : : 벡터, 또는 표준 : 양단 큐), 표준 : random_shuffle과를 의미하지 않습니다 유용 할 수 있습니다.

Answer 5

그러나 중요한 질문은 목록을 무작위 화하는 데 필요한 런타임이 런타임을 순차적으로 통과하는 것보다 클 수 있는지 여부입니다.

아마도 실제로해야 할 일은 실제로 무작위로 추출하는 것이 아니라 앞뒤가 아닌 순서로 읽는 것입니다. 예를 들어 목록에 n 개의 구성원이있는 경우 1, n, 2, n-1, 3, n-2 등 또는 1, n/2, 2, n/2 + 1, 3, n을 처리해야합니다/2 +2 등

항상 동일한 점수를 가지고 있거나 포인트 수가 작은 유한 집합에 속하는 경우, 가능한 한 각 포인트 수에 대한 포인트 평가 명령을 한 번 생성 할 수 있습니다 , 어떤 방법 으로든 진정으로 무작위로 조심스럽게 계산됩니다.

Answer 6

 
int array[N]; 

for(int i = N - 1; i > 0; i--) { 
    int j = rand() % i; 
    int tmp = array[i]; array[i] = array[j]; array[j] = i; 
}