Равномерное распределение чисел в ряду

Здравствуйте.

Имеется обычный ряд чисел.
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Необходимо равномерно и как можно максимально отдалить соседей друг от друга...
Перебором на бумажке у меня получается так:
[1, 4, 7, 2, 5, 8, 3, 6, 9]

то есть в среднем разница между соседями составляет 3. Есть проблемы:

1. Нет алгоритма. Реально цифр может быть и больше и меньше.
2. Не уверен, что это самый лучший вариант.

Пожалуйста, помогите...

0

Сообщение от Antohsa Вроде бы получилось сформулировать оценку качества.

не получилось
Вы хотите суперкомпьютер за минимальную сумму

0

ВНИАМНИЕ. МНОГО ТЕКСТА.

Уххх..... Вроде бы решил... Полностью потратил все субботу и половину воскресенья.... Сразу хочу предупредить, что я не программист, программирование это мое хобби со школы...

Пошел обратным путем. Если я не могу найти алгоритм, то найду результат работы этого алгоритма в лоб. Решил перебирать все вариации, находить лучшие и сравнивать их между собой.

Для четырех чисел (n=4) вариантов нет. Всегда будет плохо.

Для пяти сначала рекурсией перебрал вообще все возможные варианты, как я понимаю вариантов получается 5^5. Немного подкорректировал условия и взял только те, что не содержат повторов в цифрах, получилось 5! комбинаций, то есть 120. Из них выделил комбинации с наибольшей суммой по разности между членами. Вычислял разницу по модулю между текущим членом и следующим, далее все сложил. В итоге удалось выделить две комбинации с наибольшем качеством:

3 1 5 2 4
4 2 5 1 3

Если опираться на карты, то во второй комбинации двойка (то есть 7 в колоде), не поменяло местоположение, что плохо. Следуя этому критерию оставил только [3 1 5 2 4].

Далее взял n=6. Получилось 8 комбинаций. Выписал на бумажку, (нашел лучшую комбинацию) аналитически выяснилось, что есть комбинации которые просто записаны в обратном порядке, либо крайние члены лишь попарно заменены между собой. Учел это, так же убрал комбинации в которых максимальный элемент занимает предпоследнее место, то есть туз на n-1 позиции, убрал когда 1 на второй позиции (то есть в картах 6), так как эти комбинации будут априори хуже, чем другие.

Другими словами с каждым следующим n я ужесточал критерий отбора. Сами критерии удавалось выявить аналитически.

После того, как я до шел n=8 и вернулся, к n = 6, программы выдала только одну комбинацию вместо 8, как раз ту, что я нашел самостоятельно на бумажке.

Но бесконечно ужесточать критерий отбора я не могу, так как получается слишком расплывчатая и сложная логика. Когда выписываешь все на бумажку и смотришь своими глазами, то сравнить одну комбинацию с другой или выделить лучшую из группы, не составляет особого труда, можно найти тот или иной критерий, но запрограммировать их мне не под силу.

После всех ужесточений для n=7 получилось 4 комбинации, для n=8 получилось 12 комбинаций, для n=9 получилось 16 комбинаций. Последовательно выписал все на бумажку, выделил самые лучшие комбинации. Получил:

3 1 5 2 4
3 6 2 5 1 4
4 7 2 6 1 5 3
4 7 1 6 2 8 3 5
5 3 8 1 7 4 9 2 6

Последнюю комбинацию в виде карт можно записать так:
10 8 К 6 Q 9 A 7 J

Можно поспорить о качестве, но из всех зол я выбрал меньшее.

Далее, если колода с 2 до туза до в колоде 13 карт. То есть n=13;
Для n = 10 я получил 113 комбинаций.
Для n = 11 - получилось 740 комбинаций.
Для n = 12 - получилось 3319 комбинаций.
Для n = 13 после очень долгих раздумий выдал ошибку: Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

То есть просто не хватает памяти (8 ГБ оперативки и 15 Гб подкачка (если она важна конечно)). Программа проходит 13^13 степени комбинаций, берет только уникальные, а это 13!. Но 13! = 6227020800 вариантов (более 6 триллионов). 13! комбинаций все равно надо обработать. Конечно, я думаю, что можно оптимизировать и все таки заставить найти все комбинации, но при n=12 я уже получал более 3к вариантов. Что же будет при n = 13? Обработать это аналитические не представляется возможным.

