如何确定从序列中删除子序列的所有可能方式?

2024-02-27

给定两个序列,A and B,我怎样才能生成所有可能的方式的列表B可以从中删除A?

例如,在 JavaScript 中,如果我有一个函数removeSubSeq采用两个满足我要求的数组参数,它将按如下方式工作:

removeSubSeq([1,2,1,3,1,4,4], [1,4,4])会回来[ [2,1,3,1], [1,2,3,1], [1,2,1,3] ]因为最后的 4 会匹配,并且 1 可能有 3 个位置匹配

removeSubSeq([8,6,4,4], [6,4,8])会回来[]因为第二个参数实际上不是子序列

removeSubSeq([1,1,2], [1])会回来[ [1,2], [1,2] ]因为有两种方法可以删除 1,即使它会导致重复


这个问题可以解决O(n*m + r)时间、地点r是结果的总长度,使用经典的最长公共子序列 https://en.wikipedia.org/wiki/Longest_common_subsequence_problem算法。

一旦表格制作完成,如维基百科所示example https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Traceback_approach,将其替换为带有对角箭头的单元格列表,这些单元格也具有与其行相对应的值。现在,从最后一行中带有对角线的每个单元格向后遍历,累积字符串中的相关索引,并复制和分割累积值,使得带有对角线箭头的每个单元格将延续到前一行中带有对角线的所有单元格,即位于其左侧(在构建矩阵时也存储该计数),并且值减一。当累加达到零单元格时,拼接字符串中累加的索引并将其相加作为结果。

