Finding all possible sequences

Question

Hi I'm trying to build a function which will walk through all possible number sequences and pass the sequence through a function and if it return true stops.

Here is the markup:

function sequences($smallest, $biggest, $long, $func) {
   $seq = array(); // Will have $long values 
   /*
    * generates the sequence
   */

   if (call_user_func($functions[$func])) {
      return $seq;
   } else {
      //generate next sequence.
   }

} 

The generated sequence will have $long unique values between $smallest integer to $biggest integer and must be sorted example:

/* $long = 4; $smallest = 5, $biggest = 10;
 * 
 * 5,6,7,8
 * 5,6,7,9
 * 5,6,7,10
 * 5,6,8,9
 * 5,6,8,10
 * ...
 * 7,8,9,10
 *
 *
 * $long = 4; $smallest = 15, $biggest = 60;
 *
 * ...
 * 15,41,49,56
 * ...
 * 37,39,53,60
 * ...
 */

I haven’t been able to wrap my head around it, so far the only way I achieve that was to generate numbers randomly and than sorting the array each time. That's clearly not the best way.

Other programming languages will be great too (c++, C#, js, java).

NOTES

• Its not an odometer duplicate numbers in the sequence are not allowed and the values of each index can be bigger than 9.
• The function that tests the sequence against a some conditions and will return True or False it doesn't matter what it does the actual problem is generating the sequences one by one without duplicates.

Answer 1

This was a fun challenge to generate the sequences as you specified.

This code below should do what you want (I think). Or at least you should be able to modify it to suit your needs. I wasn't exactly sure if you wanted the sequences() function to return only the first sequence for which the test function $functions[$func] returns true, or all the sequences so far. In this example only the first "match" is returned (or null if no match was found).

This code requires PHP 5.5+ as it uses a generator function (and also short array syntax available in PHP 5.4+). I tested this on PHP 5.5.12 and it seems to work as intended. The code can probably be modified to work on older PHP versions if needed (just avoid using generators/yields). Actually this is the first time I've written a PHP generator function.

sequenceGenerator() is a recursive generator function that you can iterate over using foreach.

I also wrote an echoSequences() function for testing the sequence generation which just outputs all of the generated sequences in order using echo.

function sequenceGenerator(array $items, $long = null, $level = 1, $path = null) {
    $itemCount = count($items);
    if (empty($long)) $long = $itemCount;
    if ($path == null) $path = [];

    if ($itemCount > 1) {
        foreach ($items as $item) {
            $subPath = $path;
            $subPath[] = $item;
            if ($level == $long) {
                yield $subPath;
                continue;
            }

            if (count($subPath) + count($items) > $long) {
                $items = array_values(array_diff($items, [$item]));
                $iteration = sequenceGenerator($items, $long, $level + 1, $subPath);
                foreach ($iteration as $value) yield $value;
            }
        }
    } elseif ($itemCount == 1) {
        $path[] = $items[0];
        yield $path;
    }
}

// Function for testing sequence generation
function echoSequences($smallest, $biggest, $long) {
    $items = range($smallest, $biggest);
    foreach (sequenceGenerator($items, $long) as $sequence) {
        echo implode(',', $sequence)."<br>\n";
    }
}

function sequences($smallest, $biggest, $long, $func) {
    global $functions;
    $items = range($smallest, $biggest);
    foreach (sequenceGenerator($items, $long) as $sequence) {
        if (call_user_func($functions[$func], $sequence)) {
            return $sequence;
        }
    }
    return null; // Return null when $func didn't return true for any sequence
}

//echoSequences(5, 10, 4); // Test sequence generation

$functions = array(
    // This test function returns true only for the sequence [5,6,8,10]
    'testfunc' => function($sequence) { return ($sequence == [5,6,8,10]); }
);

$sequence = sequences(5, 10, 4, 'testfunc'); // Find the first sequence that 'testfunc' will return true for (or null)
if (!empty($sequence)) {
    echo 'Found match: '.implode(',', $sequence);
} else {
    echo 'Match not found';
}