사각형에 무작위 균일 점 분포 (캐치 포함)

Question

좋아, 균일 한 점 분포 문제는 몇 가지 잘 알려진 알고리즘 (Hammersley, Monte Carlo 등)에 의해 해결됩니다. 그러나 내 상황은 조금 다릅니다. 세트 이 (2, 8, 1, 5, 4, 7, 3, 6)으로 설정되어 있다고 가정 해 보겠습니다. 이러한 값은 색인 (2로 시작)에 의해 순차적으로 액세스됩니다. 이들은 (액세스 패턴 즉, 0 내지 1 인에서 8, 2에서.) X 축에 대응하는 경우, I는, 그들의 대응하는 Y 값을 찾을 갖도록 :

• 전체 지점 세트 (둘 고려되는 x 및 y 좌표)는 이 아니고 낮은 불일치 시퀀스 인이고;
• 어떤 x 값 쌍 (입력 집합)도 최대 y 값을 가져야합니다.

결과 다른 혼합 정수 [1..8] 제 때문에 각 튜플 (AI, BI) 위의 두 가지 규칙을 다음과 B을 설정한다.

요약 : 한 축에 상관없이 어느 한 축에 대한 분포를 가지므로 연속 점이 액세스 할 때 서로 멀리 떨어져 있지만 전체적으로 균일 한 전체 사각형에 분포.

예 케이스 4 개 요소 (3,1,4,2), 양호한 결과 집합 (XY 병합)은 세트 입력이 주어

((3,1), (1, 4), (4,2), (2,3)) 그리고 좋은 점은 포인트에 액세스 할 때 (3,1에서 끝까지), 액세스 할 때마다 새로운 점으로 에 큰 도약을합니다. 축 이는 전반적인 균등 분배와 함께 목표입니다. 동일한 입력 집합에 대한 나쁜 결과는 다음과 같습니다. (x 값은 정상이지만) 이제 우리는 연속적으로 y 값에 액세스하기 때문에 ((3,1), (1,2), (4,3), (2,4))입니다. .

이것은 샘플링에 사용될 사전 계산 된 테이블을 채우는 데 필요하므로 모든 알고리즘의 속도는 중요하지 않습니다 (당연히 2 년이 걸리지 않는 한). 어떤 도움을 주셔서 감사합니다.

감사

Answer 1

당신은 아마 이것을 달성하기 위해 분할 및 정복 전략을 사용할 수 있습니다. 기본적으로 1 : n의 순열을 원할 경우 1 : n/2 및 (n/2 + 1) : n의 순열을 만들어 무작위로 섞습니다. 여기

는 무작위로 그들을 산재 할 수있는 방법이다 : 당신이 그 부분을 돌보는 방법을 모르는 경우

function permute(x,y): 
    L1 = permute(x, (x+y)/2) 
    L2 = permute((x+y)/2+1, y) 
    spin = randomlyselectfrom(-1,1) 
    L = [] 
    while L1 and L2 are not empty: 
     if spin<0: 
      L.enqueue(L1.dequeue) 
     else: 
      L.enqueue(L2.dequeue) 
     if random()<0.9: 
      spin = -spin 
    return L 

나는 나 한테 물어 주시기 등 경계 조건을 검사 탈락했다.

위의 방식으로 두 개의 무작위 순서를 얻었 으면 그 중 하나를 반대로하고 쌍으로하면 필요한 쌍 시퀀스를 얻을 수 있습니다.