最大连续可达到的数量

Question

问题

定义

• 让我们将自然数定义为数字集N的可写数(WN)在M数字系统中,如果可以U使用每个成员的成员在该数字系统中写入不超过一次.更严格的'书面'定义:- 这里CONCAT意味着连接.
• 让我们将自然数定义为符号集N的连续可实现数(CAN)在M数字系统,如果它为WN-数U和M,并且还N-1为CAN-数U和M(另一个定义可以N是CAN用于U和M如果所有0 .. N数字是WN为U和M).更严格:

问题

我们有一组S自然数:(我们将零视为自然数)和自然数M,M>1.问题是找到给定U和最大的CAN(MCAN)M.给定集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. 检查是否0是WN给定U和M？转到2:我们完成了,MCAN为空
2. 检查是否1是WN给定U和M？转到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,所以问题是:

• 可能是建设性的算法在这里过度？并且,如果是,可以使用哪些其他选项？
• 有没有更快捷的方法,以确定是否为WN给定数量U和M？(如果前一点有正面答案,我们将无法构建并检查所有数字,这一点可能毫无意义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