Combinatorics: permutations + right to left; product. Like python itertools.

combo.php

<?php

namespace combo;

use InvalidArgumentException;
use OutOfBoundsException;

function py_range($start, $stop = null, $step = null)
{
    if (null === $stop) {
        $stop = $start;
        $start = 0;
    }
    if (null === $step) {
        if ($start > $stop) {
            return [];
        }
        --$stop;

        return range($start, $stop);
    } elseif (-1 === $step) {
        if ($start > $stop) {
            list($start, $stop) = [$stop, $start];
        }
        ++$start;

        return array_reverse(range($start, $stop));
    } else {
        if ($start > $stop) {
            return [];
        }

        return range($start, $stop, $step);
    }
}

/**
 * @param int $n
 *
 * @return int
 */
function factorial($n)
{
    if ($n < 0) {
        throw new OutOfBoundsException('Cannot compute factorial of a negative number.');
    }

    $factorial = 1;
    while ($n > 0) {
        $factorial *= $n;
        $n--;
    }

    return $factorial;
}

/**
 * Return successive r length permutations of elements in the iterable.
 * If r is not specified or is None, then r defaults to the length of the iterable and all possible full-length permutations are generated.
 * Permutations are emitted in lexicographic sort order. So, if the input iterable is sorted, the permutation tuples will be produced in sorted order.
 * Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeat values in each permutation.
 * Example usage,
 * ```php
 * $i = 0;
 * foreach (permutations(range(1, 3), 2) as $combo) {
 *     echo json_encode($combo) . "\n";
 *     ++$i;
 * }
 * echo 'Total count: ' . $i . "\n";
 * ```
 * Outputs,
 * ```
 * [1,2]
 * [1,3]
 * [2,1]
 * [2,3]
 * [3,1]
 * [3,2]
 * Total count: 6
 * ```
 * @link https://docs.python.org/3/library/itertools.html#itertools.permutations itertools.permutations (source)
 *
 * @param array $pool
 * @param null|int $r
 *
 * @return \Generator
 */
function permutations($pool, $r = null)
{
    $n = count($pool);
    $r = (null === $r) ? $n : $r;
    if ($r <= $n) {
        $indices = py_range($n);
        $cycles = py_range($n, $n - $r, -1);
        $ret = [];
        foreach (array_slice($indices, 0, $r) as $i) {
            $ret[] = $pool[$i];
            unset($i);
        }
        yield $ret;
        while ($n) {
            $isDone = true;
            foreach (array_reverse(py_range($r)) as $i) {
                $cycles[$i] -= 1;
                if (0 === $cycles[$i]) {
                    $indices = array_merge(
                        array_slice($indices, 0, $i),
                        array_merge(
                            array_slice($indices, $i + 1),
                            array_slice($indices, $i, 1)
                        )
                    );
                    $cycles[$i] = $n - $i;
                } else {
                    $j = $cycles[$i];
                    // swap array values: $i and $tmpKey
                    $tmpValue = $indices[$i];
                    $tmpKey = count($indices) - $j;
                    $indices[$i] = $indices[$tmpKey];
                    $indices[$tmpKey] = $tmpValue;
                    unset($tmp, $y);
                    $ret = [];
                    foreach (array_slice($indices, 0, $r) as $i0) {
                        $ret[] = $pool[$i0];
                    }
                    yield $ret;
                    $isDone = false;
                    break;
                }
            }
            if ($isDone) {
                break;
            }
        }
    }
}

/**
 * Permutations algorithm.
 * Example usage,
 * ```php
 * $a = [1, 2, 3];
 * do {
 *     echo implode(',', $a) . "\n";
 * } while ($a = nextPermutation($a, 3));
 * ```
 * Outputs:
 * ```
 * 1,2,3
 * 1,3,2
 * 2,1,3
 * 2,3,1
 * 3,1,2
 * 3,2,1
 * ```
 * @link https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9D%D0%B0%D1%80%D0%B0%D0%B9%D0%B0%D0%BD%D1%8B#.D0.92.D0.B0.D1.80.D0.B8.D0.B0.D0.BD.D1.82_.E2.84.96.C2.A01 Реализации алгоритмов/Алгоритм Нарайаны
 * @link https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9D%D0%B0%D1%80%D0%B0%D0%B9%D0%B0%D0%BD%D1%8B Алгоритм Нарайаны (Wiki)
 *
 * @param array $sequence
 * @param int $count
 *
 * @return bool|mixed
 */
function nextPermutation($sequence, $count)
{
    $out = array_keys($sequence);
    $res = $sequence;
    // step #1
    $k = $count - 2;
    while ($k >= 0 && $out[$k] >= $out[$k + 1]) {
        --$k;
    }
    if (-1 == $k) {
        return false; // end
    }
    // step #2
    $t = $count - 1;
    while ($t >= 0 && $t >= $k + 1 && $out[$k] >= $out[$t]) {
        --$t;
    }
    $tmp = $out[$k];
    $out[$k] = $out[$t];
    $out[$t] = $tmp;
    // step #3
    for ($i = $k + 1; $i < ceil(($count + $k) / 2); ++$i) {
        $t = $count + $k - $i;
        $tmp = $out[$i];
        $out[$i] = $out[$t];
        $out[$t] = $tmp;
    }

    $res = [];
    foreach ($out as $v) {
        $res[$v] = $sequence[$v];
    }

    return $res;
}

