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.
+3


source to share


1 answer


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';
}

      

+1


source







All Articles