Search for all possible sequences
Hi I am trying to build a function that will loop through all possible numeric sequences and pass the sequence through the function and if it returns true stops.
Here's 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 and $biggest
integer and must be sorted:
/* $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 get my head around myself until the only way to achieve this was to randomize the numbers and sort the array each time. This is clearly not the best way.
Other programming languages will be good too (C ++, C #, js, java).
NOTES
- Duplication of odometer numbers in sequence is not allowed, and the values of each index can be greater than 9.
- A function that tests a sequence for some conditions and returns True or False, it doesn't matter what the actual problem is, generating the sequences one at a time without duplicates.
source to share
It was an interesting challenge to create sequences as you pointed out.
This code below should do what you want (I think). Or, at the very least, you should be able to modify it to suit your needs. I was not exactly sure if you want the function to sequences()
return only the first sequence the test function $functions[$func]
returns for true
, or all sequences so far. This example only returns the first "match" (or null
if no match is found).
This code requires PHP 5.5+ as it uses the generator function (as well as the short array syntax available in PHP 5.4+). I tested this on PHP 5.5.12 and it seems to work as intended. Perhaps the code could be modified to work with older PHP versions (just avoid using generators / outputs). This is actually the first time I've written a PHP generator function.
sequenceGenerator()
is a recursive generator function that you can execute with foreach
.
I also wrote a function echoSequences()
to test sequence generation, which simply outputs all 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';
}
source to share