(箭头对应于迄今为止LCS是否来自LCS(X[i-1],Y[j]) and/or LCS(X[i],Y[j-1]), or LCS(X[i-1],Y[j-1]),看函数定义 https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#LCS_function_defined.)

例如:

  0  a  g  b  a  b  c  c
0 0  0  0  0  0  0  0  0
a 0 ↖1  1  1 ↖1  1  1  1
b 0  1  1 ↖2  2 ↖2  2  2
c 0  1  1  2  2  2 ↖3 ↖3

JavaScript 代码:

function remove(arr,sub){
  var _arr = [];
  arr.forEach(function(v,i){ if (!sub.has(i)) _arr.push(arr[i]); });
  return _arr;
}

function f(arr,sub){
  var res = [],
      lcs = new Array(sub.length + 1),
      nodes = new Array(sub.length + 1);
     
  for (var i=0; i<sub.length+1;i++){
    nodes[i] = [];
    lcs[i] = [];
   
    for (var j=0; j<(i==0?arr.length+1:1); j++){
      // store lcs and node count on the left
      lcs[i][j] = [0,0];
    }
  }
 
  for (var i=1; i<sub.length+1;i++){ 
    for (var j=1; j<arr.length+1; j++){
      if (sub[i-1] == arr[j-1]){
        lcs[i][j] = [1 + lcs[i-1][j-1][0],lcs[i][j-1][1]];
       
        if (lcs[i][j][0] == i){
                  // [arr index, left node count above]
          nodes[i].push([j - 1,lcs[i-1][j-1][1]]);
       
          lcs[i][j][1] += 1;
        }
       
      } else {
        lcs[i][j] = [Math.max(lcs[i-1][j][0],lcs[i][j-1][0]),lcs[i][j-1][1]];
      }
    }
  }
   
  function enumerate(node,i,accum){
    if (i == 0){
      res.push(remove(arr,new Set(accum)));
      return;
    }
    
    for (var j=0; j<node[1]; j++){
      var _accum = accum.slice();
      _accum.push(nodes[i][j][0]);
      
      enumerate(nodes[i][j],i - 1,_accum);
    }
  }
  
  nodes[sub.length].forEach(function(v,i){ 
    enumerate(nodes[sub.length][i],sub.length - 1,[nodes[sub.length][i][0]]); 
  });

  return res;
}

console.log(JSON.stringify(f([1,2,1,3,1,4,4], [1,4,4])));
console.log(JSON.stringify(f([8,6,4,4], [6,4,8])));
console.log(JSON.stringify(f([1,1,2], [1])));
console.log(JSON.stringify(f(['a','g','b','a','b','c','c'], ['a','b','c'])));
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

如何确定从序列中删除子序列的所有可能方式? 的相关文章

  • 使用 vscode 调试器调试 next.js

    我已经使用安装了一个项目创建下一个应用程序 https github com segmentio create next app 我需要使用我的编辑器 vscode 调试服务器端渲染 所以我访问过vscode recipes 如何调试 ne
  • Web 串行 API - 未捕获(承诺中)DOMException:无法打开串行端口/所需成员 baudRate 未定义

    下面的代码可以在我的 Xubuntu 机器上运行 但现在我在 Kubuntu 上 它不再工作了 它不会打开端口 Arduino IDE 工作正常 可以向开发板写入代码 并且我可以在 Chrome 中选择设备 Arduino Uno 但当我尝
  • TypeError: props.render 不是一个函数(React hook 形式)

    我将方法作为我用react hook form制作的形式的道具传递 当从react hook form添加控制器时 它给了我 TypeError props render不是一个函数 我在网上找不到任何解决方案 因此感谢任何帮助 impor
  • 解析“流”JSON

    我在浏览器中有一个网格 我想通过 JSON 将数据行发送到网格 但浏览器应该在接收到 JSON 时不断解析它 并在解析时将行添加到网格中 换句话说 在接收到整个 JSON 对象后 不应将行全部添加到网格中 应该在接收到行时将其添加到网格中
  • Javascript正则表达式用于字母字符和空格? [关闭]

    这个问题不太可能对任何未来的访客有帮助 它只与一个较小的地理区域 一个特定的时间点或一个非常狭窄的情况相关 通常不适用于全世界的互联网受众 为了帮助使这个问题更广泛地适用 访问帮助中心 help reopen questions 我需要一个
  • 在requestAnimationFrame中使用clearRect不显示动画

    我正在尝试在 HTML5 画布上做一个简单的 javascript 动画 现在我的画布是分层的 这样当我收到鼠标事件时 背景层不会改变 但带有头像的顶层会移动 如果我使用 requestAnimationFrame 并且不清除屏幕 我会看到
  • 如何将 Google Charts 与 Vue.js 库一起使用?

    我正在尝试使用 Vue js 库使用 Google Charts 制作图表 但我不知道如何添加到 div 这是我尝试做的 这是如何使用普通 javascript 添加图表 这是文档的代码示例 https developers google
  • Jquery/Javascript 上传和下载文件,无需后端

    是否可以在没有后端服务器的情况下在 JavaScript 函数中下载和上传文件 我需要导出和导入由 JavaScript 函数生成的 XML 我想创建按钮 保存 xml 来保存文件 但我不知道是否可行 另一方面 我希望将 XML 文件直接上
  • Meteor - 从客户端取消服务器方法

    我正在通过服务器方法执行数据库计数 用户可以选择他们希望如何执行计数 然后调用该方法 我的问题是 计数可能需要一些时间 并且用户可能会在方法运行时改变主意并请求不同的计数 有什么方法可以取消调用的方法并运行新的计数吗 我认为 this un
  • 如何使输入字段和提交按钮变灰

    我想变灰这两件事 http doorsplit heroku com 歌曲输入字段和提交按钮 直到用户输入艺术家 有没有一种简单的方法可以通过 JQuery 来做到这一点 艺术家输入字段的id是 request artist 你可以这样做
  • Javascript 数组到 VBScript

    我有一个使用 Javascript 构建的对象数组 我需要使用 VBScript 读取它 如下例所示 我找不到在 VbScript 代码中循环遍历数组的方法myArray object 这个例子是我的问题的简化 我无法更改页面的默认语言 这
  • Laravel 中只向登录用户显示按钮

    如果我以 John 身份登录 如何才能只显示 John 的红色按钮而不显示 Susan 的红色按钮 测试系统环境 Win10 Laravel5 4 Mysql5 7 19 table class table table responsive
  • 为 illustrator 导出脚本以保存为 web jpg

    任何人都可以帮我为 illustrator CC2017 编写一个脚本 将文件以 JPG 格式导出到网络 旧版 然后保存文件并关闭 我有 700 个文件 每个文件有 2 个画板 单击 文件 gt 导出 gt 另存为 Web 旧版 然后右键文
  • 如何在类似控制台的环境中运行 JavaScript?

    我正在尝试遵循这里的示例 http eloquentjavascript net chapter2 html http eloquentjavascript net chapter2 html and print blah 在浏览器中运行时
  • Javascript 纪元时间(以天为单位)

    我需要以天为单位的纪元时间 迄今为止 我已经看到过有关如何翻译它的帖子 但几天后就没有了 我对纪元时间很不好 我怎么能得到这个 我需要以天为单位的纪元时间 我将解释为您想要自纪元以来的天数 纪元本身是第 0 天 或第 1 天的开始 无论您如
  • 如何仅在最后一个
  • 处给出透明六边形角度?
  • 我必须制作这样的菜单 替代文本 http shup com Shup 330421 1104422739 My Desktop png http shup com Shup 330421 1104422739 My Desktop png
  • 将 MQTTNet 服务器与 MQTT.js 客户端结合使用

    我已经启动了一个 MQTT 服务器 就像this https github com chkr1011 MQTTnet tree master例子 该代码托管在 ASP Net Core 2 0 应用程序中 但我尝试过控制台应用程序 但没有成
  • 如何在 pg-promise 中设置模式

    我正在搜索的文档pg 承诺 https github com vitaly t pg promise特别是在创建客户端时 但我无法找到设置连接中使用的默认架构的选项 它始终使用public架构 我该如何设置 通常 为数据库或角色设置默认架构
  • 如何获取浏览器视口中当前显示的内容

    如何获取当前正在显示长文档的哪一部分的指示 例如 如果我的 html 包含 1 000 行 1 2 3 9991000 并且用户位于显示第 500 行的中间附近 那么我想得到 500 n501 n502 或类似的内容 显然 大多数场景都会比
  • 从列表中选择项目以求和

    我有一个包含数值的项目列表 我需要使用这些项目求和 我需要你的帮助来构建这样的算法 下面是一个用 C 编写的示例 描述了我的问题 int sum 21 List

随机推荐