Этот вопрос задан в интервью 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]);
}
EDIT: Обратите внимание, что семя не исправлено.
Какова вероятность того, что массив A останется прежним?
Предположим, что массив содержит уникальные элементы.
<суб > Ну, я немного поболтал с этим. Первое, о чем я думал, когда впервые прочитал эту проблему, была теория групп (в частности, симметричная группа S n). Цикл for просто строит перестановку σ в S n, создавая транспозиции (т.е. свопы) на каждой итерации. Моя математика не настолько эффектная, и я немного ржавая, поэтому, если мои обозначения несут меня. Суб >
Пусть A будет событием, когда наш массив не изменится после перестановки. В конечном итоге нам предлагается найти вероятность события A, Pr(A).
Мое решение пытается выполнить следующую процедуру:
Обратите внимание: каждая итерация цикла 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), и массив изменяется.
Пусть K_i является событием, в котором i тождественные транспозиции появляются в данной перестановке. Обратите внимание, что это является исчерпывающим разделом всех возможных результатов:
0 и N идентичными транспозициями.Таким образом, мы можем применить Закон общей вероятности:
Теперь мы можем, наконец, воспользоваться разделом. Обратите внимание, что, когда количество не-идентичных транспозиций нечетно, нет никакого способа, чтобы массив мог оставаться неизменным *. Таким образом:
* Из теории групп, перестановка четная или нечетная, но не каждая из них. Поэтому нечетная перестановка не может быть тождественной перестановкой (поскольку однозначная перестановка четна).
Итак, теперь мы должны определить две вероятности для 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). Таким образом, существуют возможности для достижения тождественной перестановки. Для полноты мы добавим биномиальный коэффициент 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 = 4 рассмотрим 2 тождественные транспозиции (т.е. i = N - 2 = 2). В качестве условного обозначения мы поместим два идентификатора в конце (и учет для последующего заказа). Теперь мы знаем, что нам нужно выбрать две транспозиции, которые при составлении станут перестановкой идентичности. Поместите любой элемент в первое место, назовите его 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 * ?
Итак, почему мы потратили минуту, чтобы более подробно рассмотреть число t2? Перестановки 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
Наконец, все вместе:
Так что это. Работайте назад, подставляя то, что мы нашли, в исходное суммирование, данное на шаге 2. Я вычислил ответ на случай N = 4 ниже. Он очень точно соответствует эмпирическому числу, найденному в другом ответе!
N = 4
M = 6 _________ _____________ _________
| Pr(K_i) | Pr(A | K_i) | Product |
_________|_________|_____________|_________|
| | | | |
| i = 0 | 0.316 | 120 / 1296 | 0.029 |
|_________|_________|_____________|_________|
| | | | |
| i = 2 | 0.211 | 6 / 36 | 0.035 |
|_________|_________|_____________|_________|
| | | | |
| i = 4 | 0.004 | 1 / 1 | 0.004 |
|_________|_________|_____________|_________|
| | |
| Sum: | 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 или более пунктами, которые являются "круговыми", как это.
Фактически, вместо того, чтобы рассматривать случаи, когда массив не изменяется, может быть проще рассмотреть случаи, когда он изменяется. Посмотрите, может ли эта проблема быть отображена на известную структуру, такую как Треугольник Паскаля.
Это сложная проблема. Я согласен с тем, что это слишком сложно решить в интервью, но это не значит, что его сложно задавать в интервью. У бедного кандидата не будет ответа, средний кандидат угадает очевидный ответ, и хороший кандидат объяснит, почему проблема слишком сложна для ответа.
Я считаю это "открытым" вопросом, который дает интервьюеру понимание кандидата. По этой причине, хотя это слишком сложно решить во время собеседования, это хороший вопрос, который следует задать во время интервью. Там больше задавать вопрос, чем просто проверять правильность или неправильность ответа.
Ниже приведен код C для подсчета числа значений 2N-кортежей индексов, которые rand может произвести и вычислить вероятность. Начиная с N = 0, он показывает количество 1, 1, 8, 135, 4480, 189125 и 12450816 с вероятностями 1, 1,.5,.185185,.0683594,.0193664 и .00571983. Графы не отображаются в Encyclopedia of 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;
}
Поведение алгоритма можно моделировать как цепь Markov по симметричная группа S N.
N элементов массива A может быть организовано в N! различные перестановки. Обозначим эти перестановки от 1 до N!, например. по лексикографическому порядку. Таким образом, состояние массива A в любое время в алгоритме может быть полностью охарактеризовано номером перестановки.
Например, для N = 3 возможна одна нумерация всех 3!= 6 могут быть:
На каждом шаге алгоритма состояние A либо остается неизменным, либо переходит из одной из этих перестановок в другую. Сейчас нас интересуют вероятности этих изменений состояния. Назовем Pr (i → j) вероятность изменения состояния от перестановки я до перестановки j в одной итерации цикла.
Поскольку мы выбираем m и n равномерно и независимо от диапазона [0, N-1], возможны N2 возможные результаты, каждый из которых одинаково вероятен.
Для N этих результатов выполняется m = n, поэтому изменений в перестановке нет. Следовательно,
.
Остальные случаи N² - N представляют собой транспозиции, т.е. два элемента обмениваются своими позициями, и поэтому перестановка изменяется. Предположим, что одна из этих транспозиций обменивает элементы в положениях x и y. Есть два случая, как эта транспозиция может быть сгенерирована алгоритмом: либо m = x, n = y, либо m = y, n = x. Таким образом, вероятность для каждой транспозиции равна 2/N².
Как это относится к нашим перестановкам? Назовем две перестановки я и j соседями тогда и только тогда, когда существует транспозиция, которая преобразует я в j (и наоборот). Тогда мы можем заключить:
Мы можем расположить вероятности Pr (i → j) в матрице перехода P ∈ [0,1] N! × N!. Определим
p ij= Pr (i → j),
где p ij - это запись в i-й строке и j-м столбце P. Обратите внимание, что
Pr (i → j) = Pr (j → i),
что означает, что P является симметричным.
Теперь ключевым моментом является наблюдение того, что происходит, когда мы умножаем P самостоятельно. Возьмем любой элемент p (2) ij of P ²:
Произведение Pr (i → k) · Pr (k → j) - вероятность того, что начиная с перестановки я мы перейдем на перестановку k за один шаг и перейдем к перестановке j после другого последующего шага. Таким образом, суммирование по всем промежуточным перестановкам k дает нам полную вероятность перехода из я в j за 2 шага.
Этот аргумент может быть расширен до более высоких степеней P. Особым следствием является следующее:
p (N) ii - это вероятность возврата к перестановке я после 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) ^ п). К сожалению, они не являются независимыми. Я чувствую, что оценка может быть показана с более сложным анализом. Ключевое слово - "проблема с шарами и корзинами".
Одно упрощенное решение
p >= 1/N N
Так как один из возможных способов остается неизменным, это если m = n для каждой итерации. И m равно n с возможностью 1 / N.
Это, безусловно, выше этого. Вопрос в том, сколько.
Вторая мысль: можно также утверждать, что если вы произвольно перетасовываете массив, каждая перестановка имеет равную вероятность. Так как существуют подстановки n!, вероятность получить только один (тот, который у нас есть в начале) равен
p = 1/N!
который немного лучше предыдущего.
Как обсуждалось, алгоритм является предвзятым. Это означает, что не каждая перестановка имеет одинаковую вероятность. Итак, 1 / N! не совсем точен. Вы должны выяснить, как распределяется перестановка.
FYI, не уверенный, что оценка выше (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, то вероятность = 1 для
все N.
Вот как это сделать. Пусть P(n,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 плохими транспозициями и сделать одну транспозицию, которая не является нейтральной.
EDIT: -2 вместо -1 в P (n-1,0)
Это не полное решение, но это как минимум.
Возьмите определенный набор свопов, которые не влияют. Мы знаем, что это должно было быть так, что его свопы закончили тем, что образовали кучу циклов разного размера, используя в общей сложности свопы n. (Для целей этого замена без эффекта может рассматриваться как петля размера 1)
Возможно, мы можем
1) Разделите их на группы, основываясь на размерах петель. 2) Рассчитайте количество способов получения каждой группы.
(Основная проблема заключается в том, что существует тонна различных групп, но я не уверен, как вы это вычисляете, если не учитывать разные группировки.)
Интересный вопрос.
Я думаю, что ответ 1/N, но у меня нет никаких доказательств. Когда я найду доказательство, я отредактирую свой ответ.
Что я получил до сих пор:
Если m == n, вы не измените массив. Вероятность получить m == n равна 1/N, так как существует N ^ 2 опций, и только N подходит ((i, i) для каждого 0 <= я <= 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.
РЕДАКТИРОВАТЬ: Я хочу ввести другой подход:
Мы можем классифицировать свопы к трем группам: конструктивные свопы, деструктивные свопы и безопасные свопы.
Конструктивный своп определяется как своп, который заставляет по крайней мере один элемент перемещаться в нужное место.
Деструктивный swap определяется как своп, который заставляет по крайней мере один элемент перемещаться из его правильной позиции.
Безвредный своп определяется как своп, который не относится к другим группам.
Легко видеть, что это разбиение всех возможных свопов. (пересечение = пустое множество).
Теперь требование, которое я хочу доказать:
The array will remain the same if and only if
the number of Destructive swap == Constructive swap in the iterations.
Если у кого-то есть встречный пример, напишите его как комментарий.
Если это утверждение верно, мы можем взять все комбинации и суммировать их - 0 безобидных свопов, 1 безобидных свопов,.., N безобидных свопов.
И для каждого возможного k безобидного свопа мы проверяем, является ли N-k четным, если нет, мы пропускаем. Если да, возьмем (N-k)/2 для деструктивного и (N-k) для конструктивного. И просто посмотрите все возможности.
Я бы смоделировал проблему как мультиграфию, где узлы являются элементами массива, а свопы добавляют непрямое (!) соединение между ними. Затем как-то найдите петли (все узлы являются частью цикла = > оригинала)
На самом деле нужно вернуться к работе!: (
хорошо, с математической точки зрения:
чтобы элементы массива менялись местами в одном и том же месте каждый раз, тогда функция Rand (N) должна генерировать одинаковое число дважды для int m и int n. поэтому вероятность того, что функция Rand (N) будет генерировать одно и то же число дважды, равна 1/N. и мы имеем Rand (N), называемый N раз внутри цикла for, поэтому мы имеем вероятность 1/(N ^ 2)
Наивная реализация в С#. Идея состоит в том, чтобы создать все возможные перестановки исходного массива и перечислить их. Затем мы строим матрицу возможных изменений состояния. Умножая матрицу на 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 на каждой итерации, тогда сделайте это N раз. P (m = n) = 1/N. Поэтому я думаю, что P = 1/(n ^ 2) для этого случая. Но тогда вы должны учитывать, что ценности меняются местами. Поэтому я думаю, что ответ (текстовый редактор получил меня) 1/N ^ N.
Вопрос: какова вероятность того, что массив A останется прежним? Условие: предположим, что массив содержит уникальные элементы.
Пробовал решение в Java.
Случайная свопинг происходит в примитивном массиве int. В java-методе параметры всегда передаются по значению, поэтому то, что происходит в методе подкачки, не имеет значения в качестве [m] и [n] элементов массива (из-под подкачки кода (a [m], a [n])) передал не полный массив.
Ответ: массив останется таким же. Несмотря на упомянутое выше условие. Ниже приведен пример кода Java:
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