logo标签列表

最大连续可达数字

algorithmnumbers
11

问题

定义

  • 我们将正整数N 定义为数字集合 enter image description here 在M进制下的可写数字(WN)，如果它可以从U的成员中使用每个成员不超过一次进行此数位记数。更严格的定义是: enter image description here - 这里的CONCAT表示连接。
  • 我们将正整数N 定义为符号集合 enter image description here 在M进制下的连续可实现数字(CAN)，如果它是U和M的WN数字，并且N-1是U和M的CAN数字(另一个定义可能是如果0 ..N的所有数字都是U和M的WN，则N是U和M的CAN数字)。更严格的定义是: enter image description here

问题

假设我们有一组自然数S: enter image description here (我们将零视为自然数) 和自然数M，其中M>1。问题是找到给定的U和M的最大CAN(MCAN)。给定的集合U可能包含重复项-但每个重复项不能使用超过一次，当然(即如果U包含{x, y, y, z}-则每个y可以使用0或1次，因此y总共可以使用0..2次)。同时期望U在M-进制下有效(即如果M=8，则任何成员中都不能包含符号8或9)。并且，当然，U的成员是数字，而不是符号(所以对于M=10来说,11是有效的)-否则，该问题将变得微不足道。

我的方法

我现在想到了一个简单的算法，它仅通过检查当前数字是否为CAN来进行:

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

因此，该算法正在尝试构建所有这些序列。我怀疑这部分可能无法改进，但也许可以？现在，如何检查数字是否为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，因此问题是：

  • 在这里使用构造算法是否过度？如果是，还有什么其他选项可供使用？
  • 有更快的方法确定给定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符号）。

@JanDvorak 为什么是错误的？ 11>10 - 是的，但是10可以由1和0组合而成 - 它们存在于U中。 - Alma Do
@JanDvorak 啊，我的疏忽。成员是“数字”，而不是“符号”。并且它们应该在“M”进制系统中有效（11是有效的十进制数）。对于您的观点，“F3A”将不是具有“M = 10”的有效“U”数字，但将具有“M = 16”的有效数字。否则，这个问题将是微不足道的（如果“U”的成员是符号，则MCAN始终不会大于“M”） - Alma Do
3
@Jack - 什么问题？而且，请不要为这种事情建议程序员。这不是一个 SO 不相关的倾倒场。 - Oded
@Oded 我只投了一票；它没有被迁移，所以我认为你有点反应过度。 - Ja͢ck
2
这个问题似乎更适合在http://cs.stackexchange.com上提问。 - RBarryYoung
显示剩余22条评论
3个回答
2

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

MCAN受最小数字的限制，对于给定数字计数，不能构造该数字的所有组合（例如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
我认为错误始于“将大于m的数字存储为额外计数”。一个示例：MCAN(10, {0,1,2}) = 2，而MCAN(10, {10, 2}) = null - 但是0,1,2和10,2都具有相同的符号。 - Alma Do
MCAN是一个缩写。从{10, 2}只能创建102和210，所以即使是0也不是{10, 2}的WN - 因此MCAN为空。 - Alma Do
@AlmaDoMundo 数字计数意味着数字在集合中出现的次数，例如{1,1,2,3} => 2个数字1，1个数字2，1个数字3。哈希只是指保持记录，以便您可以查找数字并查看其计数，或查找数字并查看它是否在集合中。 - גלעד ברקן
我看到了你的样例，但是对于一般情况下该如何操作并不清楚（因此我要求你描述完整的流程（即没有“等等”））。 - Alma Do
是的，我应该去睡觉了 :p 谢谢。 - Alma Do
显示剩余12条评论
2

我所做的递归步骤如下：

  1. 如果数字字符串在你的字母表中可用，则标记为已使用并立即返回
  2. 如果数字字符串长度为1，则返回失败
  3. 将字符串分成两部分并尝试每个部分

这是我的代码：

$u = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11];

echo ncan($u), "\n"; // 21

// the functions

function satisfy($n, array $u)
{
        if (!empty($u[$n])) { // step 1
                --$u[$n];
                return $u;
        } elseif (strlen($n) == 1) { // step 2
                return false;
        }

        // step 3
        for ($i = 1; $i < strlen($n); ++$i) {
                $u2 = satisfy(substr($n, 0, $i), $u);
                if ($u2 && satisfy(substr($n, $i), $u2)) {
                        return true;
                }
        }

        return false;
}

function is_can($n, $u)
{
        return satisfy($n, $u) !== false;
}

