Нужна функция/класс пермутаций

Тема в разделе "PHP", создана пользователем satih, 10 фев 2010.

Статус темы:
Закрыта.
Модераторы: latteo
  1. satih

    satih

    Регистр.:
    19 сен 2008
    Сообщения:
    429
    Симпатии:
    710
    Нужна функция пермутаций, есть скажем 100-200 предметов, нужно из них сделать 30-100к пермутаций, без повторов, _максимально_ разных, т.е. не просто подбором последних предметов, когда первые не меняются.

    Может кто-то знает про готовый класс работы с пермутациями, или другие решения?
     
  2. pk2002

    pk2002

    Регистр.:
    14 ноя 2006
    Сообщения:
    382
    Симпатии:
    350
    Глянь примеры из книги, мож то что нужно http://home.bolink.org/ebooks/webP/pcook/ch04_26.htm
     
    satih нравится это.
  3. satih

    satih

    Регистр.:
    19 сен 2008
    Сообщения:
    429
    Симпатии:
    710
    Вариантов с пермутациями в сети море, но каждый просто предлагает свою реализацию, так чтоб проверенный класс, вроде не нашел. Подумал такую реализацию, может просто сделать 100к пермутаций один раз (пускай не самым эффективным классом), а потом просто перемешивать 100-200 предметов? т.е. предметы в массив, берем базу из 100к пермутаций индексов, перемешиваем предметы в массиве, и при подставлении индекс -> предмет, получаем псевдо-рандомизацию..
     
  4. venetu

    venetu

    Регистр.:
    28 мар 2007
    Сообщения:
    735
    Симпатии:
    261
    В 100 раз проще будет нагенерить рандомом (не все возможные варианты подряд, а сколько-то тысяч полностью случайных) а потом их отфильтровать по "похожести" (прогнать через функцию "каждый-с-каждым", полученный массивчик отсортировать и взять нижнюю часть).
     
  5. Alternator

    Alternator

    Регистр.:
    23 мар 2009
    Сообщения:
    295
    Симпатии:
    145
    PHP:
    $item=array(
    'item1',
    'item2',
    'item3',
    'item4',
    'item5',
    'item6',
    'item7',
    'item8',
    'item9',
    'item0'
    );
    $length=10;//сколько предметов в пермутации
    $count=1000;//соклько пермутаций. указывать не более чем это возможно, иначе поулчится бесконечный цикл
    //желательно даже существенно меньше.
    //максимум factorial(count($item))/factorial(count($item)-$length)
    //для данного случая 3628800

    $permutation=array();
    while(
    count($permutation)!=$count)
        {
        
    $perm=implode(',',array_rand($item,$length));
        if(!isset(
    $permutation[md5($perm)]))
            
    $permutation[md5($perm)]=$perm;//md5 используется для оптимизации при очень длинных пермутациях
        
    }

    foreach(
    $permutation as $key=>$perm)
        {
        
    $perm=explode(',',$perm);
        for(
    $i=0,$s=count($perm);$i<$s;$i++)
            {
            echo 
    $item[$perm[$i]].', ';
            }
        echo 
    '<br>';
        }

    к сожалению на больших количествах пермутаций использование хеш-массива не столь эффективно, и тормзит все больше и больше.
    100к пермутаций из 10-и элементов я просто не дождался
    рекомендую для обеспечения уникальности пермутаций использовать HEAP-таблицу MySQL, либо же sqlite_open(':memory:');
    на задачах требующих работы с большим количеством уникальных данных это будет в порядки быстрее. допилите сами, надеюсь
     
    Belial и satih нравится это.
  6. satih

    satih

    Регистр.:
    19 сен 2008
    Сообщения:
    429
    Симпатии:
    710
    Спасибо за код, особенно за идею с md5.
    Нужно для небольшого скрипта, мускул подключать слишком жирно, скриптик должен работать везде и неосложнять юзера дополнительными требованиями, да и вкладывать в него слишком много нехочу, поэтому думал может есть для такой (скорее всего) популярной задачи готовые решения, все же всем спасибо за помощь.
     
  7. Alternator

    Alternator

    Регистр.:
    23 мар 2009
    Сообщения:
    295
    Симпатии:
    145
    ради интереса оптимизировал для работы без базы:
    100к пермутаций из 100 элементов создаются примерно за 5-7 секунд
    PHP:
    $item=array(
    'item1',
    'item2',
    'item3',
    'item4',
    'item5',
    'item6',
    'item7',
    'item8',
    'item9',
    'item0',
    'item1',
    'item2',
    'item3',
    'item4',
    'item5',
    'item6',
    'item7',
    'item8',
    'item9',
    'item0',
    'item0',
    'item1',
    'item2',
    'item3',
    'item4',
    'item5',
    'item6',
    'item7',
    'item8',
    'item9',
    'item0',
    'item0',
    'item1',
    'item2',
    'item3',
    'item4',
    'item5',
    'item6',
    'item7',
    'item8',
    'item9',
    'item0',
    'item0',
    'item1',
    'item2',
    'item3',
    'item4',
    'item5',
    'item6',
    'item7',
    'item8',
    'item9',
    'item0',
    'item0',
    'item1',
    'item2',
    'item3',
    'item4',
    'item5',
    'item6',
    'item7',
    'item8',
    'item9',
    'item0',
    'item0',
    'item1',
    'item2',
    'item3',
    'item4',
    'item5',
    'item6',
    'item7',
    'item8',
    'item9',
    'item0',
    'item0',
    'item1',
    'item2',
    'item3',
    'item4',
    'item5',
    'item6',
    'item7',
    'item8',
    'item9',
    'item0',
    'item0',
    'item1',
    'item2',
    'item3',
    'item4',
    'item5',
    'item6',
    'item7',
    'item8',
    'item9',
    'item0',
    'item0',
    'item1',
    'item2',
    'item3',
    'item4',
    'item5',
    'item6',
    'item7',
    'item8',
    'item9',
    'item0'
    );
    $length=10;//сколько предметов в пермутации
    $count=100000;//соклько пермутаций. указывать не более чем это возможно, иначе поулчится бесконечный цикл
    //желательно даже существенно меньше.
    //максимум factorial(count($item))/factorial(count($item)-$length)
    //для данного случая 3628800

    $permutation=array();
    do
        {
        for(
    $i=0;$i<$count/10;$i++)
            
    $permutation[]=implode(',',array_rand($item,$length));
        
    array_unique($permutation);
        }
    while(
    count($permutation)<$count);
    /*
    foreach($permutation as $key=>$perm)
        {
        $perm=explode(',',$perm);
        for($i=0,$s=count($perm);$i<$s;$i++)
            {
            echo $item[$perm[$i]].', ';
            }
        echo '<br>';
        }
    */
    PS принимаю благодарность как в устной, так и в денежной форме ;)
     
Статус темы:
Закрыта.