PHP Permutation Iterator

permutation_iterator.php

<?php

class PermutationIterator implements Iterator
{
    /** @var array */
    protected $items;

    /** @var int */
    protected $slots;

    /** @var array */
    protected $idxKeyMap;

    /** @var array */
    protected $slotItemIdx;

    /** @var int */
    protected $idx;

    public function __construct(array $items, int $slots)
    {
        if ($slots < 0) {
            throw new InvalidArgumentException(
                sprintf('Expected $slots to be a non-negative number, got %s', $slots)
            );
        }

        $this->items = $items;
        $this->slots = $slots;

        // Cannot assume that keys are int in $items, nor can we use array_values which would increase memory usage.
        $this->idxKeyMap = array_keys($items);
    }

    /**
     * @inheritdoc
     */
    public function current()
    {
        $permutation = [];
        foreach ($this->slotItemIdx as $slotItemIdx) {
            $permutation[] = $this->items[$this->idxKeyMap[$slotItemIdx]];
        }

        return $permutation;
    }

    /**
     * @inheritdoc
     */
    public function next()
    {
        for ($i=$this->slots-1; $i>=0; $i--) {
            $itemIdx = $this->slotItemIdx[$i];
            $hasNextItem = key_exists($itemIdx + 1, $this->idxKeyMap);
            if ($hasNextItem) {
                $this->slotItemIdx[$i]++;
                break;
            } else {
                $this->slotItemIdx[$i] = 0;
            }
        }

        $this->idx++;
    }

    /**
     * @inheritdoc
     */
    public function key()
    {
        return $this->idx;
    }

    /**
     * @inheritdoc
     */
    public function valid()
    {
        return $this->slots > 0 && $this->idx < pow(count($this->items), $this->slots);
    }

    /**
     * @inheritdoc
     */
    public function rewind()
    {
        $this->slotItemIdx = array_fill_keys(range(0, $this->slots - 1), 0);
        $this->idx = 0;
    }
}

class PermutationIteratorTest extends TestCase
{
    public function dataIterate(): array
    {
        return [
            // #0
            [
                [1, 2, 3],
                0,
                []
            ],

            // #1
            [
                [],
                1,
                []
            ],

            // #2
            [
                [1],
                2,
                [
                    [1, 1],
                ]
            ],

            // #3
            [
                [1, 2],
                2,
                [
                    [1, 1],
                    [1, 2],
                    [2, 1],
                    [2, 2],
                ]
            ],

            // #4
            [
                [1, 2, 3],
                2,
                [
                    [1, 1],
                    [1, 2],
                    [1, 3],
                    [2, 1],
                    [2, 2],
                    [2, 3],
                    [3, 1],
                    [3, 2],
                    [3, 3],
                ]
            ],

            // #5
            [
                [1, 2, 3],
                3,
                [
                    [1, 1, 1],
                    [1, 1, 2],
                    [1, 1, 3],
                    [1, 2, 1],
                    [1, 2, 2],
                    [1, 2, 3],
                    [1, 3, 1],
                    [1, 3, 2],
                    [1, 3, 3],

                    [2, 1, 1],
                    [2, 1, 2],
                    [2, 1, 3],
                    [2, 2, 1],
                    [2, 2, 2],
                    [2, 2, 3],
                    [2, 3, 1],
                    [2, 3, 2],
                    [2, 3, 3],

                    [3, 1, 1],
                    [3, 1, 2],
                    [3, 1, 3],
                    [3, 2, 1],
                    [3, 2, 2],
                    [3, 2, 3],
                    [3, 3, 1],
                    [3, 3, 2],
                    [3, 3, 3],
                ]
            ],

            // #6
            [
                [new stdClass(), 'string'],
                2,
                [
                    [new stdClass(), new stdClass()],
                    [new stdClass(), 'string'],
                    ['string', new stdClass()],
                    ['string', 'string'],
                ]
            ],

            // #7
            [
                ['key1' => 1, 0 => 2, -1 => 3],
                2,
                [
                    [1, 1],
                    [1, 2],
                    [1, 3],
                    [2, 1],
                    [2, 2],
                    [2, 3],
                    [3, 1],
                    [3, 2],
                    [3, 3],
                ]
            ],
        ];
    }

    /**
     * @dataProvider dataIterate
     *
     * @param array $givenItems
     * @param int   $givenSlots
     * @param array $expectedPermutations
     */
    public function testIterate(array $givenItems, int $givenSlots, array $expectedPermutations): void
    {
        $iterator = new PermutationIterator($givenItems, $givenSlots);

        $actualPermutations = iterator_to_array($iterator);
        $this->assertEquals($expectedPermutations, $actualPermutations);

        // Run again to test ::rewind()
        $actualPermutations = iterator_to_array($iterator);
        $this->assertEquals($expectedPermutations, $actualPermutations);
    }
}