寻找所有可能的序列

Question

嗨，我正在尝试构建一个函数，它将遍历所有可能的数字序列并将序列传递给一个函数，如果它 return true 停止。

这是标记：

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。
根据某些条件测试序列并会 return 真或假的函数它做什么并不重要实际问题是一个接一个地生成序列而不重复。

Answer 1

生成您指定的序列是一项有趣的挑战。

下面的这段代码应该可以满足您的需求（我认为）。或者至少您应该能够修改它以满足您的需要。我不确定您是否希望 sequences() 函数仅 return 测试函数 $functions[$func] returns true 的第一个序列，或所有到目前为止的序列。在此示例中，只有第一个 "match" 被 return 编辑（或者 null 如果没有找到匹配项）。

此代码需要 PHP 5.5+，因为它使用 generator 函数（以及 PHP 5.4+ 中可用的短数组语法）。我在 PHP 5.5.12 上对此进行了测试，它似乎按预期工作。如果需要，可以修改代码以在旧的 PHP 版本上工作（只是避免使用 generators/yields）。实际上，这是我第一次编写 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';
}

寻找所有可能的序列

Finding all possible sequences

php

number-sequence