function ncan($u)
{
        $umap = array_reduce($u, function(&$result, $item) {
                @$result[$item]++;
                return $result;
        }, []);
        $i = -1;

        while (is_can($i + 1, $umap)) {
                ++$i;
        }

        return $i;
}
谢谢你的工作。我看到这也是一种有建设性的算法：检查数字是否为WN，然后继续下一个，同时数字是WN，对吗？ - Alma Do
@AlmaDoMundo 是的，我认为没有其他方法；如果有的话，我很想知道 :) - Ja͢ck
我实际上正在尝试理解上面回答中的这种方式（似乎它是不建设性的）- 不幸的是，目前没有成功。 - Alma Do
@AlmaDoMundo 当你进行递归步骤时，你的前缀必须是可达到的，但你只测试了后缀。 - Ja͢ck
1
@AlmaDoMundo 但是 isWriteable(101, [10, 0, 1]) 是 false。我认为它应该是 true。 - Ja͢ck
显示剩余12条评论
1
这里是另一种方法：

1) 将集合U按照基数为M的常规数字排序。
2) 如果0到(M-1)之间缺少某个符号，则该符号是第一个不是MCAN的数字。
3) 找到在集合U中条目最少的第一个符号。从这里我们可以得到第一个不是MCAN的数字的上限。例如，如果M = 4且U = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3}，则数字333不是MCAN。这给我们提供了上限。
4) 因此，如果集合U中具有小数量出现次数的第一个元素为x，并且它具有C个出现次数，则我们可以清楚地表示任何具有C位数的数字。(因为每个元素至少有C个条目)。
5) 现在我们问是否存在小于(C+1)x的任何数字都不能是MCAN？好吧，任何(C+1)位数的数字都可以具有(C+1)个相同的符号或只有最多(C)个相同的符号。由于x是步骤3中的最小值，因此(C+1)y对于y < x是可以完成的，对于任何不同的a、b，(C)a + b都可以完成，因为它们至少有(C)个副本。

上述方法仅适用于只有一个符号的集合元素。但是，如果允许多个符号元素，则变得更加复杂。考虑以下情况：
U = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1111,11111111}
定义 c(A,B) 为长度为 B 中 A 符号的数量。
因此，对于我们的示例，c(0,1) = 15，c(0,2) = 0，c(0,3) = 0，c(0,4) = 0，... c(1,1) = 3，c(1,2) = 0，c(1,3) = 0，c(1,4) = 1，c(0,5) = 0，...，c(1,8) = 1。

我们无法生成的最大0串是16。我们无法生成的最大1串也是16。
1 = 1
11 = 1+1
111 = 1+1+1
1111 = 1111
11111 = 1+1111
111111 = 1+1+1111
1111111 = 1+1+1+1111
11111111 = 11111111
111111111 = 1+11111111
1111111111 = 1+1+11111111
11111111111 = 1+1+1+11111111
111111111111 = 1111+11111111
1111111111111 = 1+1111+11111111
11111111111111 = 1+1+1111+11111111
111111111111111 = 1+1+1+1111+11111111

但我们能使字符串变成11111101111吗？不能，因为最后一个1的字符串（1111）需要唯一一组连续的1，它们在4个位置上。一旦我们取走了它，我们就不能再制作第一个1字符串（111111），因为我们只有一个8（太大了）或3个长度为1的1（太小了）。
所以对于多个符号，我们需要另一种方法。
我们可以从排序和排列字符串中知道对于给定符号我们无法做到的最小长度。（在上面的例子中，它将是16个零或16个1。）因此，这是我们答案的上限。
现在我们要做的是从1开始，在M进制下计数。 对于每个数字，我们将其写成M进制，然后确定我们是否可以用集合U组成它。 我们使用与硬币找零问题相同的方法来进行动态规划。(例如，有关算法，请参见http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/)唯一的区别是，在我们的情况下，每个元素只有有限数量，而不是无限供应。
与硬币找零问题不同的是，我们不是减去我们正在使用的金额，而是从我们正在尝试匹配的字符串前面删除匹配的符号。（这与我们的加法-连接操作相反。）
@AlmaDoMundo和No One in Particular，这不就是我的答案吗？ - גלעד ברקן
在这种情况下，我也向您鞠躬致敬！ - גלעד ברקן
1
@NoOneinParticular 你可能需要考虑当 XXX 可以由 X 和 XX 构成的情况，例如。我似乎在你的回答中没有找到这个。 - גלעד ברקן
@groovy，这是另一个不可行的方案。有很多这样的方案。我只是展示了其中一个。我认为动态编程部分寻找答案是大部分工作所在。（请注意，您应该从“0”开始递增，直到找到一个不起作用的方案。使用您的示例，即使“10111”也不起作用，它比您的示例更小。）我越想这个问题，就越喜欢它。 - No One in Particular
好的观点。你的例子向我展示了我的想法还有更多可以做的，虽然我认为一个通用公式是可以实现的。 - גלעד ברקן
显示剩余3条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接