В итоге, к сожалению, я вернулся к тому же, с чего начал. - нужен алгоритм.... =(((

Теперь сижу смотрю на полученные комбинации (n=5..9), пытаюсь найти закономерности.

Да...а в конце мне надо всю колоду так перемешать... =(((((

0

Мне кажется суть перемешивания карт это полное отсутствие закона и невозможность его вывода. Вводя любые правила в рендом вы создаете закономерность положения и наверно возможность предсказания карты (ухудшаете перемешивание).

Зачем вам такие странные правила? Цель перемешивания это невозможность получения закона о положении. Просто рендома вполне достаточно.
Усложнить? Создаете рендом колоду. Анализ всего массива сколько повторов и где они. Переставляете где повторы с учетом масти и все.

0

Да нет. Мне не надо перемешать карты для игры... вернее надо, но качественно. Примерно такую задачу я и решаю. Если перемешивать просто shuffle() (а на самом деле там по ходу как раз таки зашит метод Fisher–Yates shuffle), то мы получаем от 5 до 15 карт совпавших по значению с пред. раскладом. По значению и масти от 1 до 5. Использую 36 карт. Таким образом надо бы следить, что бы каждый расклад был уникальным от предыдущего. Я это и делаю.

Но если контролировать лишь разницу между нынешней колодой и предыдущий вполне вероятно можно получить 4 вальта подряд, или 4 туза подряд, поэтому необходимо контролировать и качество перемешивания в этом плане. Так как критерий очень размыт, мне хочется найти предельный случай, с наибольшим равномерным разбросом карт, чтобы было от чего отталкиваться. Если у вновь получаемой колоды слишком низкое качество (много подряд одной масти, повторения по значению, последовательности по значению), то перемешиваем снова, либо корректируем. Здесь проблема в словах "слишком низкое". Если узнать максимальный уровень этого значения (что я и пытаюсь сделать), то тогда и можно будет установить и минимальный допустимый уровень.

Я совершено не хочу использовать полученную "идеальную" колоду для игры. Она будет как бы эталоном.

Единственное, что остается для меня загадкой, какого качества колоду и насколько она получается отличной от пред в реальной жизни, при перемешивании карт руками... тут надо бы провести натурный эксперимент, но чувствую выборка будет слишком мала (которую реально можно сделать одному человеку), в отличии количества комбинация.

П.С: ну и все таки хочется решить поставленную задачу с "идеальной" колодой. Я ведь сам себе задачи придумываю, сам и пытаюсь решить... вернее с вашей и с Божьей помощью....

0

IMHO, задача изначально неверно поставлена: "каждый расклад был уникальным".

На самом деле, каждая сдача должна быть непредсказуемой - знание предыдущей колоды ничего не дает для определения позиций карт в текущей. Это прямо противоположно вашим текущим устремлениям.

0

Хорошо. Согласен. Уникальной быть не должна, но все равно хоть как-то надо оценивать степень тасовки колоды? Если новая сдача на 50% такая же как предыдущая, наверное, это тоже перебор?

Хоть какой-то критерий должен быть...

0

Представьте "наихудший" для вас случай: новая колода идентична старой. И что? Кто-то мог это предсказать? Как например, дважды подряд выпадение орла в американской рулетке? Единственное, что должно вас заботить при тасовке - качество (криптографическое) PRNG.

0

Не совсем понимаю....

Вот взял одну колоду. Перемешал ее. Затем взял ее копию и перемешал ее 100 раз, каждый раз сравнивал с пред. вариантом. Получилось на 100 сдач в среднем 4 карты совпадают по значению и только 1 сдача была уникальной. Максимальное совпадение 10 карт. Можно даже вычислить мат ожидание появления совпадения по 10 картам.

Теперь возьмем ситуацию. Вы сыграли одну партию в дурака. Какая была колода в этой одной игре с некоторыми небольшими вариантами вычислить удалось. Играем второй раз. Вам на руки сдали карты, которые не совпали с прошлым разом, так же другой козырь. Таким образом в колоде + руки соперника осталось 29 карт. Казалось бы, что вероятность каждой карты 1/29, но так как вы знаете, что в среднем 4 карты совпадают с прошлой раздачи, то вероятность обнаружить нужную карту в с прошлой раздачи становится выше, то есть уже не равна 1/29. И чем больше Вы видите не совпавших карт, тем вероятность найти совпадения больше.

Я то пытаюсь сделать так, чтобы этих совпадений не было либо совсем, либо максимум 1-2 карты, и уж точно не 10.

Здесь: http://www.peoples.ru/science/... _diaconis/ можно прочитать, что достаточно лишь 7 реальных тосований карт (руками), чтобы добиться перестановки всех карт. Уж 7 раз мы все карты мешаем, а то и больше, поэтому скорее всего каждый раз мы получаем уникальную колоду, без повторов.

0

Antohsa, вам бы посетить курс теории вероятности или книжку какаю-нибудь хорошую почитать, тогда поймете, что ничего лучше рандома для перемешивания карт нет. Что из того, что 10 карт могут остаться на своих местах? Вы же не знаете какие это места. А сколько есть вариантов разложить 10 карт на 29 мест
Вы решили, что такая колода хорошо тасована

Сообщение от Antohsa 5 3 8 1 7 4 9 2 6

но ведь здесь идут по очереди мелкая, крупная, мелкая, крупная...
разве это хорошо?

0

Сообщение от Antohsa Я ведь сам себе задачи придумываю, сам и пытаюсь решить...

Мне кажется вы придумали странные и ненужные правила перемешивания, приклеили сюда математику и получили комбинаторный взрыв в расчетах.
Вам уже 4 человека говорит что рендом и все…

Включить наивного психолога.
Может причина постановки такой сложной придуманной задачи в эскапизме от других проблем? Например вы зная немого программирование и математику вынуждены работать в магазине продавцом, это подрывает ваши чувства, а в такой сложной и не решаемой задаче сбегаете от реальности?
Выключить наивного психолога.

0

Сообщение от Antohsa Я то пытаюсь сделать так, чтобы этих совпадений не было либо совсем, либо максимум 1-2 карты, и уж точно не 10.

Хорошо перемешанная колода - это когда ничего нельзя сказать про порядок карт.
Если про порядок карт можно сказать что-нибудь конкретное (например, "совпадений будет максимум 1-2"), то это уже заслуживает канделябра.

Нет ничего страшного в 10 и даже 20 совпадениях с предыдущим раскладом. Никто не мог это предсказать и, значит, никто не сможет это использовать (для обмана).
А вот если карты будут лежать "равномерно" (то есть, предсказуемо), то те, кто это заметит или узнает, получат незаконное преимущество.

Добавлено через 21 минуту

Сообщение от ProgJ но ведь здесь идут по очереди мелкая, крупная, мелкая, крупная...

Если будут играть вдвоём или вчетвером, то у одного будут все мелкие, а у другого все крупные.

0

Ребята...

Та комбинация, что я искал, не относится к игре. Я не собираюсь сдавать эту колоду на руки, мне нужна она была только для построения шкалы качества.

Сообщение от ProgJ Вы же не знаете какие это места

Я знаю какие это места и значение карт на этих местах. Из предыдущего расклада. Допустим осталось 20 карт, какие карты остались выяснить удалось. Знаем что 10 карт совпадают с пред. расклада. Остается сравнить колоды. Если разница в 10 картах, то сразу и получаем их позицию и значения. Если больше - не беда - вычисляем вероятность.... Если совпадает 5 карт, все тоже самое только не так явно все это становится... Где ошибка в моей логике?

Сообщение от ProgJ но ведь здесь идут по очереди мелкая, крупная, мелкая, крупная...

Как может быть по другому? Крупная, крупная, мелкая, мелкая? В этих комбинациях никогда не будет короля рядом с дамой, туза рядом с шестеркой, шестерка рядом с семеркой. Как разделить между собой 1,2,3? Остаются только "старшие" товарищи.

Сообщение от Excalibur921 Включить наивного психолога.

Пожалуйста, не надо его включать. Сейчас просто много времени, мой бизнес сезонный. В основном летний. Решил немного размять мозги....

Сообщение от Shamil1 Хорошо перемешанная колода - это когда ничего нельзя сказать про порядок карт.

Согласен.

Сообщение от Shamil1 Никто не мог это предсказать и, значит, никто не сможет это использовать

Но вот как раз, когда я слепо всегда использую рандом, я точно смогу сказать, что 4-5 карт совпадут с пред. расклада. Какие - выяснить удастся в ходе сдачи. Использовать можно по разному.

Не понимаю, почему всех так напрягает мысль проверить колоду перед сдачей? Хорошо, опустим мы это качество перемешивания. Не будем следить за тем, чтобы не было 4 вальта подряд... Но почему хотя бы не убрать совпадения? Это тоже никто не может предсказать, вернее, если это даже известно, то этим никак не воспользоваться.

0

Сообщение от Antohsa Но вот как раз, когда я слепо всегда использую рандом, я точно смогу сказать, что 4-5 карт совпадут с пред. расклада. Какие - выяснить удастся в ходе сдачи. Использовать можно по разному.

Точно Вы сказать не можете, Вы только можете посчитать вероятность этого события.
Приведите хотя бы один пример использования этой информации для получения преимущества в игре.

Добавлено через 9 минут

Сообщение от Antohsa Но почему хотя бы не убрать совпадения?

Потому что тем самым Вы меняете правила игры. И, что ещё хуже, Вы делаете это тайно.

Представьте, например, что Вы играете в покер на трёх картах.
Правила:
В колоде 3 карты: туз, король и дама. Каждому из игроков сдают по одной карте. Первый игрок может поставить или не поставить. Второй игрок может подравнять или выкинуть.
Стратегия:
С королём ставить нет смысла (оппонент подравняет с тузом и выкинет даму). С тузом надо ставить (оппонент может подравнять с королём). С дамой тоже нужно ставить (можно заставить оппонента выкинуть короля), но реже, чем с тузом.

А теперь представьте, что добрый дядя из хороших побуждений решил убрать совпадения. Теперь, глядя на свою карту, я смогу точно сказать, какая карта у оппонента. А он, бедняга, не знает, что добрый дядя убирает совпадения, поэтому я легко его обыграю.

0

Shamil1

Ваш пример с покером совсем в крайности впадает. Слишком узкая игра. В этом примере о какой-то перемешке карт речи быть не может.

Мой пример. Тоже утрирован, то чтобы проще было понять.
Вы узнали, что прошлая колода была такой: 2,10,9,3,4,8,7,6,5,4
Знаете, что при перемешке 2 карты совпадут (в тех же позициях будут те же карт).
Вы сыграли пол игры, в колоде осталось 5 карт. Вы поняли какие: 2,4,8,9,10. Записал их по порядку. Знаем только номинал, позиций не знаем.
До этого момента совпадений с пред. колодой не было.
Теперь сравним последние 5 карт пред. колоды и нынешней:

8,7,6,5,4
2,4,8,9,10

При условии, что мы знаем что 2 карты совпадут, сразу станет понятно, какие.. это 8 и 4. И позиции их ясны. Нынешняя колода имеет вид: 8 ? ? ? 4

Случай крайний. Но если не удастся вычислить карты точно, то вероятности будут отличаться от 1/n, где n количество оставшихся карт.

Где опять моя логика не верна?

0

Сообщение от Antohsa Где опять моя логика не верна?

Если у меня 5 раз подряд выпал орёл, то следующие 5 раз обязательно выпадет реверс?

Сообщение от Antohsa Ваш пример с покером совсем в крайности впадает. Слишком узкая игра.

Если карт больше, то всё то же самое. Только вместо 100% "перекоса" будет "55" или даже "50.5". Примерно, как если бы орёл выпадал с вероятностью 50.5%. Вроде бы почти 50, но достаточно, чтобы выиграть.
(Слышали про счётчиков в Блэкджек? Они как раз за счёт небольшого изменения вероятностей и выигрывают свои миллионы... ).

0