algorithm - 最大连续可达到数量

问题

定义

让我们将自然数N定义为M数字系统中设置的数字的可写数字(WN)，前提是它可以使用每个成员从U成员中多次写入此数字系统中。 “书面”的更严格定义:-此处CONCAT表示串联。

让我们将自然数N定义为M数字系统中设置的符号的连续可实现数字(CAN)，如果它是U和M的WN编号，并且N-1是U和M的CAN编号(另一个定义如果N和U的所有M编号均为WN，则对于0 .. N和U可以为M。更严格:

问题

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

我的方法

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

检查给定0和U的M是否为WN？转到2:完成，MCAN为空

检查给定1和U的M是否为WN？转到3:完成了，MCAN是0

...

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

//$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，所以问题是:

可能是 build 性的算法在这里过多吗？而且，如果可以，还可以使用哪些其他选项？

是否有更快速的方法来确定给定U和M的数字是否为WN？ (如果前一点的答案是肯定的，那么这一点可能没有意义，并且我们不会在N之前构建并检查所有数字)。

sample

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符号)。

最佳答案

从0到m-1散列数字的位数。散列大于m的数字，该数字由一个重复的数字组成。

MCAN受最小的digit约束，对于该digit count，不能构造给定(digit count - 1)的该数字的所有组合(例如X000，X00X，X0XX，XX0X，XXX0，XXXX)，或者为零时的ojit_code(例如，对于所有四位数的组合，仅需要三个零的组合；对于零计数的零，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