/**
 * Permutations algorithm right to left.
 *
 * Example usage,
 *
 * ```php
 * foreach(permutationsRightToLeftGenerator([1, 2, 3]) as $a) {
 *     echo implode(',', $a) . "\n";
 * }
 * ```
 *
 * Outputs:
 *
 * ```
 * 2,3,1
 * 3,1,2
 * 1,3,2
 * 2,1,3
 * 1,2,3
 * ```
 *
 * @link https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9D%D0%B0%D1%80%D0%B0%D0%B9%D0%B0%D0%BD%D1%8B#.D0.92.D0.B0.D1.80.D0.B8.D0.B0.D0.BD.D1.82_.E2.84.96.C2.A02 Реализации алгоритмов/Алгоритм Нарайаны
 * @link https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9D%D0%B0%D1%80%D0%B0%D0%B9%D0%B0%D0%BD%D1%8B Алгоритм Нарайаны (Wiki)
 *
 * @param array $sequence
 *
 * @return \Generator
 */
function permutationsRightToLeftGenerator($sequence)
{
    $b = $sequence;
    $a = array_reverse($b);
    while ($a !== $b) {
        $i = 0;

        while ($a[$i] > $a[$i - 1]) {
            $i++;
        }
        $j = 0;
        while ($a[$j] < $a[$i]) {
            ++$j;
        }

        $c = $a[$j];
        $a[$j] = $a[$i];
        $a[$i] = $c;

        $x = array_reverse(array_slice($a, 0, $i));
        $y = array_slice($a, $i);

        $a = array_merge($x, $y);

        $out = $a;

        yield $out;
    }
}

/**
 * Example usage,
 *
 * ```php
 * foreach(permutationsGenerator([1, 2, 3], 3) as $a) {
 *     echo implode(',', $a) . "\n";
 * }
 * ```
 *
 * Outputs:
 *
 * ```
 * 1,2,3
 * 1,3,2
 * 2,1,3
 * 2,3,1
 * 3,1,2
 * 3,2,1
 * ```
 *
 * @param array $sequence
 * @param int $count
 *
 * @return \Generator
 */
function permutationsGenerator($sequence, $count)
{
    $out = $sequence;

    do {
        $message = (yield $out);

        while ('rewind' === $message) {
            $out = $sequence;
            $message = (yield $out);
        }

    } while ($out = nextPermutation($out, $count));
}

interface PermutationsInterface
{
    /**
     * @return int
     */
    public function length();

    /**
     * @return \Generator
     */
    public function iterator();
}

class Permutations implements PermutationsInterface
{
    protected $sequence;
    protected $count;

    public function __construct($sequence, $count = null)
    {
        $this->sequence = $sequence;
        $this->count = $count;
    }

    /**
     * @return int
     */
    protected function getCount()
    {
        return (null === $this->count) ? count($this->sequence) : $this->count;
    }

    /**
     * @return int
     */
    public function length()
    {
        $n = count($this->sequence);
        $r = $this->getCount();

        // The number of items returned is n! / (n-r)! when 0 <= r <= n or zero when r > n.

        if ($r > $n) {
            return 0;
        }

        return factorial($n) / factorial($n - $r);
    }

    /**
     * @return \Generator
     */
    public function iterator()
    {
        $count = $this->getCount();

        if (count($this->sequence) === $count) {
            return permutationsGenerator($this->sequence, $count);
        }

        return permutations($this->sequence, $count);
    }

    /**
     * @return \Generator
     */
    public function iteratorRightToLeft()
    {
        return permutationsRightToLeftGenerator($this->sequence);
    }
}

class ProductGenerator implements PermutationsInterface
{
    /**
     * @var PermutationsInterface[]
     */
    protected $lists;

    /**
     * ProductGenerator constructor.
     *
     * Example usage,
     *
     * ```php
     * $productGenerator = new \combo\ProductGenerator([['a', 'b'], [1, 2], ['c']]);
     * echo 'Count calculated: ' . $productGenerator->getCombinationsCount() . "\n";
     * $i = 0;
     * foreach ($productGenerator->getGenerator() as $combo) {
     *     echo json_encode($combo) . "\n";
     *     ++$i;
     * }
     * echo 'Count real: ' . $i . "\n";
     * ```
     *
     * Outputs:
     *
     * ```
     * Count calculated: 4
     * [["a","b"],[1,2],["c"]]
     * [["b","a"],[1,2],["c"]]
     * [["a","b"],[2,1],["c"]]
     * [["b","a"],[2,1],["c"]]
     * Count real: 4
     * ```
     *
     * @param $lists
     */
    public function __construct($lists)
    {
        foreach ($lists as &$list) {
            if (is_scalar($list)) {
                $list = new Permutations([$list]);
            } elseif (is_array($list)) {
                $list = new Permutations($list);
            } elseif (!($list instanceof PermutationsInterface)) {
                throw new InvalidArgumentException('Bad list item type. Must be instance of [[Permutations]]');
            }
            unset($list);
        }

        $this->lists = $lists;
    }

    /**
     * @return int
     */
    public function length()
    {
        if (0 === count($this->lists)) {
            return 0;
        }
        
        $count = 1;

        foreach ($this->lists as $list) {
            $count *= $list->length();
        }

        return $count;
    }

    /**
     * @return \Generator
     */
    public function iterator()
    {
        $lists = $this->lists;

        $countLists = count($lists);

        if (0 !== $countLists) {

            /** @var static $lastGenerator */
            $lastGenerator = end($lists);

            if (1 === count($lists)) {
                foreach ($lastGenerator->iterator() as $lastCombo) {
                    yield [$lastCombo];
                }
            } else {
                foreach ($lastGenerator->iterator() as $lastCombo) {
                    $innerLists = array_slice($lists, 0, -1);
                    $inerGenerator = new static($innerLists);
                    foreach ($inerGenerator->iterator() as $list) {
                        yield array_merge($list, [$lastCombo]);
                        unset($list);
                    }
                }
            }
        }
    }
}