어레이가 동일하게 유지 될 확률은 얼마입니까?
이 질문은 Microsoft 인터뷰에서 요청되었습니다. 왜이 사람들이 확률에 대해 이상한 질문을하는지 알고 싶어요?
rand (N)이 주어지면 0에서 N-1까지의 난수를 생성하는 난수 생성기입니다.
int A[N]; // An array of size N
for(i = 0; i < N; i++)
{
int m = rand(N);
int n = rand(N);
swap(A[m],A[n]);
}
편집 : 시드가 고정되어 있지 않습니다.
배열 A가 동일하게 유지 될 확률은 얼마입니까?
배열에 고유 한 요소가 포함되어 있다고 가정합니다.
글쎄, 나는 이것으로 약간 재미있었습니다. 문제를 처음 읽을 때 가장 먼저 생각한 것은 그룹 이론 (특히 대칭 그룹 S n )이었습니다. for 루프는 각 반복에서 전치 (즉, 스왑)를 구성 하여 S n 에서 순열 σ를 간단히 만듭니다 . 내 수학은 그다지 훌륭하지 않고 약간 녹슬 었으므로 내 표기법이 벗어난 경우에는 부담이 없습니다.
개요
하자 A우리의 배열이 치환 후 변경되지 발생합니다. 우리는 궁극적으로 사건의 가능성을 발견하도록 요청 A, Pr(A).
내 솔루션은 다음 절차를 따르려고 시도합니다.
- 가능한 모든 순열 고려 (예 : 배열 재정렬)
- 이러한 순열을 포함하는 소위 ID 전치 수를 기반 으로 분리 된 집합으로 분할 합니다. 이에 문제를 줄일 수 있습니다 심지어 에만 순열.
- 순열이 짝수 (및 특정 길이) 인 경우 항등 순열을 얻을 확률을 결정합니다.
- 이 확률을 합산하여 배열이 변경되지 않은 전체 확률을 얻습니다.
1) 가능한 결과
for 루프를 반복 할 때마다 다음 두 가지 중 하나가 발생하는 스왑 (또는 전치 )이 생성됩니다.
- 두 요소가 바뀝니다.
- 요소는 자신과 교환됩니다. 우리의 의도와 목적을 위해 배열은 변경되지 않았습니다.
두 번째 사례에 레이블을 지정합니다. 다음과 같이 신원 전치 를 정의 해 보겠습니다 .
신원 전위는 숫자 자체로 교체 될 때 발생합니다. 즉, 위의 for 루프에서 n == m 일 때.
나열된 코드의 주어진 실행에 대해 우리는 N조옮김 을 구성 합니다. 0, 1, 2, ... , N이 "사슬"에 나타나는 정체성 전치 가있을 수 있습니다 .
예를 들어 다음과 같은 N = 3경우를 고려하십시오 .
Given our input [0, 1, 2].
Swap (0 1) and get [1, 0, 2].
Swap (1 1) and get [1, 0, 2]. ** Here is an identity **
Swap (2 2) and get [1, 0, 2]. ** And another **
홀수 개의 비 정체성 전치 (1)가 있고 배열이 변경됩니다.
2) ID 전치 수에 따른 분할
주어진 순열에서 동일성 전치가 나타나는 K_i사건이 되자 i. 이것은 가능한 모든 결과의 완전한 분할을 형성합니다.
- 순열은 두 개의 다른 양의 동일성 전치를 동시에 가질 수 없습니다.
- 가능한 모든 순열에는
0및NID 전치 가 있어야합니다 .
따라서 우리는 총 확률 의 법칙을 적용 할 수 있습니다 .
이제 마침내 파티션을 활용할 수 있습니다. ID 가 아닌 전치 의 수가 홀수이면 배열이 변경되지 않을 수 없습니다 *. 그러므로:
* 그룹 이론에서 순열은 짝수이거나 홀수이지만 둘다는 아닙니다. 따라서 홀수 순열은 ID 순열이 될 수 없습니다 (ID 순열이 짝수이기 때문에).
3) 확률 결정
따라서 이제 N-i짝수에 대해 두 가지 확률을 결정해야합니다 .
첫 학기
첫 번째 항 
은 i동일성 전치 로 순열을 얻을 확률을 나타냅니다 . 이것은 for 루프가 반복 될 때마다 이항으로 밝혀졌습니다.
- 결과는 이전 결과와 무관하며
- 동일성 전치를 만들 확률은 동일
1/N합니다.
따라서 N시행의 경우 i동일성 전치 를 얻을 확률 은 다음과 같습니다.
두 번째 학기
당신이 여기까지 만들었다면, 우리가 찾는 문제를 감소 
하기위한 N - i도. 이것은 i전치가 신원 인 경우에 주어진 신원 순열을 얻을 확률을 나타냅니다 . 가능한 순열 수에 대해 동일성 순열을 달성하는 방법의 수를 결정하기 위해 순진한 계산 방식을 사용합니다.
먼저 순열 (n, m)과 (m, n)동등한 것을 고려하십시오 . 그런 다음 M가능한 비 정체성 순열의 수로 합시다 . 이 수량을 자주 사용합니다.
여기서 목표는 전치 모음을 결합하여 동일성 순열을 형성하는 방법의 수를 결정하는 것입니다. 의 예제와 함께 일반적인 솔루션을 구성하려고합니다 N = 4.
N = 4모든 신원 전치 ( 즉 i = N = 4 )가 있는 경우를 고려해 봅시다 . X정체성 전치를 표현 하자 . 각각에 대해 X, 거기 N가능성 (그들은 다음과 같습니다 n = m = 0, 1, 2, ... , N - 1). 따라서 N^i = 4^4정체성 순열을 달성 할 수 있는 가능성 이 있습니다 . 완전성을 위해 이항 계수를 추가하여 C(N, i)항등 전치 순서를 고려합니다 (여기서는 1과 같습니다). 위의 요소의 물리적 레이아웃과 아래의 가능성 수를 사용하여 아래에 설명하려고했습니다.
I = _X_ _X_ _X_ _X_
N * N * N * N * C(4, 4) => N^N * C(N, N) possibilities
이제 명시 적으로 대체하지 않고 N = 4그리고 i = 4, 우리는 일반적인 경우 볼 수 있습니다. 위와 이전에 찾은 분모를 결합하면 다음을 찾을 수 있습니다.
이것은 직관적입니다. 사실, 그 이외의 다른 값 1은 아마 당신을 놀라게 할 것입니다. 생각해보십시오 : 우리는 모든 N전치가 정체성이라고 말하는 상황이 주어집니다 . 이 상황에서 어레이가 변경되지 않았을 가능성은 무엇입니까? 분명히 1.
이제 다시에 대해 N = 42 개의 동일성 전치 ( 즉 i = N - 2 = 2 )를 고려해 봅시다 . 관례 적으로 우리는 마지막에 두 ID를 배치 할 것입니다 (그리고 나중에 주문할 수도 있음). 이제 우리는 구성 될 때 정체성 순열이 될 두 개의 조옮김을 선택해야한다는 것을 알고 있습니다. 첫 번째 위치에 요소를 배치하고 t1. 위에서 언급했듯이 정체성이 아니라고 M가정 t1할 수있는 가능성 이 있습니다 (이미 두 개를 배치 한 것과 같을 수 없음).
I = _t1_ ___ _X_ _X_
M * ? * N * N
두 번째 지점에 들어갈 수있는 유일한 요소는의 역입니다 t1. 이것은 사실입니다 t1(역의 고유성에 의해 유일한 요소입니다). 이항 계수를 다시 포함합니다.이 경우 4 개의 열린 위치가 있고 2 개의 동일성 순열을 배치하려고합니다. 얼마나 많은 방법으로 할 수 있습니까? 4 2를 선택합니다.
I = _t1_ _t1_ _X_ _X_
M * 1 * N * N * C(4, 2) => C(N, N-2) * M * N^(N-2) possibilities
다시 일반적인 경우를 살펴보면이 모든 것은 다음과 같습니다.
마지막으로 N = 4신원 전치가없는 경우를 처리합니다 ( 예 :) i = N - 4 = 0. 가능성이 많기 때문에 까다로워지기 시작하고 이중으로 세지 않도록주의해야합니다. 마찬가지로 첫 번째 지점에 단일 요소를 배치하고 가능한 조합을 조사하는 것으로 시작합니다. 가장 쉬운 첫 번째 방법 : 같은 조옮김을 4 번 반복합니다.
I = _t1_ _t1_ _t1_ _t1_
M * 1 * 1 * 1 => M possibilities
이제 두 개의 고유 한 요소 t1와 t2. 거기 M에 대한 가능성 t1만 M-1가능성은 t2(이후 t2동일 할 수 없다 t1). 모든 준비를 소진하면 다음과 같은 패턴이 남습니다.
I = _t1_ _t1_ _t2_ _t2_
M * 1 * M-1 * 1 => M * (M - 1) possibilities (1)st
= _t1_ _t2_ _t1_ _t2_
M * M-1 * 1 * 1 => M * (M - 1) possibilities (2)nd
= _t1_ _t2_ _t2_ _t1_
M * M-1 * 1 * 1 => M * (M - 1) possibilities (3)rd
이제 세 가지 고유 한 요소 t1인 t2,, t3. t1먼저 배치 하고 t2. 평소처럼 우리는 다음을 가지고 있습니다.
I = _t1_ _t2_ ___ ___
M * ? * ? * ?
우리는 아직 얼마나 많은 가능성이 있는지 말할 수 없으며 t2, 그 이유를 곧 알게 될 것입니다.
이제 우리 t1는 세 번째 자리에 있습니다. 공지 사항, t1마지막 자리에 갈 것 인 경우에, 우리는 단지 재현 될 수 있기 때문에 거기에 가야 (3)rd상기 구성합니다. 이중 계산은 나쁘다! 이렇게하면 세 번째 고유 요소 t3가 최종 위치에 남습니다 .
I = _t1_ _t2_ _t1_ _t3_
M * ? * 1 * ?
그렇다면 왜 t2s 의 수를 더 자세히 고려하기 위해 잠시 시간을 내야 했습니까? 트랜스 포지션은 t1하고 t2 할 수없는 분리 된 순열 (수 , 즉 그들 중 하나 (오직 하나 그들도 동일 할 수 없기 때문에) 공유해야 n또는 m). 그 이유는 그들이 분리되어 있다면 순열 순서를 바꿀 수 있기 때문입니다. 이것은 우리가 (1)st배열을 두 배로 세는 것을 의미합니다 .
말하십시오 t1 = (n, m). t2형식 (n, x)또는 (y, m)일부 를 위해 x그리고 y비 연속적이어야합니다. 참고 x하지 않을 수 n또는 m과 y많은 수 없습니다 n나 m. 따라서 가능한 순열의 t2수는 실제로 2 * (N - 2)입니다.
따라서 레이아웃으로 돌아갑니다.
I = _t1_ _t2_ _t1_ _t3_
M * 2(N-2) * 1 * ?
이제 t3구성의 역이어야합니다 t1 t2 t1. 수동으로 해보겠습니다.
(n, m)(n, x)(n, m) = (m, x)
따라서 t3이어야합니다 (m, x). 이 참고 하지 에 해체 t1되지는 동일하거나 t1또는 t2이 경우에 대한 이중 계산이 없습니다.
I = _t1_ _t2_ _t1_ _t3_
M * 2(N-2) * 1 * 1 => M * 2(N - 2) possibilities
마지막으로,이 모든 것을 합치면 :
4) 종합하기
그게 다입니다. 2 단계에서 주어진 원래의 합에 우리가 찾은 것을 대입하여 거꾸로 작업하십시오 N = 4. 아래 사례에 대한 답을 계산했습니다 . 다른 답변에서 찾은 경험적 숫자와 매우 가깝습니다!
N = 4
M = 6 _________ _____________ _________
| Pr (K_i) | Pr (A | K_i) | 제품 |
_________ | _________ | _____________ | _________ |
| | | | |
| i = 0 | 0.316 | 120/1296 | 0.029 |
| _________ | _________ | _____________ | _________ |
| | | | |
| i = 2 | 0.211 | 6/36 | 0.035 |
| _________ | _________ | _____________ | _________ |
| | | | |
| i = 4 | 0.004 | 1/1 | 0.004 |
| _________ | _________ | _____________ | _________ |
| | |
| 합계 : | 0.068 |
| _____________ | _________ |
단정
여기에 적용 할 그룹 이론의 결과가 있다면 멋질 것입니다. 이 모든 지루한 계산을 완전히 없애고 문제를 훨씬 더 우아한 것으로 단축하는 데 확실히 도움이 될 것입니다. 에서 일을 그만 두었습니다 N = 4. 를 들어 N > 5, 어떤 주어진 만 (좋은, 잘 모르겠어요 방법) 근사치를 제공합니다. 예를 들어, N = 8전치가 주어지면 위에서 설명하지 않은 네 가지 고유 한 요소로 정체성을 만드는 분명한 방법이 있습니다. 순열이 길어질수록 방법의 수는 계산하기가 더 어려워집니다 (내가 말할 수있는 한 ...).
어쨌든 인터뷰 범위 내에서 이런 일을 할 수는 없었습니다. 운이 좋으면 분모 단계까지 갈 것입니다. 그 외에는 꽤 끔찍해 보입니다.
왜이 사람들이 확률에 대해 이상한 질문을하는지 알고 싶어요?
이와 같은 질문은 면접관이 인터뷰 대상자의
- 코드 읽기 능력 (매우 간단한 코드이지만 적어도 뭔가)
- 알고리즘을 분석하여 실행 경로를 식별하는 기능
- 가능한 결과와 엣지 케이스를 찾기 위해 논리를 적용하는 기술
- 문제를 해결하는 과정에서 추론 및 문제 해결 기술
- 의사 소통 및 업무 기술-질문을하거나 관련 정보를 바탕으로 독립적으로 업무를 수행합니까?
... 등등. 인터뷰 대상자의 이러한 특성을 드러내는 질문을하는 열쇠는 믿을 수 없을 정도로 간단한 코드를 갖는 것입니다. 이것은 비코 더가 갇혀있는 사기꾼을 떨쳐냅니다. 잘못된 결론으로 오만한 점프; 게 으르거나 수준 이하의 컴퓨터 과학자는 간단한 해결책을 찾고 그만 찾는다. 종종 그들이 말했듯이 올바른 답을 얻었는지 아닌지가 아니라 사고 과정에 깊은 인상을 주는지 여부입니다.
저도 질문에 답하려고합니다. 인터뷰에서 나는 한 줄의 서면 답변보다는 나 자신을 설명하겠다. 이것은 나의 '답변'이 틀렸더라도 논리적 사고를 보여줄 수 있기 때문이다.
A는 동일하게 유지됩니다 (예 : 동일한 위치에있는 요소).
m == n모든 반복에서 (모든 요소가 자신과 만 교체되도록) 또는- 교체 된 모든 요소는 원래 위치로 다시 교체됩니다.
첫 번째 경우는 duedl0r이 제공하는 '간단한'경우이며 배열이 변경되지 않은 경우입니다. 이것이 답이 될 수 있습니다.
배열 A가 동일하게 유지 될 확률은 얼마입니까?
배열이에서 변경된 i = 1다음 다시 되돌아 가면 i = 2원래 상태에 있지만 '동일하게 유지'되지 않았습니다. 변경된 다음 다시 변경되었습니다. 그것은 똑똑한 기술 일 수 있습니다.
그런 다음 요소가 교체되고 다시 교체 될 가능성을 고려할 때 인터뷰에서 계산이 내 머리 위에 있다고 생각합니다. 분명한 고려 사항은 변경이 필요하지 않다는 것입니다. 다시 변경 스왑, 1과 2, 2와 3, 1과 3, 마지막으로 2와 3을 바꾸는 세 가지 요소 사이에 쉽게 스왑이있을 수 있습니다. 계속하면 이와 같이 '원형'인 4, 5 또는 그 이상의 항목간에 스왑이있을 수 있습니다.
사실, 오히려 배열이 변경되는 경우를 고려보다,이 경우 고려하는 것이 더 간단 할 수 있다 변경합니다. 이 문제가 Pascal의 삼각형 과 같은 알려진 구조에 매핑 될 수 있는지 고려하십시오 .
이것은 어려운 문제입니다. 인터뷰에서 해결하기가 너무 어렵다는 데 동의하지만, 그렇다고 인터뷰에서 묻는 것이 너무 어렵다는 의미는 아닙니다. 가난한 후보는 답을 얻지 못하고, 보통 후보는 분명한 답을 추측하고, 좋은 후보는 왜 문제에 답하기가 너무 어려운지 설명 할 것입니다.
나는 이것이 면접관에게 후보자에 대한 통찰력을 제공하는 '개방형'질문이라고 생각합니다. 이런 이유로 인터뷰에서 해결하기가 너무 어렵지만 인터뷰에서 물어 보는 것은 좋은 질문입니다. 대답이 옳은지 틀린지 확인하는 것보다 질문을하는 것이 더 많습니다.
다음은 rand가 확률을 생성하고 계산할 수있는 2N- 튜플 인덱스 값의 수를 계산하는 C 코드입니다. N = 0으로 시작하여 1, 1, 8, 135, 4480, 189125 및 12450816의 개수를 표시하며 확률은 1, 1, .5, .185185, .0683594, .0193664 및 .00571983입니다. 카운트는 Integer Sequences 백과 사전에 나타나지 않으므로 내 프로그램에 버그가 있거나 매우 모호한 문제입니다. 만약 그렇다면, 문제는 구직자가 해결하려는 것이 아니라 그들의 사고 과정과 그들이 좌절을 어떻게 처리 하는지를 드러내 기위한 것입니다. 나는 그것을 좋은 인터뷰 문제로 보지 않을 것입니다.
#include <inttypes.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#define swap(a, b) do { int t = (a); (a) = (b); (b) = t; } while (0)
static uint64_t count(int n)
{
// Initialize count of how many times the original order is the result.
uint64_t c = 0;
// Allocate space for selectors and initialize them to zero.
int *r = calloc(2*n, sizeof *r);
// Allocate space for array to be swapped.
int *A = malloc(n * sizeof *A);
if (!A || !r)
{
fprintf(stderr, "Out of memory.\n");
exit(EXIT_FAILURE);
}
// Iterate through all values of selectors.
while (1)
{
// Initialize A to show original order.
for (int i = 0; i < n; ++i)
A[i] = i;
// Test current selector values by executing the swap sequence.
for (int i = 0; i < 2*n; i += 2)
{
int m = r[i+0];
int n = r[i+1];
swap(A[m], A[n]);
}
// If array is in original order, increment counter.
++c; // Assume all elements are in place.
for (int i = 0; i < n; ++i)
if (A[i] != i)
{
// If any element is out of place, cancel assumption and exit.
--c;
break;
}
// Increment the selectors, odometer style.
int i;
for (i = 0; i < 2*n; ++i)
// Stop when a selector increases without wrapping.
if (++r[i] < n)
break;
else
// Wrap this selector to zero and continue.
r[i] = 0;
// Exit the routine when the last selector wraps.
if (2*n <= i)
{
free(A);
free(r);
return c;
}
}
}
int main(void)
{
for (int n = 0; n < 7; ++n)
{
uint64_t c = count(n);
printf("N = %d: %" PRId64 " times, %g probabilty.\n",
n, c, c/pow(n, 2*n));
}
return 0;
}
알고리즘의 동작은으로 모델링 될 수 마르코프 연쇄 오버 대칭 그룹 S N .
기초
N 어레이의 요소들이 A배치 될 수있는 N ! 다른 순열. 예를 들어 사전 순서에 따라 1부터 N 까지 이러한 순열에 번호를 매기겠습니다 . 따라서 A알고리즘에서 언제든지 배열의 상태 는 순열 번호로 완전히 특성화 될 수 있습니다.
예를 들어, N = 3의 경우 모든 3의 가능한 번호 매기기! = 6 개의 순열은 다음과 같습니다.
- 알파벳
- acb
- Bac
- bca
- 택시
- cba
상태 전이 확률
알고리즘의 각 단계에서의 상태 A는 동일하게 유지되거나 이러한 순열 중 하나에서 다른 순열로 전환됩니다. 이제 우리는 이러한 상태 변화의 확률에 관심이 있습니다. Pr ( i → j )를 단일 루프 반복 에서 순열 i 에서 순열 j 로 상태가 변할 확률 이라고합시다 .
우리는 선택할 같이 m 및 n은이 범위에서 균일하게 독립적 [0, N은 -1]이있다 N 똑같이 가능성이 각각 ² 가능한 결과.
정체
들면 N 이러한 결과 m = N 때문에 순열에 변화가없는 보유하고있다. 따라서,
.
조옮김
나머지 N ²- N 케이스는 전치입니다. 즉, 두 요소가 위치를 교환하므로 순열이 변경됩니다. 이러한 전치 중 하나가 위치 x 및 y 의 요소를 교환한다고 가정 합니다. 이 전치가 알고리즘에 의해 생성되는 방법에는 두 가지 경우가 있습니다 : m = x , n = y 또는 m = y , n = x . 따라서 각 전치에 대한 확률은 2 / N ²입니다.
이것이 우리의 순열과 어떤 관련이 있습니까? i 를 j로 (또는 그 반대로) 변환하는 전치가있는 경우에만 두 순열 i 및 j 이웃을 호출합시다 . 그런 다음 결론을 내릴 수 있습니다.
전환 매트릭스
전이 행렬 P ∈ [0,1] N ! × N ! 에서 확률 Pr ( i → j )을 배열 할 수 있습니다 . . 우리는 정의합니다
p ij = Pr ( i → j ),
여기서 P는 (IJ)는 의 항목 인 I 번째 행과 J 의 열 번째 P는 . 참고
Pr ( i → j ) = Pr ( j → i ),
이것은 P 가 대칭 임을 의미 합니다.
이제 핵심은 P 를 스스로 곱할 때 일어나는 일을 관찰 하는 것입니다. 모든 요소를 가지고 P를 (2) IJ 의 P ² :
제품 Pr ( i → k ) · Pr ( k → j )는 순열 i 에서 시작하여 한 단계에서 순열 k 로 전환하고 다른 후속 단계 후에 순열 j 로 전환 할 확률입니다 . 따라서 모든 중간 순열 k를 합산하면 2 단계 에서 i 에서 j 로 전환 될 총 확률을 얻을 수 있습니다.
이 인수는 P의 더 높은 거듭 제곱으로 확장 될 수 있습니다 . 특별한 결과는 다음과 같습니다.
P ( N ) II는 전치 다시 돌아갈 확률 I를 후 N의 우리 순열 가정에서 시작 단계 I .
예
N = 3으로 이걸 해보자. 우리는 이미 순열에 대한 번호를 가지고있다. 해당 전환 매트릭스는 다음과 같습니다.
P 를 그 자체로 곱 하면 다음이 제공됩니다.
또 다른 곱셈은 다음과 같습니다.
주 대각선의 요소는 우리가 원하는 확률이고, 범 15 / 81 또는 5 / 27 .
토론
이 접근법은 수학적으로 건전하고 N의 모든 값에 적용 할 수 있지만 이 형식에서는 실용적이지 않습니다. 전이 행렬 P 에는 N ! ² 항목이 있으며 이는 매우 빠르게 증가합니다. N = 10 인 경우 에도 행렬의 크기는 이미 13 조 항목을 초과합니다. 따라서이 알고리즘의 순진한 구현은 실행 불가능한 것으로 보입니다.
그러나 다른 제안과 비교할 때이 접근 방식은 매우 구조화되어 있으며 어떤 순열이 이웃인지 파악하는 것 이상의 복잡한 파생이 필요하지 않습니다. 내 희망은이 구조화를 이용하여 훨씬 더 간단한 계산을 찾을 수 있다는 것입니다.
예를 들어, P 의 모든 거듭 제곱의 모든 대각선 요소 가 동일 하다는 사실을 이용할 수 있습니다. 우리가 쉽게의 추적 계산할 수 있습니다 가정 P N을 ,이 솔루션은 단순히 TR입니다 ( P N ) / N !. 미량의 P N은 의 합과 같다 N 의 고유치 번째의 파워. 따라서 P 의 고유 값을 계산하는 효율적인 알고리즘 이 있다면 설정 될 것입니다. 그러나 N = 5 까지의 고유 값을 계산하는 것보다 더 이상 탐구하지 않았습니다 .
경계 1 / n n <= p <= 1 / n 을 관찰하는 것은 쉽습니다 .
여기에 역 지수 상한을 보여주는 불완전한 아이디어가 있습니다.
{1,2, .., n}에서 2n 번의 숫자를 그리고 있습니다. 그중 하나가 고유 한 경우 (정확히 한 번 발생), 요소가 사라지고 원래 위치로 돌아갈 수 없기 때문에 배열이 확실히 변경됩니다.
고정 된 숫자가 고유 할 확률은 2n * 1 / n * (1-1 / n) ^ (2n-1) = 2 * (1-1 / n) ^ (2n-1)이며 비대칭 2 / e입니다. 2 , 0에서 멀어짐. [2n은 어떤 시도를했는지 선택했기 때문에, 1 / n은 그 시도에서 얻었고, (1-1 / n) ^ (2n-1)은 얻지 못했습니다. 다른 시도]
이벤트가 독립적 인 경우 모든 숫자가 고유하지 않을 가능성은 (2 / e 2 ) ^ n이며 이는 p <= O ((2 / e 2 ) ^ n)을 의미합니다. 불행히도 그들은 독립적이지 않습니다. 좀 더 정교한 분석으로 그 한계를 보여줄 수 있다고 생각합니다. 키워드는 "공과 쓰레기통 문제"입니다.
한 가지 단순한 솔루션은
p> = 1 / N N
배열이 동일하게 유지되는 한 가지 가능한 방법은 m = n모든 반복에 대해 경우 입니다. 그리고 가능성 과 m동일 합니다.n1 / N
확실히 그것보다 높습니다. 문제는 얼마나 ..
두 번째 생각 : 배열을 무작위로 섞으면 모든 순열의 확률이 같다고 주장 할 수도 있습니다. n!순열이 있기 때문에 (처음에 가지고있는) 하나만 얻을 확률은 다음과 같습니다.
p = 1 / N!
이전 결과보다 약간 낫습니다.
논의 된 바와 같이 알고리즘은 편향되어 있습니다. 이는 모든 순열이 동일한 확률을 갖는 것은 아니라는 것을 의미합니다. 따라서 1 / N!정확하지 않습니다. 순열의 분포가 어떻게되는지 알아 내야합니다.
참고로, 위의 경계 (1 / n ^ 2)가 다음과 같은지 확실하지 않습니다.
N=5 -> 0.019648 < 1/25
N=6 -> 0.005716 < 1/36
샘플링 코드 :
import random
def sample(times,n):
count = 0;
for i in range(times):
count += p(n)
return count*1.0/times;
def p(n):
perm = range(n);
for i in range(n):
a = random.randrange(n)
b = random.randrange(n)
perm[a],perm[b]=perm[b],perm[a];
return perm==range(n)
print sample(500000,5)
모든 사람들은 A[i] == i명시 적으로 언급되지 않은 라고 가정합니다 . 저도이 가정을 할 것이지만 확률은 내용에 따라 다릅니다. 예를 들어이면 A[i]=0모든 N에 대해 확률 = 1입니다.
방법은 다음과 같습니다. P(n,i)결과 배열이 원래 배열과 정확히 i 개의 전치만큼 차이가 날 확률로 합시다 .
우리는 알고 싶습니다 P(n,0). 사실 :
P(n,0) =
1/n * P(n-1,0) + 1/n^2 * P(n-1,1) =
1/n * P(n-1,0) + 1/n^2 * (1-1/(n-1)) * P(n-2,0)
설명 : 우리는 두 가지 방법으로 원래 배열을 얻을 수 있습니다. 이미 좋은 배열에서 "중립"전치를 만들거나 "나쁜"전치 만 되 돌리는 것입니다. "나쁜"전치가 하나만있는 배열을 얻으려면 잘못된 전치가 0 인 배열을 가져와 중립이 아닌 전치 하나를 만들 수 있습니다.
편집 : P (n-1,0)에서 -1 대신 -2
완전한 해결책은 아니지만 적어도 무언가입니다.
효과가없는 특정 스왑 세트를 사용하십시오. 우리는 스왑이 총 n스왑을 사용하여 크기가 다른 루프를 형성 한 경우가 틀림 없다는 것을 알고 있습니다. (이를 위해 효과가없는 스왑은 크기 1의 루프로 간주 될 수 있습니다.)
아마도 우리는
1) 루프의 크기에 따라 그룹으로 나누십시오.
2) 각 그룹을 얻는 방법의 수를 계산하십시오.
(가장 큰 문제는 거기에 있다는 것입니다 t 다른 그룹의,하지만 난 당신이 계정에 다른 그룹을하지 않는 경우에 당신이 실제로이를 계산하는 것 어떻게 아니에요.)
흥미로운 질문입니다.
대답은 1 / N이라고 생각하지만 증거가 없습니다. 증거를 찾으면 답을 수정하겠습니다.
지금까지 얻은 것 :
m == n이면 배열을 변경하지 않습니다. N ^ 2 옵션이 있고 N 만 적합하기 때문에 m == n을 얻을 확률은 1 / N입니다 ((i, i) 모든 0 <= i <= N-1).
따라서 우리는 N / N ^ 2 = 1 / N을 얻습니다.
Pk를 k 번의 스왑 반복 후 크기 N의 배열이 동일하게 유지 될 확률을 나타냅니다.
P1 = 1 / N. (아래에서 보듯이)
P2 = (1 / N) P1 + (N-1 / N) (2 / N ^ 2) = 1 / N ^ 2 + 2 (N-1) / N ^ 3.
Explanation for P2:
We want to calculate the probability that after 2 iterations, the array with
N elements won't change. We have 2 options :
- in the 2 iteration we got m == n (Probability of 1/N)
- in the 2 iteration we got m != n (Probability of N-1/N)
If m == n, we need that the array will remain after the 1 iteration = P1.
If m != n, we need that in the 1 iteration to choose the same n and m
(order is not important). So we get 2/N^2.
Because those events are independent we get - P2 = (1/N)*P1 + (N-1/N)*(2/N^2).
Pk = (1 / N) * Pk-1 + (N-1 / N) * X. (첫 번째는 m == n, 두 번째는 m! = n)
X가 무엇인지 더 많이 생각해야합니다. (X는 상수 또는 다른 것이 아니라 실제 공식을 대체합니다.)
Example for N = 2.
All possible swaps:
(1 1 | 1 1),(1 1 | 1 2),(1 1 | 2 1),(1 1 | 2 2),(1 2 | 1 1),(1 2 | 1 2)
(1 2 | 2 1),(1 2 | 2 2),(2 1 | 1 1),(2 1 | 1 2),(2 1 | 2 1),(2 1 | 2 2)
(2 2 | 1 1),(2 2 | 1 2),(2 2 | 2 1),(2 1 | 1 1).
Total = 16. Exactly 8 of them remain the array the same.
Thus, for N = 2, the answer is 1/2.
편집 : 다른 접근 방식을 소개하고 싶습니다.
스왑을 건설적 스왑, 파괴적 스왑 및 무해한 스왑의 세 그룹으로 분류 할 수 있습니다.
구성 적 스왑은 하나 이상의 요소가 올바른 위치로 이동하도록하는 스왑으로 정의됩니다.
파괴적 스왑은 하나 이상의 요소가 올바른 위치에서 이동하도록하는 스왑으로 정의됩니다.
무해한 스왑은 다른 그룹에 속하지 않는 스왑으로 정의됩니다.
이것이 가능한 모든 스왑의 파티션임을 쉽게 알 수 있습니다. (교차점 = 빈 세트).
이제 내가 증명하고 싶은 주장 :
The array will remain the same if and only if
the number of Destructive swap == Constructive swap in the iterations.
반례가있는 사람이 있으면 댓글로 적어주세요.
이 주장이 맞다면, 우리는 모든 조합을 취하여 0 개의 무해한 스왑, 1 개의 무해한 스왑, .., N 무해한 스왑을 합산 할 수 있습니다.
그리고 가능한 k 개의 무해한 스왑에 대해 Nk가 짝수인지 확인하고 그렇지 않은 경우 건너 뜁니다. 그렇다면 파괴적인 경우 (Nk) / 2를, 건설적인 경우 (Nk)를 사용합니다. 그리고 모든 가능성을보십시오.
노드가 배열의 요소이고 스왑이 그들 사이에 무 방향 (!) 연결을 추가하는 다중 그래프로 문제를 모델링합니다. 그런 다음 어떻게 든 루프를 찾습니다 (모든 노드는 루프의 일부 => 원본)
작업에 복귀해야합니다! :(
음, 수학적 관점에서 :
배열 요소가 매번 같은 위치에서 교체되도록하려면 Rand (N) 함수가 int m 및 int n에 대해 동일한 숫자를 두 번 생성해야합니다. 따라서 Rand (N) 함수가 동일한 숫자를 두 번 생성 할 확률은 1 / N입니다. for 루프 안에서 N 번 호출 된 Rand (N)이 있으므로 확률은 1 / (N ^ 2)입니다.
C #의 순진한 구현. 아이디어는 초기 배열의 가능한 모든 순열을 만들고 열거하는 것입니다. 그런 다음 가능한 상태 변화 매트릭스를 만듭니다. 행렬 자체를 N 번 곱하면 순열 #i에서 순열 #j로 이어지는 N 단계에서 얼마나 많은 방법이 존재하는지 보여주는 행렬을 얻을 수 있습니다. Elemet [0,0]은 동일한 초기 상태로 이어지는 방법을 보여줍니다. 행 # 0의 요소 합계는 다양한 방법의 총 수를 표시합니다. 전자를 후자로 나누어 확률을 얻습니다.
실제로 총 순열 수는 N ^ (2N)입니다.
Output:
For N=1 probability is 1 (1 / 1)
For N=2 probability is 0.5 (8 / 16)
For N=3 probability is 0.1851851851851851851851851852 (135 / 729)
For N=4 probability is 0.068359375 (4480 / 65536)
For N=5 probability is 0.0193664 (189125 / 9765625)
For N=6 probability is 0.0057198259072973293366526105 (12450816 / 2176782336)
class Program
{
static void Main(string[] args)
{
for (int i = 1; i < 7; i++)
{
MainClass mc = new MainClass(i);
mc.Run();
}
}
}
class MainClass
{
int N;
int M;
List<int> comb;
List<int> lastItemIdx;
public List<List<int>> combinations;
int[,] matrix;
public MainClass(int n)
{
N = n;
comb = new List<int>();
lastItemIdx = new List<int>();
for (int i = 0; i < n; i++)
{
comb.Add(-1);
lastItemIdx.Add(-1);
}
combinations = new List<List<int>>();
}
public void Run()
{
GenerateAllCombinations();
GenerateMatrix();
int[,] m2 = matrix;
for (int i = 0; i < N - 1; i++)
{
m2 = Multiply(m2, matrix);
}
decimal same = m2[0, 0];
decimal total = 0;
for (int i = 0; i < M; i++)
{
total += m2[0, i];
}
Console.WriteLine("For N={0} probability is {1} ({2} / {3})", N, same / total, same, total);
}
private int[,] Multiply(int[,] m2, int[,] m1)
{
int[,] ret = new int[M, M];
for (int ii = 0; ii < M; ii++)
{
for (int jj = 0; jj < M; jj++)
{
int sum = 0;
for (int k = 0; k < M; k++)
{
sum += m2[ii, k] * m1[k, jj];
}
ret[ii, jj] = sum;
}
}
return ret;
}
private void GenerateMatrix()
{
M = combinations.Count;
matrix = new int[M, M];
for (int i = 0; i < M; i++)
{
matrix[i, i] = N;
for (int j = i + 1; j < M; j++)
{
if (2 == Difference(i, j))
{
matrix[i, j] = 2;
matrix[j, i] = 2;
}
else
{
matrix[i, j] = 0;
}
}
}
}
private int Difference(int x, int y)
{
int ret = 0;
for (int i = 0; i < N; i++)
{
if (combinations[x][i] != combinations[y][i])
{
ret++;
}
if (ret > 2)
{
return int.MaxValue;
}
}
return ret;
}
private void GenerateAllCombinations()
{
int placeAt = 0;
bool doRun = true;
while (doRun)
{
doRun = false;
bool created = false;
for (int i = placeAt; i < N; i++)
{
for (int j = lastItemIdx[i] + 1; j < N; j++)
{
lastItemIdx[i] = j; // remember the test
if (comb.Contains(j))
{
continue; // tail items should be nulled && their lastItemIdx set to -1
}
// success
placeAt = i;
comb[i] = j;
created = true;
break;
}
if (comb[i] == -1)
{
created = false;
break;
}
}
if (created)
{
combinations.Add(new List<int>(comb));
}
// rollback
bool canGenerate = false;
for (int k = placeAt + 1; k < N; k++)
{
lastItemIdx[k] = -1;
}
for (int k = placeAt; k >= 0; k--)
{
placeAt = k;
comb[k] = -1;
if (lastItemIdx[k] == N - 1)
{
lastItemIdx[k] = -1;
continue;
}
canGenerate = true;
break;
}
doRun = canGenerate;
}
}
}
반복 할 때마다 m == n이 될 확률입니다. P (m == n) = 1 / N. 그래서 저는 그 경우에 대해 P = 1 / (n ^ 2)라고 생각합니다. 그러나 그런 다음 값이 다시 바뀐다는 것을 고려해야합니다. 그래서 대답은 (텍스트 편집기가 나를 얻었습니다) 1 / N ^ N이라고 생각합니다.
질문 : 배열 A가 동일하게 유지 될 확률은 얼마입니까? 조건 : 배열에 고유 한 요소가 포함되어 있다고 가정합니다.
Java로 솔루션을 시도했습니다.
무작위 스와핑은 기본 int 배열에서 발생합니다. 자바 메소드에서 매개 변수는 항상 값으로 전달되므로 스왑 메소드에서 발생하는 일은 배열의 a [m] 및 a [n] 요소 (아래 코드에서 swap (a [m], a [n]))가 중요하지 않습니다. 완전한 배열이 아닙니다.
대답은 배열이 동일하게 유지된다는 것입니다. 위에서 언급 한 조건에도 불구하고. 아래 자바 코드 샘플을 참조하세요.
import java.util.Random;
public class ArrayTrick {
int a[] = new int[10];
Random random = new Random();
public void swap(int i, int j) {
int temp = i;
i = j;
j = temp;
}
public void fillArray() {
System.out.println("Filling array: ");
for (int index = 0; index < a.length; index++) {
a[index] = random.nextInt(a.length);
}
}
public void swapArray() {
System.out.println("Swapping array: ");
for (int index = 0; index < a.length; index++) {
int m = random.nextInt(a.length);
int n = random.nextInt(a.length);
swap(a[m], a[n]);
}
}
public void printArray() {
System.out.println("Printing array: ");
for (int index = 0; index < a.length; index++) {
System.out.print(" " + a[index]);
}
System.out.println();
}
public static void main(String[] args) {
ArrayTrick at = new ArrayTrick();
at.fillArray();
at.printArray();
at.swapArray();
at.printArray();
}
}
샘플 출력 :
채우는 배열 : 인쇄 배열 : 3 1 1 4 9 7 9 5 9 5 교환 배열 : 인쇄 배열 : 3 1 1 4 9 7 9 5 9 5
'IT TIP' 카테고리의 다른 글
| 1000 개의 Entity Framework 개체를 만들 때 SaveChanges ()를 언제 호출해야합니까? (0) | 2020.10.24 |
|---|---|
| ASP.NET MVC에서 Error.cshtml은 어떻게 호출됩니까? (0) | 2020.10.24 |
| -D 매개 변수 또는 환경 변수를 Spark 작업에 전달하는 방법은 무엇입니까? (0) | 2020.10.24 |
| 왜 instanceof가 babel-node 아래에있는 Error 서브 클래스의 인스턴스에서 작동하지 않습니까? (0) | 2020.10.24 |
| Docker : 마운트가 거부되었습니다. (0) | 2020.10.24 |