...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Reconstruction of permutations distorted by reversal errors
【24h】

Reconstruction of permutations distorted by reversal errors

机译：重构由于反向误差而失真的排列

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The problem of reconstructing permutations on n elements from their erroneous patterns which are distorted by reversal errors is considered in this paper. Reversals are the operations reversing the order of a substring of a permutation. To solve this problem, it is essential to investigate structural and combinatorial properties of a corresponding Cayley graph on the symmetric group generated by reversals. It is shown that for any n >= 3 an arbitrary permutation pi is uniquely reconstructible from four distinct permutations at reversal distance at most one from a where the reversal distance is defined as the least number of reversals needed to transform one permutation into the other. It is also proved that an arbitrary permutation is reconstructible from three permutations with a probability P3 -> 1 and from two permutations with a probability P-2 similar to 1/3 as n -> infinity. A reconstruction algorithm is presented. In the case of at most two reversal errors it is shown that at least 3/2 (n - 2)(n + 1) erroneous patterns are required in order to reconstruct an arbitrary permutation. (c) 2007 Elsevier B.V. All rights reserved.
机译：本文考虑了从n个元素的错误模式中重建排列的问题，这些错误模式会由于反转误差而失真。逆转是逆转排列的子字符串顺序的操作。为了解决这个问题，研究反转产生的对称群上相应Cayley图的结构和组合性质至关重要。结果表明，对于任何n> = 3，任意排列pi都可以从四个不同的排列中唯一地重建，该排列在一个反向距离处最多为一个，而反向距离定义为将一个排列转换为另一个排列所需的最少数量的反向。还证明了可以从概率为P3-> 1的三个排列和概率为P-2的两个排列（类似于1/3的n->无穷大）重构任意排列。提出了一种重构算法。在最多两个反转误差的情况下，表明至少需要3/2（n-2）（n +1）个错误模式才能重构任意排列。 （c）2007 Elsevier B.V.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号