각 색인에서 고유 한 값을 갖는 일련의 숫자를 생성하십시오.

Question

숫자가 1:n 인 행이 있습니다. 나는 숫자도 두 번째 행을 추가 찾고 있어요 1:n하지만은 다음을 만족하면서 이들은 무작위 순서로해야한다 :

1. 없음 위치
   는이 두 행에서 같은 번호가
2. 숫자들의 조합이 발생하지 두번
예

다음 숫자 7은 모두 1 행과 2 행의 동일 위치에서 발생

Row 1: 1 2 3 4 5 6 7 ... 
Row 2: 3 6 15 8 13 12 7 ... 

(즉 위치 7; 2 + 7 다음

Row 1: 1 2 3 4 5 6 7 ... 
Row 2: 3 7 15 8 13 12 2 ... 

조합에서 위치 2 및 7 (2 회 나타나는 동안함으로써 규칙 1)

을 만족시키지 않는, 따라서 2 규칙을 만족하지 않음).

이 작업을 수동으로 수행하는 것은 가능하지만 (적어도 합리적인 숫자가 될 때까지) 가능할 수도 있지만, MATLAB에서이를 위해 상당히 세련된 해결책이 있어야합니다.

Answer 1

이것은 매우 간단합니다.노드를 무작위로 둘러보고, 'a'노드 다음에 'b'노드가 나타나면 노드 'a'아래에 'b'노드가 나타남을 의미합니다. '목록에 :

그래서 초기 임의 순열 그리고이 경우에는 도보 3 -> 2 -> 5 -> 1 -> 4입니다

3 2 5 1 4 

인 경우 다음과 같이 행을 작성합니다

Row 1: 1 2 3 4 5 
Row 2: 4 5 2 3 1 

이 랜덤 워크 것 두 조건을 모두 만족시킨다.

하지만 네트워크에서 둘 이상의주기를 허용 하시겠습니까? 나는 두 사람이 서로의 모자를 쓰는 것을 원하지 않는다는 것을 안다. 그러나 7 명은 어떨까요? 은 서로의 모자가 있고 다른 하나는 의 모자가 있습니까? 이것이 받아 들일 수 있고 바람직한가?

Answer 2

이 문제는 derangment 순열이라고합니다.
데이터의 무작위 순열을 찾으려면 randperm 함수를 사용하십시오.

x = [1 2 3 4 5 6 7]; 
y = randperm(x); 

그런 다음 순서가 유효한지 확인할 수 있습니다. 그렇지 않다면 몇 번이고 반복하십시오.
성공할 때마다 probability은 약 0.3입니다. 즉, 찾을 때까지 약 10/3 시간이 필요합니다. 따라서 답변을 정말 빨리 찾을 수 있습니다.

또는 this algorithm을 사용하면 임의적 인 분열을 만들 수 있습니다.

당신이 크기> 2의주기를 갖고 싶어

편집,이 문제의 일반화이다. 확률이 인 that case은 작지만 고정 된 단계에서 찾을 수있을 정도로 큽니다. 따라서 동일한 접근법이 여전히 유효합니다.

Answer 3

Andrey는 이미 randperm 및 거절 샘플링 방식과 같은 방식으로 사용자를 지적했습니다. 순열 p을 생성 한 후에 고정 소수점이 있는지를 쉽게 확인할 수있는 방법은 any(p==1:n)입니다. 길이 2의주기가 있는지 여부를 확인하는 쉬운 방법은 any(p(p)==1:n)입니다.

그래서이 순열 1:n의 p 이행 요구 사항에 도착하십시오 for 루프와 while 루프의 각 카운트 반복이 주변

p=[]; 
while (isempty(p)) 
    p=randperm(n); 
    if any(p==1:n), p=[]; 
    elseif any(p(p)==1:n), p=[]; 
    end 
end 

를, 하나의 평균 4.5 순열을 생성 할 필요가 있다는 것 모든 유효한 "(길이 3의주기가 허용되지 않는 경우 6.2)에 대해. 매우 흥미로운.