:: Игры Разума
Лото
Владимир Максимов
Автор

Сообщений: 14098
Откуда: Москва
Дата регистрации: 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 и меньше максимально возможного.
Ratings: 0 negative/0 positive
Re: Лото
leonid

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006
Вот это не то, что надо?
m.n=12 && kolichestvo jacheek
m.k=10 && kolichestvo elementov v jachejke
&& togda m.k^m.n - kolichestvo razlichnyh variantov
&& a m.k^(m.n-1) - kolichestvo povtorenij kazhdogo elementa
m.t=25 && trebuemoe kolichestvo povtorenij
local ar1(m.n, m.k) && massiv s vozmozhnymi elementami
for m.i=1 to m.n
for m.j=1 to m.k
ar1(m.i, m.j)=padl(m.i,2,"0")+chr(asc('A')+m.j-1) && naprimer
next
next
rand(-1)
create cursor tmp (f1 N(20,0))
do while reccount("tmp")< m.t
m.rc=reccount("tmp")
for m.i=1 to m.t-m.rc
insert into tmp values (rnd(0, m.k^(m.n-1)-1))
next
select distinct f1 from tmp into cursor tmp1
use in tmp
use dbf("tmp1") in 0 again alias tmp
use in tmp1
enddo
&& v kursore tmp m.t razlichnyh chisel ot 0 do m.k^(m.n-1)-1
&& v principe mozno bylo prosto vzjatj chisla ot 0 do m.t-1,
&& no dlja loto navernoe luchshe sluchajnye
local ar2(m.n, m.k*m.t)
select tmp
scan
ar2(1,(recno()-1)*m.k+1)=0
for m.i=2 to m.n
ar2(m.i,(recno()-1)*m.k+1)=int(f1/(m.k^(m.i-2)))%m.k
next
for m.j=2 to m.k
for m.i=1 to m.n
ar2(m.i,(recno()-1)*m.k+m.j)=(ar2(m.i,(recno()-1)*m.k+1)+m.j-1)%m.k
next
next
endscan
&& vot sobstvenno i vse, ostaljnoe - pokaz rezuljtata
create cursor tmp2 (f2 C(254))
for m.i=1 to m.k*m.t
m.f2=""
for m.j=1 to m.n
m.f2=m.f2+","+ar1(m.j, ar2(m.j, m.i)+1)
next
insert into tmp2 values (substr(m.f2,2))
next
&& kursor sostoit iz m.k*m.t strok, kotorye mozhno razbitj na m.t blokov
&& po m.k strok v kazhdom. V kazhdom bloke kazhdyj element vstrechaetsja
&& rovno odin raz. Krome togo, postroenie kursora iskljuchaet vozmozhnostj
&& nalichija odinakovyh strok
browse
function rnd && vozraschaet sluchajnoe celoe chislo ot m.n1 do m.n2
lparameter m.n1, m.n2
local m.n3, m.n4, m.it, m.rn
m.n3=int(m.n1)
m.n4=int(m.n2)
if m.n3>m.n4
return -1
endif
if m.n3=m.n4
return m.n3
endif
m.it=m.n4-m.n3+1
m.rn=m.n4+1
do while m.rn>m.n4
m.rn=m.n3+int(rand()*m.it)
enddo
return m.rn
Ratings: 0 negative/0 positive
Re: Лото
Владимир Максимов
Автор

Сообщений: 14098
Откуда: Москва
Дата регистрации: 02.09.2000
Результат-то получается, но я что-то логику не пойму. Понятно, что "игра" идет с координатами (адресами), а не с самими значениями. Но не вполне понятно как? Можно объснить что тут к чему?
Ratings: 0 negative/0 positive
Re: Лото
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Hi Владимир!

Это все ограничения? Мне кадется что в стандартном русском лото ещё недопустимы три заполненных ячейки в одном столбце, а в одной строке должно быть ровно 5 заполненных ячеек (из 10)... Т.е. условия гораздо более строгие, и то что ты выделил не будет являться самым сложным...

А что касается генерации - то один из способов, это сначала все варианты сделать, а потом уже выкидывать лишние. Правда я не уверен что если делать это "просто" - т.е. ориентируясь лишь на данные текущего состояния массива, то мы не попадём в тупик - когда ещё надо выкидывать и выкидывать лишние карточки, а граничное условие уже будет нарушаться...

