我有一个相当抽象的问题,我想过,但找不到一个有效的解决方案。
问题
假设我们有一个由对象数组表示的规则列表,这些对象都有一个属性,该属性指定了它可以与之相邻的对象的Array[3]:
rules = [{
id: 0,
canMatchWith: [0, 1, 3, 5]
}, {
id: 1,
canMatchWith: [1, 0, 2, 12]
}, ...]每个元素只能与其他3个元素和自身兼容。
问题
给定一个id数组作为输入,没有排序并且可以有重复项,那么输出一个数组以使每个元素都出现在其相邻元素的canMatchWith数组中的有效算法是什么?另一个有趣的问题是:在尝试之前,我们能否快速确定给定输入是否至少有一个解决方案?还有:这是一个排序问题吗?使用图形和节点比使用数组更好吗?
我所有的尝试都涉及多次遍历输入数组,同时对单个项目进行排序,如果这是一个死胡同,它就会重新开始,这是不够的。
我不一定需要一个完整的解决方案,欢迎提出意见和想法。
发布于 2021-09-06 20:36:12
您可以将其解释为图遍历问题:
那么你的排序算法就是一个图遍历问题,你在图中搜索一条路径,每个节点恰好传递一次。我没有搜索一个特定的算法,但我打赌有一些算法在那里,可以确定这样的顺序(即图遍历)是否可能,如果是,它看起来如何…
https://stackoverflow.com/questions/69079943
复制相似问题