Sinclair, еще раз повторю - первоначальный алгоритм просеивания (без итераций) некорректен - он дает неверные маргинальные распределения, и не столько потому, что "не может обнаружить событий с нулевой вероятностью", а потому, что при формировании нужного маргинального распределения одной компоненты отбрасываются(не отбрасываются) реализации, которые НЕ НУЖНО(НУЖНО) отбрасывать для формирования маргинального распределения другой компоненты (сродни "перетягиванию одеяла")! Потому и необходимы итерации, чтобы как-то "прийти к общему знаменателю". Чтобы убедиться в этом, возьмите, например, в качестве маргинальных
[ для этого случая в совместном распределении уже не нужно, чтобы обязательно были значения с нулевыми вероятностями (исключая диагональные)] и примените алгоритм без итераций - убедитесь, что результат будет неверным.
Я еще вчера прочитал этот ваш пост. В общем, я понял написанное.
Ощутил печаль. И думал снова пол ночи, что можно сделать.
Набрел на такой алгоритм:
1) Генерируем ряд исходов по маргинальным распределениям, безо всяких отсевов.
Часть исходов будут недопустимыми (ладьи на одной линии).
Выделяем их в отдельную группу.
Смотрим на получившееся распределение отсеянных вариантов. Если мы подберем соответствующее колличество допустимых вариантов, как можно ближе соответствующих этому распределению - то получившиеся маргинальные распределения будет теми же, которые получились бы при генерации, если бы несовместных исходов не было вовсе.
2) Подбираем совместные исходы, соответствующих "отбракованному распределению". Как это сделать - отдельный разговор
3) Получившееся распределение будет болеть той же болезнью, что и остальные алгоритмы (про нулевую совместную вероятность). Решать его надо, как я придумал позапрошлой ночью:
post674071.html#p674071 (просевом окончательной выборки)
Как не трудно заметить, это разновидность второго алгоритма из оппоста, который всплывал несоклько раз по ходу треда.
Теперь, надо описать подалгоритм генерации допустимых исходов по отбракованному распределению (расписать пункт 2 приведенного выше алгоритма). Сначала для случаев, когда нельзя стоять на одной клетке, а на одной линии можно:
Сразу оговоримся, что это будет особое распределение. Оно будет целочисленным. Каждый раз, когда мы будем получать на 1м шаге вышеприведенного алгоритма недопустимый исхода вида (a, b, c), где a будет равно b, или b равно с, или a равно с, мы будем увеличивать на 1 реализацию a маргинального спектра первой фишки, на 1 реализацию b второй фишки, и на 1 реализацию с третьей.
То есть, это просто более удобное представление распределения для моей задачи. Ну чтобы не путаться с терминологией, можно называть это "спектром".
Если мы будем просто генерировать исходы по этому спектру - мы будем получать еще больше "коллизий", чем при исходной генерации. Потому мы сделаем следующее:
a) просуммируем спектры для всех фишек.
b) найдем элемент суммарного спектра с самым большим значением. Его нужно тратить в первую очередь, чтобы минимизировать число коллизий.
c) посмотрим, какой из маргинальных спектров имеет наиболее колличество этих элементов. Возьмем его. Это будет позиция фишки, соответствующей этому спектру.
d) теперь надо выбрать позицию следующей фишки. В общем, выбираем ее так же, только с запретом занимать уже занятую позицию. Берем суммарные маргинальные спектры оставшихся фишек, откидываем занятый вариант, берем максимальный элемент, смотрим, какой спект внес больший вклад в эту позицию, и это и будет позиция соответствующей этому спектру фишки.
e) с последней фишкой и вовсе все просто - берем из ее спектра самый большой неиспользованный элемент.
f) перейдем на начало, пока спектры не нулевые
Данный алгоритм будет "тратить" изначально наиболее склонные к коллизиям области спектра.
Если мы доходим до коллизии - останавливаем алгоритм, и остаток отбрасываем со словами - "мы сделали все, что могли". Впрочем, мне кажется, что коллизии при этом алгоритме возникнут не может. Но точного доказательства нет.
Я, вообще, понимаю, что описал сумбурно. Но я надеюсь, что идею можно уловить.
В принципе, такой алгоритм можно сделать прямо для всего исходного распределения. Умножить распределение на миллион, получить из распределений спектры, которые необходимо потратить, и начать их тратить.
Понятно, что хотя маргинальные спектры будут теми же самыми - мы сильно подпортим совместное распределение таким алгоритмом. Что ж. В приведенном мною варианте, когда мы пропускаем через этот алгоритм только часть исходов - негативные последствия этого будут меньше. Тем более, что и с ними, думаю, можно бороться.
Вот такой алгоритм. Похоже, ничего другого не остается. Что же, тут по крайней мере затраты вычислительные просто минимальны (а это большой плюс для меня)
Надо додумать, как его модифицировать для ладей, пробивающих линии, впрочем, похоже, это не сложно, и как можно снизить деформацию совместного распределения от такой вот "генерации по максимуму". Наверное надо придумать какое-то условие, при котором будет заведомо известно, что оставшийся спектр можно потратить без коллизий, и пока это условие выполняется - тратить его вероятностно, оставив для "генерации по максимуму" только "кочерыжку.