Нахождение всех возможных последовательностей
Привет, я пытаюсь построить функцию, которая будет проходить через все возможные числовые последовательности и передавать последовательность через функцию, и если она вернет истину, останавливается.
Вот разметка:
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.
}
}
Сгенерированная последовательность будет иметь $long уникальный значения между $smallest целое число $biggest целое и должно быть отсортировано пример:
/* $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
* ...
*/
Я не мог обернуть это вокруг головы, пока единственный способ, которым я достиг, это генерировать числа случайным образом и затем сортировать массив каждый раз.
Это явно не лучший способ.
Также подойдут и другие языки программирования (c ++, C #, js, java).
ЗАМЕТКИ
- Это не одометр дубликаты чисел в последовательности не допускаются, и значения каждого индекса могут быть больше, чем 9.
- Функция, которая проверяет последовательность на соответствие некоторым условиям и возвращает True или False, независимо от того, что она делает, на самом деле проблема заключается в генерации последовательностей одна за другой без дубликатов.
Решение
Это было забавное испытание для генерации последовательностей, как вы указали.
Этот код ниже должен делать то, что вы хотите (я думаю). Или, по крайней мере, вы сможете изменить его в соответствии со своими потребностями. Я не был точно уверен, что вы хотели sequences() функция для возврата только первой последовательности, для которой тестовая функция $functions[$func] возвращается trueили все последовательности пока. В этом примере возвращается только первое «совпадение» (или null если совпадений не найдено).
Этот код требует PHP 5.5+, так как он использует генератор функция (а также синтаксис короткого массива, доступный в PHP 5.4+). Я проверил это на PHP 5.5.12, и он, кажется, работает как задумано. Код, вероятно, может быть изменен для работы на старых версиях PHP, если это необходимо (просто избегайте использования генераторов / выходов). На самом деле, я впервые написал функцию генератора PHP.
sequenceGenerator() рекурсивная функция генератора, которую вы можете перебрать, используя foreach,
Я также написал echoSequences() функция для тестирования генерации последовательности, которая просто выводит все сгенерированные последовательности в порядке, используя 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';
}
Другие решения
Других решений пока нет …