Permutace
Školení, která pořádám 
Občas (např. při luštění šifer) potřebuji pracovat s permutacemi. K tomu lze přistoupit dvěma způsoby – buď si pokaždé napsat funkci, která bude s permutací přímo pracovat tak, jak je potřeba, nebo napsat funkci, která vygeneruje všechny permutace, se kterými budeme pracovat až mimo ni. Druhý způsob je jistě univerzálnější:
<?php /** Vygenerování permutací * @param array pole z prvky, ze kterých se má permutace vytvořit, např. range(1, 2) * @return array pole všech permutací, např. array(array(1, 2), array(2, 1)) * @copyright Jakub Vrána, https://php.vrana.cz/ */ function permutace($prvky) { if (count($prvky) == 1) { return array($prvky); } $return = array(); foreach ($prvky as $prvek) { foreach (permutace(array_diff($prvky, array($prvek))) as $zbytek) { $return[] = array_merge(array($prvek), $zbytek); } } return $return; } // použití foreach (permutace(range(1, 3)) as $permutace) { echo implode(", ", $permutace) . "\n"; } ?>
Pro vyřazení prvku z pole se používá funkce array_diff, která prvek musí v poli znovu vyhledat. Rychlejší by nejspíš bylo použít funkci array_splice, která prvek vyjme přímo podle jeho pozice, ale bylo by s tím o něco víc práce.
Diskuse
pif:
moc hezký algoritmus, ale kdybych uvažoval, kde permutace použít v php ;DDD napadlo by mě pravé nefalšované nic. K pozastavení už je jen to, žes to někdy potřeboval.
Qels:
šlo by to přepsat do Céčka?Vladimír:
Tak samozřejmě že by šlo, přepisoval jsem to do C#, tak aby každý vstupní parametr byl jakoby unikátní a nebyl to celkem problém.Já využití našel při parametrickém vyhledávání krabic, kdy když zadáš roměry x, y, z, tak je ti jedno kterým třem rozměrům a v jakém pořadí to odpovídá, ale nesmí se stát, že to vyhledá krabici o rozměrech x, x, z.
Moc díky za inspiraci.
Kdyby někdo měl zájem, tak klidně nasdílím (vavrik.vladimir, gmail.com)
pif:
tedy kromě těch sterilních soutěží...
Juro Hajdúch:
Kombinatorika je zaujímavá, ale ma napadá (zatiaľ) len jedno použitie - lámanie hesla :-(. Inak dobrá funkcia. Večer sa idem hrať.jux:
johooo, uz nekoho vidim, jak pomoci jednoho z nejpomalejsich skriptovacich jazyku na svete lusti hesla:))josef:
Mám jednu prosbu, potřeboval bych vědět jednu věc ze života. Byl jsem v restauraci se dvěma kamarádama a číšník měl 9 druhů různých nápojů, od sladkých až po ty nejtvrdší. Tyto nápoje nám poprvé rozlil tak, že každý jsme měli ve sklenici tři druhy nápojů. Dohromad tedy devět. Otázka zní, kolikrát musí číšník nalét všech devět nápojů do skleniček, po třech nápojích do skleničky, aby všichni tři hosté měli dohromady jinou skladbu nápoje ve skleničkách. Je jedno jestli ve skleničce bude nápoj nahoře, uprostřed nebo dole( např. alžírská káva vaječný koňak- káva- mléko nebo šlehačka. Obsah sklenice se může i zamýchat. nevím jak to vypočítat domnívám se že se jedná o permutace. Dík za odpovědJirka Chmiel:
Díky moc. Jen bych upozornil na případ, kdy se budou ve vstupním poli prvky opakovat. Např.: pro array(1,2,2) funkce vrátí array(array(1,2),array(2,1)). Jinak super dík.Jirka Chmiel:
Tak ne. vrátí to dokonce array(array(2,1),array(2,1)), hmm...visitor:
Nyní jsem narazil na to samé a divil jsem se, že to nefunguje. Bude to třebapřepsat na ten array_splice().visitor:
Tak vyřešil jsem to takto:<?php
function permutace($prvky) {
if (count($prvky) == 1) {
return array($prvky);
}
$return = array();
foreach ($prvky as $key => $prvek) {
foreach (permutace(deleteItem($prvky, $key)) as $zbytek) {
$return[] = array_merge(array($prvek), $zbytek);
}
}
return $return;
}
function deleteItem($arr, $pos) {
unset($arr[$pos]);
return $arr;
}
?>
Radim Kleinpeter:
Tak já tu jsem s dost reálným příkladem použití této permutace... na což nestačí ani tento příklad.Mám filtr čehosi, dejme tomu katalog mobilů.
Pro sitemap potřebuji vygenerovat kompletní seznam všech variant / kombinací / permutací, které si člověk může naklikat.
Tedy např. všechny značky a u všech značek všechny ceny, všechny typy mobilů, ale také typy mobilů bez uvedení ceny, atd atd...
Typ, resp. filtrů mám asi 5, položek v nich v řádu jednotek až desítek.
sett:
Ahoj,poradí mě někdo program nebo jak zjistím kombinace z písmem a b c d e když chci jen 3 ve skupině jejich všechny kombinace ....můžou se i opakovat....díky sett@post.czDiskuse je zrušena z důvodu spamu.
© 2005-2024 