Skip to content

Instantly share code, notes, and snippets.

@gskema
Created February 14, 2019 12:35
Show Gist options
  • Save gskema/8bd4f9b565b888bd9fb42d1fa8b58904 to your computer and use it in GitHub Desktop.
Save gskema/8bd4f9b565b888bd9fb42d1fa8b58904 to your computer and use it in GitHub Desktop.
PHP Permutation Iterator
<?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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment