PHP Bug

Combinations.php

<?php

class Combinations
{
    public static function unique($values, $minLength = 1, $maxLength = null)
    {
        // $combinations is an array of [["a"], ["a"], … ["a", "b"], ["a", "b", "c"], …]
        // The array may not be sorted. Each internal array IS sorted.
        // Keys produced by the generator are sequential but shouldn't matter

        $combinations = static::sorted($values, $minLength, $maxLength);

        // Uncomment this and everything works correctly
        // $combinations = static::ensurePackedArrays($combinations);

        $combinations = iterator_to_array($combinations, false);

        // Uncommenting this changes the results; Still not perfect
        // sort($combinations, SORT_REGULAR);

        for ($i=0; $i < 10; $i++) {
            $combinations = array_unique($combinations, SORT_REGULAR);
        }

        // Without packed arrays:
        // 340 items - using $i < 0; 144 items - using $i < 1
        // 62 items - using $i < 2; 36 items - using $i < 10

        yield from $combinations;
    }

    private static function ensurePackedArrays($values)
    {
        foreach ($values as $value) {
            $result = [];

            foreach ($value as $i) {
                $result[] = $i;
            }

            yield $result;
        }
    }

    private static function sorted($values, $minLength = 1, $maxLength = null)
    {
        foreach (static::compute($values, $minLength, $maxLength) as $combo) {
            sort($combo, SORT_REGULAR);

            yield array_unique($combo, SORT_REGULAR);
        }
    }

    public static function compute($values, $minLength = 1, $maxLength = null)
    {
        $maxLength = $maxLength ?? count($values);

        for ($length = $minLength; $length <= $maxLength; $length++) {
            yield from static::combinations($values, $length);
        }
    }

    private static function combinations($values, $count)
    {
        $numberOfValues = count($values);
        $possibilities = pow($numberOfValues, $count);

        for ($i = 0; $i < $possibilities; $i++) {
            yield iterator_to_array(static::combination($values, $count, $i), false);
        }
    }

    private static function combination($values, $count, $index)
    {
        $numberOfValues = count($values);

        for ($i = 0; $i < $count; $i++) {
            // Figure out where in the array to start from,
            // given the external state and the internal loop state
            $pos = $index % $numberOfValues;

            // Supply the next item in the combination
            yield $values[$pos];

            $index = ($index - $pos) / $numberOfValues;
        }
    }
}

Usage.php

<?php

// This should produce 15 items. It doesn't. Change the number of iterations of array_unique to see differences.

print_r(iterator_to_array(
  Combinations::unique(["a", "b", "c", "d"]),
  false
));

Version Details

PHP 7.1.5-1+deb.sury.org~xenial+2 (cli) (built: May 22 2017 12:48:42) ( NTS )
Copyright (c) 1997-2017 The PHP Group
Zend Engine v3.1.0, Copyright (c) 1998-2017 Zend Technologies
    with Zend OPcache v7.1.5-1+deb.sury.org~xenial+2, Copyright (c) 1999-2017, by Zend Technologies
    with blackfire v1.17.0~linux-x64-non_zts71, https://blackfire.io, by Blackfireio Inc.