首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何重新排列数组,使其与兼容的相邻数组排序?

问如何重新排列数组,使其与兼容的相邻数组排序?
EN

Stack Overflow用户
提问于 2021-09-06 20:22:53
回答 1查看 26关注 0票数 0

我有一个相当抽象的问题,我想过,但找不到一个有效的解决方案。

问题

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

代码语言:javascript
复制
rules = [{
  id: 0,
  canMatchWith: [0, 1, 3, 5]
}, {
  id: 1,
  canMatchWith: [1, 0, 2, 12]
}, ...]

每个元素只能与其他3个元素和自身兼容。

问题

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

我所有的尝试都涉及多次遍历输入数组,同时对单个项目进行排序,如果这是一个死胡同,它就会重新开始,这是不够的。

我不一定需要一个完整的解决方案,欢迎提出意见和想法。

EN

回答 1

Stack Overflow用户

发布于 2021-09-06 20:36:12

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

  • 你的值是图的结点,兼容关系是边(即,在图的两个结点之间有一条边,如果它们可以相邻排序的话)

那么你的排序算法就是一个图遍历问题,你在图中搜索一条路径,每个节点恰好传递一次。我没有搜索一个特定的算法,但我打赌有一些算法在那里,可以确定这样的顺序(即图遍历)是否可能,如果是,它看起来如何…

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/69079943

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档