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.

Jakub Vrána, Řešení problému, 25.9.2006, diskuse: 13 (nové: 0)

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ěd

Jirka 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.cz

Diskuse je zrušena z důvodu spamu.

avatar © 2005-2024 Jakub Vrána. Publikované texty můžete přetiskovat pouze se svolením autora. Ukázky kódu smíte používat s uvedením autora a URL tohoto webu bez dalších omezení Creative Commons. Můžeme si tykat. Skripty předpokládají nastavení: magic_quotes_gpc=Off, magic_quotes_runtime=Off, error_reporting=E_ALL & ~E_NOTICE a očekávají předchozí zavolání mysql_set_charset. Skripty by měly být funkční v PHP >= 4.3 a PHP >= 5.0.