Другой способ - создать "кучи" чисел (например в виде курсора ) и вынимать числа из них (удалять записи из курсора) - подыскивая им место на незаполненных карточках.


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Лото
Владимир Максимов
Автор

Сообщений: 14098
Откуда: Москва
Дата регистрации: 02.09.2000
Разумеется, это не все условия! Просто я "выдернул" тот кусок, который тогда не смог решить. Все остальное вроде бы не вызывало проблем.

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

Ну, через "кучи" я и делал. Виртуальные, правда. Т.е. физически кучи не создавал, а генерил их "на лету" с проверкой ранее сформированных значений. Поскольку генерация шла через RAND(), то получить одинаковое количество повторов при всем желании не удавалось. Несколько значений все-равно "выпадало".
Ratings: 0 negative/0 positive
Re: Лото
Foxtrot

Сообщений: 3408
Откуда: Куда:
Дата регистрации: 25.04.2003
вот мой вариант
limit=3
CLOSE TABLES
SET DELETED OFF
SET ESCAPE ON
CREATE CURSOR loto (cell1 I, cell2 I, cell3 I)
FOR x=1 TO 2
FOR y=11 TO 12
FOR z=21 TO 22
INSERT INTO loto VALUES (x, y, z)
ENDFOR
ENDFOR
ENDFOR
SELECT 0
CREATE CURSOR nums (num I, inuse I)
FOR x=1 TO 22
IF INLIST(x, 1,2,11,12,21,22)
INSERT INTO nums VALUES (x, 4)
ENDIF
ENDFOR
CALCULATE MIN(inuse), MAX(inuse) TO m1, m2
DO WHILE NOT (m1=limit AND m2=limit)
SELECT loto
SCAN ALL
SCATTER TO aa
FOR x=1 TO 3
SELECT nums
LOCATE FOR num=aa(x)
DO CASE
CASE inuse>limit AND DELETE("loto")=.F.
DELETE IN loto
z=-1
CASE inuse<limit AND DELETE("loto")
RECALL IN loto
z=1
OTHERWISE
LOOP
ENDCASE
FOR y=1 TO x
LOCATE FOR num=aa(y)
REPLACE inuse WITH inuse+z
ENDFOR
SELECT loto
SKIP z
ENDFOR
ENDSCAN
SELECT nums
REPLACE ALL inuse WITH 0
SELECT loto
SCAN FOR DELETED()=.F.
SCATTER TO aa
FOR x=1 TO 3
SELECT nums
LOCATE FOR num=aa(x)
REPLACE inuse WITH inuse+1
ENDFOR
ENDSCAN
SELECT nums
CALCULATE MIN(inuse), MAX(inuse) FOR DELETED()=.F. TO m1, m2
ENDDO
SET DELETED ON
SELECT loto
BROWSE


------------------
Мойте ноги, моя ноги вы моете и руки
Ratings: 0 negative/0 positive
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 все числа разные) и из метода построения остальных строк.
Ratings: 0 negative/0 positive
Re: Лото
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Hi Владимир!

В том то и дело, что RAND() надо использовать лишь на самом последнем этапе - для "перемешивания" уже сформированных карточек. А вот сами карточки формировать лучше не случайным образом, а строго последовательным И ничего тогда не будет пропадать.
Тупой алгоритм - каждой карточке присвоить RAND() номер (можно и с повторениями!), и потом отсортировать карточки по этому номеру (а если они в таблице, то просто сделать индекс).

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

Сложность будет в том, что получится огромный массив, а т.к. фокс не может эффективно работать с памятью (имеется в виду на низком уровне - т.е. грубо говоря представлять всю карточку как 30-40 байт, а все карточки как Сишный массив таких структур) то и тормоза будут жуткие. Даже на том-же C#, если представлять карточку как полноценный объект - будут тормоза, а вот если представить как 30 байт, и манипулировать именно так - то получим вполне неплохую производительность (если конечно массив целиком поместится в памяти). Я слал либо сюда, либо на sql.ru какой-то алгоритм для "проверки" лотереи (коллеги помоли - нарисовали на C#) - ибо на фоксе производительность была действительно значительно ниже (хотя бы потому что он все переменные оборачивает в свой аналог Variant-а, а если писать в файл то прилично тормозят дисковые операции).


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Лото
Владимир Максимов
Автор

