algorithm - 最大连续可达到数

Question

问题

定义

• 让我们为数字集 定义一个自然数 N 作为一个可写数 (WN)在 M 数字系统中，如果它可以从 U 的成员写入此数字系统，使用每个成员不超过一次。 “书面”的更严格定义: - 这里的 CONCAT 表示连接。
• 让我们定义一个自然数 N 作为符号集 的连续可实现数 (CAN)在 M 数字系统中，如果它是 U 和 M 的 WN 编号，并且 N-1 是一个CAN-number for U and M(另一种定义可能是N is CAN for U and M 如果所有 0 .. N 数字对于 U 和 M 都是 WN)。更严格:

问题

让我们有一组 S 个自然数: (我们将零视为自然数)和自然数M，M>1。问题是找到给定 U 和 M 的最大 CAN (MCAN)。给定集合 U 可能包含重复项 - 但每个重复项不能使用多次，这是有原因的(即如果 U 包含 {x, y , y, z} - 那么每个 y 可以使用 0 次或 1 次，所以 y 总共可以使用 0..2 次)。此外 U 预计在 M 数字系统中有效(即不能包含符号 8 或 9 在任何成员如果 M=8)。而且，U 的成员当然是数字，而不是符号 M(所以 11 对 M=10 有效) - 否则问题将是微不足道的。

我的方法

我现在想到了一个简单的算法，它只是通过以下方式检查当前号码是否为 CAN:

1. 对于给定的 U 和 M，检查 0 是否为 WN？转到 2:我们完成了，MCAN 为空
2. 对于给定的 U 和 M，检查 1 是否为 WN？转到 3:我们完成了，MCAN 是 0
3. ...

因此，该算法正在尝试构建所有这些序列。我怀疑这部分是否可以改进，但可以吗？现在，如何检查数字是否为 WN。这也是某种“替代蛮力”。对于 M=10(事实上，因为我们处理的是字符串，任何其他 M 都不是问题)我用 PHP 函数实现了这一点:

//$mNumber is our N, $rgNumbers is our U
function isWriteable($mNumber, $rgNumbers)
{
   if(in_array((string)$mNumber, $rgNumbers=array_map('strval', $rgNumbers), true))
   {
      return true;
   }
   for($i=1; $i<=strlen((string)$mNumber); $i++)
   {
      foreach($rgKeys = array_keys(array_filter($rgNumbers, function($sX) use ($mNumber, $i)
      {
         return $sX==substr((string)$mNumber, 0, $i);
      })) as $iKey)
      {
         $rgTemp = $rgNumbers;
         unset($rgTemp[$iKey]);
         if(isWriteable(substr((string)$mNumber, $i), $rgTemp))
         {
            return true;
         }
      }
   }
   return false;
}

- 所以我们正在尝试一个部分，然后检查其余部分是否可以用递归编写。如果无法写入，我们将尝试 U 的下一个成员。我认为这是一个可以改进的地方。

细节

如您所见，算法试图构建 N 之前的所有数字并检查它们是否为 WN。但唯一的问题是 - 找到 MCAN，所以，问题是:

• 这里可能是建设性算法过多？如果是，还可以使用哪些其他选项？
• 对于给定的 U 和 M，是否有更快速的方法来确定数字是否为 WN？ (如果前一点有肯定答案，这一点可能没有意义，我们不会构建和检查 N 之前的所有数字)。

样本

U = {4, 1, 5, 2, 0}
M = 10

然后 MCAN = 2(无法达到 3)

U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11}
M = 10

然后 MCAN = 21(可以达到之前的所有内容，对于 22，总共没有两个 2 符号)。

Answer 1

散列从 0 到 m-1 的数字的数字计数。对由一个重复数字组成的大于 m 的数字进行哈希处理。

MCAN 受最小的 digit 约束，对于给定的 digit count 无法构造该数字的所有组合(例如，X000,X00X,X0XX,XX0X, XXX0,XXXX) 或 (digit count - 1) 在零的情况下(例如，对于四个数字的所有组合，只需要三个零的组合；对于零计数为零， MCAN 为空)。数字计数按升序计算。

例子:

1. MCAN (10, {4, 1, 5, 2, 0})
   3 is the smallest digit for which a digit-count of one cannot be constructed.
   MCAN = 2

2. MCAN (10, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11})
   2 is the smallest digit for which a digit-count of two cannot be constructed.
   MCAN = 21

3. (from Alma Do Mundo's comment below) MCAN (2, {0,0,0,1,1,1})
   1 is the smallest digit for which all combinations for a digit-count of four
   cannot be constructed.
   MCAN = 1110

4. (example from No One in Particular's answer) 
   MCAN (2, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1111,11111111})
   1 is the smallest digit for which all combinations for a digit-count of five
   cannot be constructed.
   MCAN = 10101