Лото | |
---|---|
Владимир Максимов Автор Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Вообще-то, я не уверен, что решение средствами FoxPro в принципе существует. Точнее, что оно достаточно простое. Просто некоторое время назад один упорный товарищь добивался от меня ее решения, но я так ничего и не смог сделать...
В целом, это задача на формирование карточек лото. Но саму задачу несколько упрощаю, "выдергивая" ключевой момент. Итак, есть 3 "ячейки" (столбцы в карточке лото). Каждая ячейка может принимать фиксированное количество значений. Значения в каждой ячейке не одинаковые: 1 ячейка: 1, 2 2 ячейка: 11, 12 3 ячейка: 21, 22 Если выписать вообще ВСЕ возможные сочетания значений, то получим: 1 11 21 1 11 22 1 12 21 1 12 22 2 11 21 2 11 22 2 12 21 2 12 22 Если теперь подсчитать, сколько раз каждое значение было использовано, то получим, что каждое значение было использовано ровно 4 раза. Во всех сочетаниях 4 раза использовалась 1, 4 раза использовалась 2, 4 раза использовалось 11, ... Вопрос заключается в следующем: Можно ли составить алгоритм перебора варинатов значений такой, чтобы в результате получить набор вариантов, при котором каждое значение использовалось бы ровно 3 раза? А ровно 2 раза? И именно каждое. В этом-то и загвоздка... В общем случае, иметь возможность задать количество значений, при том, что это количество больше 1 и меньше максимально возможного. |
Re: Лото | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Вот это не то, что надо?
|
Re: Лото | |
---|---|
Владимир Максимов Автор Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Результат-то получается, но я что-то логику не пойму. Понятно, что "игра" идет с координатами (адресами), а не с самими значениями. Но не вполне понятно как? Можно объснить что тут к чему?
|
Re: Лото | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Hi Владимир!
Это все ограничения? Мне кадется что в стандартном русском лото ещё недопустимы три заполненных ячейки в одном столбце, а в одной строке должно быть ровно 5 заполненных ячеек (из 10)... Т.е. условия гораздо более строгие, и то что ты выделил не будет являться самым сложным... А что касается генерации - то один из способов, это сначала все варианты сделать, а потом уже выкидывать лишние. Правда я не уверен что если делать это "просто" - т.е. ориентируясь лишь на данные текущего состояния массива, то мы не попадём в тупик - когда ещё надо выкидывать и выкидывать лишние карточки, а граничное условие уже будет нарушаться... Другой способ - создать "кучи" чисел (например в виде курсора ) и вынимать числа из них (удалять записи из курсора) - подыскивая им место на незаполненных карточках. ------------------ WBR, Igor |
Re: Лото | |
---|---|
Владимир Максимов Автор Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Разумеется, это не все условия! Просто я "выдернул" тот кусок, который тогда не смог решить. Все остальное вроде бы не вызывало проблем.
Хотя мысль "сформировать все, потом выкинуть лишнее", почему-то тогда мне в голову не пришла. На первый взгляд, кажется, это самое простое решние, но, "на второй", а чем это отличается от собственно описанной постановки задачи? Результат-то надо получить тот же - список вариантов с фиксированным количеством повторов. Только их надо не сформировать, а выбросить. Ну, через "кучи" я и делал. Виртуальные, правда. Т.е. физически кучи не создавал, а генерил их "на лету" с проверкой ранее сформированных значений. Поскольку генерация шла через RAND(), то получить одинаковое количество повторов при всем желании не удавалось. Несколько значений все-равно "выпадало". |
Re: Лото | |
---|---|
Foxtrot Сообщений: 3408 Откуда: Куда: Дата регистрации: 25.04.2003 |
вот мой вариант
------------------ Мойте ноги, моя ноги вы моете и руки |
Re: Лото | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
В курсоре tmp у нас m.t различных чисел от 0 до m.k^(m.n-1)-1. Будем их рассматривать как числа, имеющие (m.n-1) разрядов в системе счисления по основанию m.k. К каждому из этих чисел добавляется еще один разряд (чтобы разрядов было m.n) и в него ставится нолик. Эти числа записываются в масив ar2 (поразрядно в m.k-ричной системе счисления) в строчки 1, m.k+1, 2*m.k+1, ... Они являются базовыми для заполнения остальных строчек массива. Рассмотрим, как заполняются остальные строчки массива на примере куска от 1 до m.k. Берется первая строка, к каждому разряду добавляется единичка, берется, если необходимо, по модулю m.k, и записывается во вторую строчку. Затем к разрядам первой строчки добавляется двойка, и записывается в третью строку, и т.д. В результате в строках 1 - m.k в каждом разряде каждое значение встретится ровно по одному разу. Ну, а во всем массиве ar2 каждое значение встретится m.t раз. В принципе, нужно еще доказать, что в массиве ar2 не будет одинаковых строчек, но это довольно легко понять, учитывая что в строках 1, m.k+1, 2*m.k+1, ... значения разные (это следует из того, что в массиве tmp все числа разные) и из метода построения остальных строк.
|
Re: Лото | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Hi Владимир!
В том то и дело, что RAND() надо использовать лишь на самом последнем этапе - для "перемешивания" уже сформированных карточек. А вот сами карточки формировать лучше не случайным образом, а строго последовательным И ничего тогда не будет пропадать. Тупой алгоритм - каждой карточке присвоить RAND() номер (можно и с повторениями!), и потом отсортировать карточки по этому номеру (а если они в таблице, то просто сделать индекс). Можно совместить оба процесса - т.е. рандомизировать не саму генерацию карточек, а их "размещение" в итоговом массиве (но это сложнее, т.к. тут без хорошей оптимизации, битовых карт "заполненности" массива или структур типа "список с возможностью вставки в произвольную позицию" и тому подобной ерунды не обойтись). Сложность будет в том, что получится огромный массив, а т.к. фокс не может эффективно работать с памятью (имеется в виду на низком уровне - т.е. грубо говоря представлять всю карточку как 30-40 байт, а все карточки как Сишный массив таких структур) то и тормоза будут жуткие. Даже на том-же C#, если представлять карточку как полноценный объект - будут тормоза, а вот если представить как 30 байт, и манипулировать именно так - то получим вполне неплохую производительность (если конечно массив целиком поместится в памяти). Я слал либо сюда, либо на sql.ru какой-то алгоритм для "проверки" лотереи (коллеги помоли - нарисовали на C#) - ибо на фоксе производительность была действительно значительно ниже (хотя бы потому что он все переменные оборачивает в свой аналог Variant-а, а если писать в файл то прилично тормозят дисковые операции). ------------------ WBR, Igor |
Re: Лото | |
---|---|
Владимир Максимов Автор Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Игорь, ты не понял проблему. Ты как раз описываешь алгоритм, которым я первоначально попытался решить задачу. Не решается она таким образом!
Чтобы было понятно, возьмем тот пример, который я приводил в условии. Формируем полный массив всех возможных вариантов. 1 11 21 1 11 22 1 12 21 1 12 22 2 11 21 2 11 22 2 12 21 2 12 22 Теперь, из этого массива надо "выдернуть" такой набор, чтобы каждого значения было ровно 3 штуки. Предположим, что отобрали первые 3 варианта 1 11 21 1 11 22 1 12 21 Имеем: число 1 - 3 раза, число 2 - 0 раз, число 11 - 2 раза, число 12 - 1 раз, число 21 - 2 раза, число 22 - 1 раз Число 1 выбрано уже предельное количество раз (3 раза). Больше его использовать нельзя. Значит, остаются только варианты с числом 2 (он вообще еще ни разу не было использовано). Берем первое попавшееся из набора 2 11 21 Достигли предела по числам 11 и 21 - тоже оказались взяты ровно 3 раза. Значит, использовать вариант, который содержит числа 1, 11 и 21 - уже нельзя. Будет переполнение. Из оставшихся вариантов осталось 2 12 22 И все. Больше ничего взять нельзя, поскольку будет переполнение по какому-то из чисел. Но полученный набор вариантов не дает одинакового количества значений для всех чисел. Для чисел 2, 12 и 22 получаем, что они были выбраны только 2 раза из требуемых 3! С другой стороны, набор, который содержит ровно по 3 раза каждое число реально существует. Его можно подобрать. Вопрос в том, каким образом выполнить этот подбор. Вот именно про это я говорил. Не получается случайным образом делать отбор. Нужен некий алгоритм отбора. |
Re: Лото | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Hi Владимир!
Не, это ты не понял что я хотел сказать Цитата:В точности твоя ситуация. Цитата:Перемешивание # отбор - это лишь дополнительная ступень обработки, чтобы карточки не шли "по порядку" - сначала все начинающиеся на 1, потом все на 2... Т.е. в твоём примере это то что надо сделать после того как из 8-ми мы отобрали 4 (если надо по 2 каждое число) или 6 (это если надо по 3 каждого) карточек. Я вовсе не предлагал использовать RAND() для отбора - хотя ЧАСТИЧНО он конечно может применяться - например когда мы выясним что надо выкинуть либо A либо B, то вполне логично выбирать из них через RAND() - для повышения "качества" отбора. Хотя алгоритму отбора должно быть без разницы - будет выбран кандидат случайно, или просто взят первый подходящий... Есть алгоритмы с "откатом" - т.е. например в твоём случае после того как мы взяли на N шаге 2,11,21 мы обнаружили что на N+1 шаге отбор заканчивается, но заканчивается неудовлетворительно (не выполнено условие "равенства вхождения") - значит надо вернуться на N шаг и повторить его, но уже С УЧЁТОМ полученного опыта (т.е. не выбирать 2,11,21, а выбрать что-то иное). Ессно что может оказаться так, что мы будем возвращаться на N шаг столько раз, что в конце концов окажется что выбирать больше не из чего - а значит надо будет возвращаться на N-1 шаг... И так вплоть до того как мы не получим нужное решение, или до тех пор пока мы не убедимся что его нету (т.е. это когда мы будем возвращаться на 1-шаг столько раз, что в итоге для отбора окажутся заблокированными ВСЕ карточки). По сути это перебор, но перебор направленный. Как его оптимизировать - отдельный вопрос... ------------------ WBR, Igor |
Re: Лото | |
---|---|
Владимир Максимов Автор Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Игорь, теперь кажется понял о чем речь. Спасибо.
Леонид, Канат, я чуть попозже попробую понять Вашу логику. Сейчас просто сил нет |
Re: Лото | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Hi, Igor
В предложенном тобой методе есть недостаток: он все-таки недостаточно рандомизирован. При определенных параметрах может, например, получиться результат 1,1,1,1,1,1,1,1,1,1 2,2,2,2,2,2,2,2,2,2 1,1,1,1,1,1,1,1,1,2 2,2,2,2,2,2,2,2,2,1 И сколько это строчки потом не перемешивай, они все-равно будут похожи друг на друга. В предложенном мной методе этот недостаток тоже имеется, хотя наверное и в несколько меньшей степени. Подумав на досуге, я придумал еще один способ, который по-видимому даст максимальную рандомизированность результата
Идея в принципе та же, что и предыдущем методе, результат строится блоками, в каждом из которых нужное значение встречается ровно 1 раз. Только в первом случае отсутствие одинаковых строк в результате достигалось с помощью определенного алгоритма (что снижало рандомизированность), а здесь здесь достигается грубой проверкой и переделыванием блока в случае необходимости. Этот метод может плохо (медленно) работать, если m.t достаточно большое, но если m.t существенно меньше m.k^(m.n-1), то все будет работать нормально. |
Re: Лото | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Hi leonid!
Описанную тобой проблему (для алгоритма отбора) легко решить - причём даже разными способами: 1) Перемешать карточки ДО выполнения отбора. 2) При отборе выбирать не "первую подходящую" (это кстати помимо прочего будет жутко неэффективно), а "случайную" карточку из некоторого набора "предпочтительных". Однако это не решает его основную проблему - скорость... Увы, но при росте размеров выборки скорость просто катастрофически падает Оно и понятно - уже для карточек из 3 колонок по 3 разных числа в каждой и требуемой "повторяемости" скажем 5 существует более 17 миллионов возможных "отборов" (27 карточек из которых надо выбрать 15). А для карточек из 12 колонок по 10 возможных чисел в каждой и требуемой повторяемости в 25 - как у тебя в примере существует просто невообразимое число вариантов отбора - число из более чем 2500 знаков (выбор 250 карточек из 1 триллиона=1e12 возможных). Одна генерация такого массива карточек займёт уйму времени, а в фоксе наверняка будет вообще невозможна (даже если умудрится запихать всю карточку в 1 байт, то потребуется около 1 Терабайта только для их хранения). Так что алогритм "генерации" тут выигрывает на 1000% ------------------ WBR, Igor |
© 2000-2024 Fox Club  |