Сообщений: 14098
Откуда: Москва
Дата регистрации: 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 раза каждое число реально существует. Его можно подобрать. Вопрос в том, каким образом выполнить этот подбор.

Вот именно про это я говорил. Не получается случайным образом делать отбор. Нужен некий алгоритм отбора.
Ratings: 0 negative/0 positive
Re: Лото
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Hi Владимир!

Не, это ты не понял что я хотел сказать
Цитата:
Правда я не уверен что если делать это "просто" - т.е. ориентируясь лишь на данные текущего состояния массива, то мы не попадём в тупик
В точности твоя ситуация.
Цитата:
RAND() надо использовать лишь на самом последнем этапе - для "перемешивания" уже сформированных карточек
Перемешивание # отбор - это лишь дополнительная ступень обработки, чтобы карточки не шли "по порядку" - сначала все начинающиеся на 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
Ratings: 0 negative/0 positive
Re: Лото
Владимир Максимов
Автор

Сообщений: 14098
Откуда: Москва
Дата регистрации: 02.09.2000
Игорь, теперь кажется понял о чем речь. Спасибо.

Леонид, Канат, я чуть попозже попробую понять Вашу логику. Сейчас просто сил нет
Ratings: 0 negative/0 positive
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
И сколько это строчки потом не перемешивай, они все-равно будут похожи друг на друга. В предложенном мной методе этот недостаток тоже имеется, хотя наверное и в несколько меньшей степени. Подумав на досуге, я придумал еще один способ, который по-видимому даст максимальную рандомизированность результата
m.n=12 && kolichestvo jacheek
m.k=10 && kolichestvo elementov v jachejke
&& togda m.k^m.n - kolichestvo razlichnyh variantov
&& a m.k^(m.n-1) - kolichestvo povtorenij kazhdogo elementa
m.t=25 && trebuemoe kolichestvo povtorenij
local ar1(m.n, m.k) && massiv s vozmozhnymi elementami
for m.i=1 to m.n
for m.j=1 to m.k
ar1(m.i, m.j)=padl(m.i,2,"0")+chr(asc('A')+m.j-1) && naprimer
next
next
rand(-1)
create cursor rn0 (f1 i) && kursor c chislami ot 0 do m.k-1 dlja zapolnenija razrjadov
for m.i=0 to m.k-1
insert into rn0 values (m.i)
next
create cursor tmp2 (f2 C(254)) && kursor, v kotoryj budet sobiratjsja rezuljtat
local ar2(m.n, m.k)
m.cnt=0
do while m.cnt<m.t
for m.i=1 to m.n
select rand(), f1 from rn0 order by 1 into cursor rn1 && chisla iz kursora rn0 peremeshivajutsja
scan
ar2(m.i, recn())=f1
endscan
next
create cursor tmp1 (f2 C(254)) && kursor v kotoryj pomeschaetsja 1 blok rezuljtata
for m.i=1 to m.k
m.f2=""
for m.j=1 to m.n
m.f2=m.f2+","+ar1(m.j, ar2(m.j, m.i)+1)
next
insert into tmp1 values (substr(m.f2,2))
next
&& proverka, net li ranee vstrechavshihsja strochek v novom bloke
select * from tmp1 where sys(2007,tmp1.f2) in (select sys(2007,tmp2.f2) from tmp2) into array ar3
if _tally=0
m.cnt=m.cnt+1
select tmp2
append from dbf("tmp1")
endif
enddo
browse

Идея в принципе та же, что и предыдущем методе, результат строится блоками, в каждом из которых нужное значение встречается ровно 1 раз. Только в первом случае отсутствие одинаковых строк в результате достигалось с помощью определенного алгоритма (что снижало рандомизированность), а здесь здесь достигается грубой проверкой и переделыванием блока в случае необходимости. Этот метод может плохо (медленно) работать, если m.t достаточно большое, но если m.t существенно меньше m.k^(m.n-1), то все будет работать нормально.
Ratings: 0 negative/0 positive
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
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 4 (Гостей: 4)

© 2000-2024 Fox Club 
Яндекс.Метрика