时间戳

首页 > 解决方案 > 如何重新排列要与兼容邻居订购的阵列？

arrays - 如何重新排列要与兼容邻居订购的阵列？

问题描述

我有一个相当抽象的问题，我想到了但无法找到有效的解决方案。

问题

假设我们有一个由对象数组表示的规则列表，这些对象数组都有一个属性，该属性指定一个Array[3]可以与之相邻的对象：

rules = [{
  id: 0,
  canMatchWith: [0, 1, 3, 5]
}, {
  id: 1,
  canMatchWith: [1, 0, 2, 12]
}, ...]

每个元素只能兼容，比方说 3 个其他元素，以及它本身。

问题

给定一个包含 s 的数组id作为输入，没有排序并且可以有重复项，什么是可以输出数组以使每个元素都出现在其邻居canMatchWith数组中的有效算法？另一个有趣的问题是：我们能否在尝试之前快速确定给定的输入是否至少有一个解决方案？另外：这是排序问题吗？使用图形和节点而不是数组会更好吗？

我所有的尝试都涉及在订购单个项目时多次遍历输入数组，如果它是死胡同，它只是重新开始，这还不够好。

我不一定需要一个完整的解决方案，欢迎指点和想法。

标签： arraysalgorithmabstract

解决方案

您可以将其解释为图遍历问题：

  • 您的值是图的节点
  • “兼容”关系是边（即，图的两个节点之间存在边，如果它们可以彼此相邻排序）

那么您的排序算法是一个图遍历问题，您可以在其中搜索通过图的路径，将每个节点恰好传递一次。我没有搜索特定的算法，但我敢打赌，那里有一些算法，可以确定这样的顺序（即图遍历）是否可能，如果是的话，它看起来如何......

推荐阅读