За последние 24 часа нас посетили 45209 программистов и 1811 роботов. Сейчас ищут 754 программиста ...

Скрипт комбинаций лотереи "6 из 36"

Тема в разделе "PHP для новичков", создана пользователем xmav, 22 июл 2014.

  1. xmav

    xmav Активный пользователь

    С нами с:
    20 фев 2013
    Сообщения:
    10
    Симпатии:
    0
    Доброе время суток всем! Пытаюсь написать вывод всех комбинаций лотереи 6 из 36. Причем планирую не выводить в общий список те комбинации, которые повторяются в 4 цифрах с предыдущими. На этом и завис (

    Пишу в базу данных (пока поставил коммент записи в базу - ибо долго в базу пишет) все комбинации с повторами (для теста беру не 6 из 36, а 6 из 18):

    Код (Text):
    1.  
    2. set_time_limit(1200);
    3. $start=1;
    4. $finish=18;
    5. for ($x1=$start; $x1<$finish+1; $x1++)
    6.     {
    7.     $d1=$x1;
    8.     for ($x2=$x1; $x2<$finish+1; $x2++)
    9.         {
    10.         $d2=$x2;
    11.         if ($d2>$d1)
    12.             {
    13.             for ($x3=$x2; $x3<$finish+1; $x3++)
    14.                 {  
    15.                     $d3=$x3;
    16.                     if ($d3>$d2)
    17.                         {
    18.                         for ($x4=$x3; $x4<$finish+1; $x4++)
    19.                             {
    20.                                 $d4=$x4;
    21.                                 if ($d4>$d3)
    22.                                     {
    23.                                         for ($x5=$x4; $x5<$finish+1; $x5++)
    24.                                             {
    25.                                             $d5=$x5;
    26.                                             if ($d5>$d4)
    27.                                                 {
    28.                                                     for ($x6=$x5; $x6<$finish+1; $x6++)
    29.                                                         {
    30.                                                         $d6=$x6;
    31.                                                         if ($d6>$d5)
    32.                                                             {
    33.                                                                 $sql = "INSERT INTO `loto` (`d1`,`d2`,`d3`,`d4`,`d5`,`d6`) VALUES ('$d1','$d2','$d3','$d4','$d5','$d6')";
    34.                                                                 echo $d1." ".$d2." ".$d3." ".$d4." ".$d5." ".$d6."<br>";
    35.                                                                 //mysql_query($sql);
    36.                                                             }
    37.                                                         }
    38.                                                 }
    39.                                             }
    40.                                     }
    41.                             }
    42.                         }
    43.                 }
    44.             }
    45.         }
    46.     }
    Подскажите, пожалуйста, уважаемые, как теперь можно из этой базы удалить дубликаты?
    Например, одна из строчек 1,2,3,4,5,6 и 1,3,4,5,7,8 является лишней, т.к. у них идет повтор 1,3,4,5

    Заранее благодарю за критику / предложения! Всем хорошего дня!
     
  2. Хыиуду

    Хыиуду Активный пользователь

    С нами с:
    3 июн 2014
    Сообщения:
    618
    Симпатии:
    5
    if (count(array_intersect(array(1,2,3,4,5,6), array(1,3,4,5,7,8)))>=4) // удалить из базы второй массив
     
  3. xmav

    xmav Активный пользователь

    С нами с:
    20 фев 2013
    Сообщения:
    10
    Симпатии:
    0
    Код (Text):
    1. if (count(array_intersect(array(1,2,3,4,5,6), array(1,3,4,5,7,8)))>=4) // удалить из базы второй массив
    если я правильно понимаю данный код удалит только комбинацию 1,3,4,5,7,8 ?
    если да, то как быть с оставшейся кучей одинаковостей?
     
  4. Хыиуду

    Хыиуду Активный пользователь

    С нами с:
    3 июн 2014
    Сообщения:
    618
    Симпатии:
    5
    Циклом пройтись по оставшейся куче одинаковости и сделать то же самое.
     
  5. xmav

    xmav Активный пользователь

    С нами с:
    20 фев 2013
    Сообщения:
    10
    Симпатии:
    0
    Хыиуду, а как циклом выбрать такие одинаковости?
    как средствами PHP найти-то эти одинаковости?
     
  6. Хыиуду

    Хыиуду Активный пользователь

    С нами с:
    3 июн 2014
    Сообщения:
    618
    Симпатии:
    5
    Ну, во-первых, полный цикл у вас - это 1.4 миллиарда запросов. Крайне плохой фэн-шуй.
    Во-вторых, поищите точки оптимизации ваших циклов. Понятное дело, что если первым вы взяли комбинацию 1, 2, 3, 4, 5, 6, то дальше можно все смело пропускать как минимум до 1, 2, 3, 7, 8, 9, потому что все предыдущие заведомо не подходят. После этого следующий прыжок будет уже в сторону 1, 2, 3, 10, 11, 12. Намек понятен?
     
  7. xmav

    xmav Активный пользователь

    С нами с:
    20 фев 2013
    Сообщения:
    10
    Симпатии:
    0
    Согласен. Если есть какие-то предложения - готов выслушать, чтобы уменьшить эти запросы.

    Я уже делал так. Просто думал что проще будет создать ВСЕ-ПРИВСЕ возможные комбинации и потом удалять уже одинаковости. Неправильно размышляю?
     
  8. Хыиуду

    Хыиуду Активный пользователь

    С нами с:
    3 июн 2014
    Сообщения:
    618
    Симпатии:
    5
    Еще раз. 1.4 миллиарда - это МНОГО. Это как минимум 10 гигабайт таблица, и скрипт ваш будет отрабатывать полторы недели (если считать время одного запроса за 1 мс и отбросить все накладные расходы). Это к вопросу о "создать все".
    Далее. Можно оптимизировать сами циклы:
    Код (Text):
    1. for ($x1=$start; $x1<$finish+1; $x1++)
    2.    {
    3.    $d1=$x1;
    4.    for ($x2=$x1; $x2<$finish+1; $x2++)      {
    5.       $d2=$x2;
    6.       if ($d2>$d1)
    7.          { for ($x3=$x2; $x3<$finish+1; $x3++) ...
    тут я вижу аж три замечания.
    Во-первых, зачем вам дополнительные переменные и еще эта проверка на больше-меньше? Можно же сразу начинать от x+1.
    Во-вторых, $x<$finish+1 - гораздо лучше и понятнее писать $x<=$finish.
    Наконец, в-третьих, если при вашем переборе должно выполняться условие $x1<$x2<...<$x6, тогда циклы надо гонять не до $finish, а до $finish-$n, где $n - уровень внешнего цикла по отношению к самому глубокому.
    То есть все ваши вложенные циклы гораздо проще, быстрее и нагляднее будут работать в следующем виде:
    Код (PHP):
    1. for ($x1 = $start; $x1 <= $finish-5; $x1++)
    2. for ($x2 = $x1+1; $x2 <= $finish-4; $x2++)
    3. for ($x3 = $x2+1; $x2 <= $finish-3; $x3++)
    4. for ($x4 = $x3+1; $x2 <= $finish-2; $x4++)
    5. for ($x5 = $x4+1; $x2 <= $finish-1; $x5++)
    6. for ($x6 = $x5+1; $x2 <= $finish; $x6++) {...}
    7.  
    Ради интереса можете посчитать, сколько операций это сэкономит.
    Но, как я уже писал, полный перебор в любом случае будет неэффективен. Ищите, как можно оптимизировать, я постом выше уже привел пример
     
  9. xmav

    xmav Активный пользователь

    С нами с:
    20 фев 2013
    Сообщения:
    10
    Симпатии:
    0
    Хыиуду, благодарен вам подсказки! Соглашусь с вами, что создавать полностью весь перебор не правильно.

    Покажу первую версию кода, который перебирает цифры и дает минимальное кол-во одинаковостей вида 1,2,3,4,5,6 и 1,2,3,4,5,7 (тут аж 5 цифр совпадает):

    Код (Text):
    1.  
    2. for ($x1=$start; $x1<$finish+1; $x1++)
    3.         for ($x2=$start; $x2<$finish-3; $x2++)
    4.             {
    5.                 if ($x1<$x2)
    6.                     {
    7.                         for ($x3=$x2+1; $x3<$finish; $x3=$x3+4)
    8.                             {
    9.                                 $x4=$x3+1;
    10.                                 $x5=$x3+2;
    11.                                 $x6=$x3+3;
    12.                                
    13.                                 if (
    14.                                 ($x3<$finish) AND ($x4<$finish) AND ($x5<$finish) AND (($x6<$finish) OR ($x6=$finish))
    15.                                 AND
    16.                                 (($d3<>$x2) AND ($d4<>$x2) AND ($d5<>$x2) AND ($d6<>$x2))
    17.                                 )
    18.                                     {
    19.                                         echo $x1." ".$x2." ".$x3." ".$x4." ".$x5." ".$x6."<br>";
    20.                                         // $sql = "INSERT INTO `loto` (`d1`,`d2`,`d3`,`d4`,`d5`,`d6`) VALUES ('$x1','$x2','$x3','$x4','$x5','$x6')";
    21.                                         // mysql_query($sql);
    22.                                     }
    23.                             }
    24.                     }
    25.             }
    вот несколько первых строчек, которые выводит данный скрипт:

    1 2 3 4 5 6 -> одинаковость #1 (одинаковы цифры 1,3,4,5,6)
    1 2 7 8 9 10
    1 2 11 12 13 14
    1 2 15 16 17 18
    1 3 4 5 6 7 -> одинаковость #1 (одинаковы цифры 1,3,4,5,6)
    1 3 8 9 10 11
    1 3 12 13 14 15
    1 4 5 6 7 8
    1 4 9 10 11 12
    1 4 13 14 15 16
    1 5 6 7 8 9
    1 5 10 11 12 13
    1 5 14 15 16 17

    Как с помощью PHP выловить эти самые одинаковости?
    Стояли бы они каждый на своем месте - было бы проще наверное их выловить.
    А тут они на разных местах стоят (
     
  10. Хыиуду

    Хыиуду Активный пользователь

    С нами с:
    3 июн 2014
    Сообщения:
    618
    Симпатии:
    5
    Я же уже писал, count(array_intersect($array1, $array2)) - подсчитывает, сколько в этих двух массивах совпадающих чисел.
     
  11. xmav

    xmav Активный пользователь

    С нами с:
    20 фев 2013
    Сообщения:
    10
    Симпатии:
    0
    Хыиуду, благодарен вам за терпение

    Попробовал пооптимизировать обработку сравнения сгенерированных комбинаций и вот что получилось:
    Код (Text):
    1.  
    2.     set_time_limit(0);
    3.     $step=4; // максимальное кол-во одинаковостей для комбинаций
    4.    
    5.     // записываем 1,2,3,4,5,6 в массив, чтобы было с чем сравнивать
    6.     $array0[0][0]=1;
    7.     $array0[0][1]=2;
    8.     $array0[0][2]=3;
    9.     $array0[0][3]=4;
    10.     $array0[0][4]=5;
    11.     $array0[0][5]=6;
    12.    
    13.     for ($x1 = $start; $x1 <= $finish-5; $x1++)
    14.         for ($x2 = $x1+1; $x2 <= $finish-4; $x2++)
    15.             for ($x3 = $x2+1; $x3 <= $finish-3; $x3++)
    16.                 for ($x4 = $x3+1; $x4 <= $finish-2; $x4++)
    17.                     for ($x5 = $x4+1; $x5 <= $finish-1; $x5++)
    18.                         for ($x6 = $x5+1; $x6 <= $finish; $x6++)
    19.                             {
    20.                            
    21.                                 $count++;                               // количество перебранных комбинаций
    22.                                 $array1=array($x1,$x2,$x3,$x4,$x5,$x6); // массив свежегенерированной комбинации
    23.                                
    24.                                 for ($i=0; $i<count($array0); $i++)     // пробегаем в цикле весь массив, чтобы узнать нет ли одинаковостей
    25.                                     {
    26.                                         $balls=count(array_intersect($array1, array($array0[$i][0],$array0[$i][1],$array0[$i][2],$array0[$i][3],$array0[$i][4],$array0[$i][5])));
    27.                                         if ($balls>=$step) {break 2;}
    28.                                     }
    29.                                    
    30.                                 if ($balls<$step)
    31.                                     {
    32.                                         $count_array++; // переменная используемая для указания индекса строки при записи в массив
    33.                                         $array0[$count_array][0]=$x1;
    34.                                         $array0[$count_array][1]=$x2;
    35.                                         $array0[$count_array][2]=$x3;
    36.                                         $array0[$count_array][3]=$x4;
    37.                                         $array0[$count_array][4]=$x5;
    38.                                         $array0[$count_array][5]=$x6;
    39.                                     }
    40.                                    
    41.                             }
    Но всё равно сравнение больших значений $finish не происходит, серверу не хватает кубатуры для обработки большого объема информации.

    Уважаемые подскажите, пожалуйста, что еще можно подправить в вышеуказанном коде, чтобы скрипт работал побыстрее.
    Заранее всех благодарю!
     
  12. Хыиуду

    Хыиуду Активный пользователь

    С нами с:
    3 июн 2014
    Сообщения:
    618
    Симпатии:
    5
    Код (Text):
    1.    $array0[0][0]=1;
    2.    $array0[0][1]=2;
    3.    $array0[0][2]=3;
    4.    $array0[0][3]=4;
    5.    $array0[0][4]=5;
    6.    $array0[0][5]=6;
    Это пишется проще: $array0[0] = range(0,5);
    for ($i=0; $i<count($array0); $i++) - вынесите count($array0) за массив. Например
    Код (Text):
    1. $cnt = count($array[0]);
    2. for ($i=0; $i<$cnt; $i++)
    Далее
    Код (Text):
    1. $balls=count(array_intersect($array1, array($array0[$i][0],$array0[$i][1],$array0[$i][2],$array0[$i][3],$array0[$i][4],$array0[$i][5])));
    Обнять и плакать, зачем так сложно?
    Код (Text):
    1. $balls=count(array_intersect($array1, $array0[$i]));
    Код (Text):
    1.                         if ($balls<$step)
    2.                            {
    3.                               $count_array++; // переменная используемая для указания индекса строки при записи в массив
    4.                               $array0[$count_array][0]=$x1;
    5.                               $array0[$count_array][1]=$x2;
    6.                               $array0[$count_array][2]=$x3;
    7.                               $array0[$count_array][3]=$x4;
    8.                               $array0[$count_array][4]=$x5;
    9.                               $array0[$count_array][5]=$x6;
    10.                            }
    - по-моему, избыточная проверка, раз уж сюда добрались, она в любом случае true. А следовательно, вся эта простыня заменяется на
    Код (Text):
    1. $array0[]=$array1;
    И не нужен никакой $count_array;
    Ну, и последнее: если у вас нижний лимит - 4 совпадения, то вы уверены, что нужен break 2, а не break $balls-$step+1? Это я так, без проверки, чисто умозрительно.
     
  13. xmav

    xmav Активный пользователь

    С нами с:
    20 фев 2013
    Сообщения:
    10
    Симпатии:
    0
    Спасибо за подсказку

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

    Код (Text):
    1. $balls=count(array_intersect($array1, $array0[$i]));
    Да, действительно проще запись. Спасибо.

    Для значения $balls=3 мы пишем свежегенерированную комбинацию пишем в массив + если у нас $step=4,
    то break 3-4+1 ---> будет break 0; такое разве бывает?
    Сделал break 3; - еще быстрее забегало - правильно я понимаю, что с помощью break 3; мы переходим в цикл генерации последней шестой цифры?

    Но всё равно слабовато ... еще бы ускорить бы ...
    Думаю может применить ход с расчетом кол-во совпадений $balls?
    Например, если $balls==6, то при $step=4 делать break к генерации числа x4?
    $balls==5 + $step=4 = break to x5?
    $balls==4 + $step=4 = break to x6? (что сейчас и делается)
    Есть ли в этих размышлениях здравый смысл?

    что-то готовы код, только для разных $balls не понимаю какой поставить break
    Код (Text):
    1. if ($balls==$step+2) {break 3;}
    2. if ($balls==$step+1) {break 3;}
    3. if ($balls==$step)   {break 3;}
    Ставлю 5,4,3 - что-то цифры все разъезжаются сразу

    Текущий код:
    Код (Text):
    1.  
    2.     $step=4;
    3.     $array0[0] = range(1,6);
    4.    
    5.     for ($x1 = $start; $x1 <= $finish-5; $x1++)
    6.         for ($x2 = $x1+1; $x2 <= $finish-4; $x2++)
    7.             for ($x3 = $x2+1; $x3 <= $finish-3; $x3++)
    8.                 for ($x4 = $x3+1; $x4 <= $finish-2; $x4++)
    9.                     for ($x5 = $x4+1; $x5 <= $finish-1; $x5++)
    10.                         for ($x6 = $x5+1; $x6 <= $finish; $x6++)
    11.                             {
    12.                                 $count++;
    13.                                 $array1=array($x1,$x2,$x3,$x4,$x5,$x6);
    14.                                 $cnt = count($array0);
    15.                                 for ($i=0; $i<$cnt; $i++)
    16.                                     {
    17.                                         // if (count(array_intersect($array1, $array0[$i]))>=$step) {break 3;}
    18.                                         $balls=count(array_intersect($array1, $array0[$i]));
    19.                                         if ($balls==$step+2) {break 3;}
    20.                                         if ($balls==$step+1) {break 3;}
    21.                                         if ($balls==$step)   {break 3;}
    22.                                     }
    23.                                 $array0[]=$array1;
    24.                             }
     
  14. Хыиуду

    Хыиуду Активный пользователь

    С нами с:
    3 июн 2014
    Сообщения:
    618
    Симпатии:
    5
    В этом случае просто не выполнится условие if ($balls >= $step)
     
  15. xmav

    xmav Активный пользователь

    С нами с:
    20 фев 2013
    Сообщения:
    10
    Симпатии:
    0
    Хыиуду, а по этой оптимизации нет никаких у вас идей?

    Но всё равно слабовато ... еще бы ускорить бы ...
    Думаю может применить ход с расчетом кол-во совпадений $balls?
    Например, если $balls==6, то при $step=4 делать break к генерации числа x4?
    $balls==5 + $step=4 = break to x5?
    $balls==4 + $step=4 = break to x6? (что сейчас и делается)
    Есть ли в этих размышлениях здравый смысл?

    Для разных $balls не понимаю какой поставить break

    Код (Text):
    1.     if ($balls==$step+2) {break 3;}
    2.     if ($balls==$step+1) {break 3;}
    3.     if ($balls==$step)   {break 3;}
    Ставлю 5,4,3 - что-то цифры все разъезжаются сразу