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

[satih]

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

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

 

[pk2002]

Глянь примеры из книги, мож то что нужно

Для просмотра скрытого содержимого вы должны войти или зарегистрироваться.

 

[satih]

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

 

[venetu]

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

 

[Alternator]

$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:');
на задачах требующих работы с большим количеством уникальных данных это будет в порядки быстрее. допилите сами, надеюсь

 

[satih]

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

 

[Alternator]

ради интереса оптимизировал для работы без базы:
100к пермутаций из 100 элементов создаются примерно за 5-7 секунд

$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 принимаю благодарность как в устной, так и в денежной форме