임시 저장 장치없이 의사 랜덤 순서로 그리드의 모든 셀을 방문하십시오.

Question

NxN 눈금이 있고 모든 셀을 정확히 한 번 방문하고 의사 임의 순서로 방문하려고한다고 가정하십시오. 순서는 매우 임의적 일 필요는 없지만 그리드 셀 정렬의 다른 순열이 가능하도록 시드 할 수 있어야합니다. 단순히 모든 셀 좌표 목록을 임의로 바꾸고 인덱싱하지 않고이 작업을 수행 할 수 있습니까? 즉, 인덱스 (i,j)을 (i',j')으로 일대일로 완전히 변환 할 수있는 수식 (또는 그러한 수식을 구성하는 일반적인 방법)을 원합니다.

후속 조치 (실제로 의도 된 질문) i>j (아래쪽 삼각형)에 해당하는 요소 만 방문하려는 NxN 그리드에 대해서도 동일한 작업을 수행 할 수 있습니까?

Answer 1

0..ROWS * COLS-1 범위의 각 숫자 N이 결정적으로 셀 (N DIV ROWS, N MOD ROWS)을 가리키기 때문에이 질문은 this SO question과 같습니다. 유용한 답변과 참고 자료가 있습니다.

Answer 2

먼저 문제를 2 차원에서 1 차원으로 변경하십시오 (모든 N 차원 배열은 1 차원 인덱스를 N 차원 인덱스로 변환하는 올바른 알고리즘을 사용하여 1 차원 배열로 처리 할 수 ​​있음). 0 또는 N 사이의 모든 값을 seed 나 pseudo-random 형식으로 정확히 한 번씩 방문하거나 O (1) 저장소 요구 사항 (질문에서 명확하지 않음)을 사용하는 알고리즘을 원합니다. 나는 개인적으로 그런 알고리즘이 없다는 것을 안다. 의심할만한 것이 하나 존재한다. 그러나 다시 나는 하나가 존재하지 않는다는 것을 증명할 수 없다. 그래서 내가 제공 할 수있는 것보다 더 똑똑 할 수도있다.

편집

내가 틀렸다. Linear Feedback Shift Register을 사용할 수 있습니다. 위키 피 디아 페이지는 1에서 19 비트 길이의 최대 LSFR을 설정하는 방법을 보여 주며 최대 168 비트 길이의 레지스터에 대한 설정이있는 PDF에 대한 링크가 있습니다. N을 분석하고 가장 가까운 비트 LFSR 기능을 발견하는 것입니다 후자의 기능에 대한 N

// a 31 bit LFSR 
// based on http://forums.sun.com/thread.jspa?threadID=5276320 
public static int getNextValue(int register) { 
    int t31 = (register & (1 << 30)) >>> 30; 
    int t28 = (register & (1 << 27)) >>> 27; 
    int input = t31^t28; 
    register <<= 1; 
    register |= input; 
    register &= 0x7fffffff; // mask with this to ensure 0s in the high order bits 
    return register; 
} 

public static int getNextValueBelowN(int value, int n) { 
    do { 
     value = getNextValue(value); 
    } while (value > n); 
    return value; 
} 

명백한 최적화 1에서 당신에게 의사 난수 값을 줄 것이다 알고리즘을 구현하기 어려울 안 그것에 길이 만 낮은 삼각형을 타격 while 루프 두 번째 부분에

최종 편집

,이 최소화 미스는 당신이 한 차원 인덱스를 변환 N을 줄이고 방식을 변경해야 의미 2 차원으로 예 :

public static int getMaxValue(int dimension) { 
    int retVal = 0; 
    while (dimension > 0) { 
     retVal += dimension--; 
    } 
    return retVal; 
} 


public static int getMaxValueFast(int dimension) { 
    int retVal = 0; 
    if (dimension % 1 == 1) { 
     retVal += dimension--; 
    } 
    retVal += ((dimension + 1) * dimension/2); 
    return retVal; 
} 



public static Point getCoordinates(int index, int dimension) { 
    Point retVal = new Point(); 
    while (index >= dimension) { 
     ++retVal.x; 
     index -= dimension--; 
    } 
    retVal.y = index; 
    return retVal; 
} 

Answer 3

방문한 셀을 표시하십시오. 이를 위해 무작위로 튜플을 생성하고 아직 방문하지 않은 경우에만 셀을 방문 할 수 있습니다.

는 낮은 삼각를 들어, 당신은 또한 당신이 이미 방문한 것과 추적하기 위해 마킹을 사용하지만, 지금은 정수 i 및 j를 생성 할 때, i이 j 동일한 경우는 그것을 멀리 던져 그렇지 않으면 튜플을 사용할 수 있습니다 (i, j) 인 경우 i > j 및 (j, i)j > i 인 경우.