충돌없이 배열을 무작위로 채우는 알고리즘

Question

N 개의 정수 배열을 '0'값으로 설정한다고 가정 해 봅시다. 값이 '0'인 배열의 무작위 요소를 선택하고 값을 넣으려고합니다. '1'

어떻게 효율적으로 수행 할 수 있습니까?

나는이 개 솔루션을 함께했다하지만 두 번째는 관련

때문에 충돌의 가능성의 큰 배열 매우 비효율적이다

int array[N] //init to 0s 
int n //number of 1s we want to add to the array 
int i = 0 
while i < n 
    int a = random(0, N) 
    if array[a] == 0 
     array[a] = 1 
     i++ 
    end if 
end while 

매우 ineficient

먼저 해결책을 찾아 목록에 나머지 0 개의 위치가 모두 포함되어 있으며 배열의 색인에 해당하는 값을 찾기 위해 남은 0과 0 사이의 난수를 선택합니다. 그것은 작업의 수를 경계하기 때문에, 최초의 솔루션보다 훨씬 더 안정적이지만, 우리가 배열을 채우려면 아직 N²의 최악의 시나리오의 복잡성을 가지고 완전히

n들과 N-n와

Answer 1

두 번째 솔루션은 실제로 좋은 시작이다. 나는 그것이 모든 배열을 채우려는 경우 O (N²)가되는 모든 변경 후에 위치 목록을 다시 만드는 것을 포함한다고 가정합니다. 그러나 매번 목록을 다시 작성할 필요는 없습니다. 배열을 채우기를 원하기 때문에 무작위 순서를 사용하고 그에 따라 나머지 위치를 선택할 수 있습니다. 그냥 무작위 순서를 얻을 셔플, 당신이 여기 [0, 1, 3, 6] 제로 위치의 목록을 구축하면 [0, 0, 1, 0, 1, 1, 0]

:

는 예를 들어, 다음 배열 (크기 7과 0의 초기 완전하지) 걸릴. 그런 다음 위치에 지정된 순서대로 배열을 채 웁니다. 셔플은 [3, 1, 6, 0]를 제공하는 경우

는 예를 들어, 당신과 같이 배열을 채울 수 : 배열이 처음에 0으로 채워되어

[0, 0, 1, 0, 1, 1, 0] <- initial configuration 
[0, 0, 1, 1, 1, 1, 0] <- First, position 3 
[0, 1, 1, 1, 1, 1, 0] <- Second, position 1 
[0, 1, 1, 1, 1, 1, 1] <- etc. 
[1, 1, 1, 1, 1, 1, 1] 

경우, 다음도 쉽다. 초기 목록은 0부터 N까지의 정수 목록입니다 (배열의 크기). 그것을 섞어서 같은 과정을 적용하십시오.

전체 배열을 채우고 싶지 않은 경우에도 전체 목록을 작성해야하지만 배열을 채운 다음자를 수 있습니다 (일부 지점 이후 배열 채우기를 중지한다는 의미).

물론이 솔루션을 사용하려면 각 단계에서 배열이 변경되지 않아야합니다.

Answer 2

당신은 채울 수있는 배열 0을 만들고 무작위로 섞는다.

Fisher-Yates shuffle 선형 복잡도를 갖는다 :

for i from N−1 downto 1 do 
    j ← random integer such that 0 ≤ j ≤ i 
    exchange a[j] and a[i]