Autor Zpráva
jeremyXX
Profil *
Ahoj všem,

nenašel by se prosím někdo, kdo by dokázal přepsat zdrojový kód z Javascriptu do PHP?
Jedná se mi o tento kód:
jsfiddle.net/dkp41eL3/8

Dělá mi tam problém JS funkce concat a slice

Děkuji předem
Kcko
Profil
Od toho je tady jiná sekce
CZechBoY
Profil
<?php
function k_combinations(array $set, $k)
{
    if ($k > count($set) || $k <= 0) {
        return [];
    }

    if ($k == count($set)) {
        return [$set];
    }

    if ($k == 1) {
        $combs = [];
        for ($i = 0; $i < count($set); $i++) {
            $combs[] = [$set[$i]];
        }

        return $combs;
    }

    // assert ('1 < $k'); assert('$k < count($set)');

    $combs = [];
    for ($i = 0; $i < count($set) - $k + 1; $i++) {
        $head = array_slice($set, $i, $i + 1);
        $tailcombs = k_combinations(array_slice($set, $i + 1), $k - 1);
        for ($j = 0; $j < count($tailcombs); $j++) {
            $combs[] = array_merge($head, $tailcombs[$j]);
        }
    }

    return $combs;
}

$results = k_combinations(["1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", "26", "27", "28", "29", "30"], 3);

$str = "";
for ($i = 0; $i < count($results); $i++) {
    $str .= "{P:" . implode(',', $results[$i]) . "},";
}

echo $str;
Alphard
Profil
CZechBoY [#3]:
Až na to, že to nefunguje... V PHP u funkce array_slice značí třetí parametr délku výběru, nikoliv poslední prvek. Na 25. řádek je lepší dát $head = [$set[$i]];.

Ovšem, toto je nádherná ukázka na trochu použití generátorů. Pokud není potřeba držet to pole v paměti celé, lze tím ušetřit značné prostředky. Původní verze vyžaduje memory: 440.29872131348 MiB, 5.7s.

Pokud kód mírně upravím...
Pokud jen nahradím return za yield, bude vše špatně. Je vhodnější použít úplně jiný algoritmus, viz [#8] Alphard.
CZechBoY
Profil
Alphard:
Hm, asi jsem nezkontroloval celej vystup.

Chtel to jen prepsat, ne optimalizovat :-)...
jeremyXX
Profil *
Dobré ráno všem,

předem se omlouvám za špatné umístění příspěvku.

Děkuji všem za Vaše odpovědi.
CZechBoY - přepsal jsem to úplně stejně, ale narazil jsem na stejný problém a to že fce mezi JS a PHP pracují odlišně
Alphard - zkoušel jsem Váš kód, ale bohužel nefunguje, stále mě to hlásí, že první argument fce array_merge není pole

Mohl by jste se na to ještě prosím podívat, potřeboval bych a by PHP kód se choval výsledkem úplně stejně jako v JS

ještě jednou děkuji za ochotu
jeremyXX
Profil *
Ještě jednou dobrý den,

vypadá to že jsem to již snad poskládal
zde je výsledný kód:
<?php
 $input = array(1, 2, 3,4, 5, 6);
 $count = 3;

function k_combinations(array $set, $k){
    if ($k > count($set) || $k <= 0) {
        return [];
    }
 
    if ($k == count($set)) {
        return [$set];
    }
 
    if ($k == 1) {
        $combs = [];
        for ($i = 0; $i < count($set); $i++) {
            $combs[] = [$set[$i]];
        }
        return $combs;
    }
 
    $combs = [];
    for ($i = 0; $i < count($set) - $k + 1; $i++) {
        $head = [$set[$i]];
        $tailcombs = k_combinations(array_slice($set, $i + 1), $k - 1);
        for ($j = 0; $j < count($tailcombs); $j++) {
            $combs[] = array_merge($head, $tailcombs[$j]);
        }
    } 
    return $combs;
}

function k_combinations2(array $set, $k){
    if ($k > count($set) || $k <= 0) {
        yield [];
    }
 
    if ($k == count($set)) {
        yield [$set];
    }
 
    if ($k == 1) {
        foreach ($set as $v) {
            yield [$v];
        }
    }
 
    for ($i = 0; $i < count($set) - $k + 1; $i++) {
        $head = [$set[$i]];
        foreach (k_combinations(array_slice($set, $i + 1), $k - 1) as $item) {
            yield array_merge($head, $item);
        }
    }
}

 
$results = k_combinations2($input, $count);
foreach($results as $item){
    echo "{P:" . implode(',', $item) . "},";
}
?>

všem děkuji za pomoc
Alphard
Profil
K tomuto vláknu je třeba se vrátit, omlouvám se, že až po týdnu, dříve jsem to nestihl. Uvést myšlenku s yield byl sice dobrý nápad, avšak v tom kódu [#4] Alphard je všechno špatně :-(. Triviální úprava není možná, ten algoritmus se na použití s yield nehodí, kvůli skokům, práci se zásobníky, počítání počtu položek...

Teoreticky je výpočet kombinací rozebraný např. zde, prakticky se mi potom zdá velmi dobrá implementace v Pythonu v itertools.combinations. Tu jsem si také vypůjčil a přepsal (snad správně) do PHP:

function combinationsIndices($n, $r) {
    if ($r > $n) {
        return ;
    }
    $indices = range(0, $r - 1);
    yield $indices;
    while (true) {
        for ($i = $r - 1; $i >= -1; $i--) {
            if ($i == -1) {
                return ;
            }
            if ($indices[$i] != $i + $n - $r) {
                break;
            }
        }
        $indices[$i] += 1;
        for ($j = $i + 1; $j < $r; $j++) {
            $indices[$j] = $indices[$j-1] + 1;
        }
        yield $indices;
    }
}

function combinations($set, $r) {
    foreach (combinationsIndices(count($set), $r) as $item) {
        $arr = [];
        foreach ($item as $key) {
            $arr[] = $set[$key];
        }
        yield $arr;
    }
}

$gen = combinations(range(0, 5), 3);
foreach ($gen as $item) {
    echo implode(',', $item), PHP_EOL;
}

Není třeba držet žádné velké zásobníky, není zde rekurze, jen se postupně posouvají indexy, pomocí kterých se sestavuje výsledné pole.

Vaše odpověď

Mohlo by se hodit


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: