gpt4 book ai didi

algorithm - 合并一些排序顺序未知的列表

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:31:25 25 4
gpt4 key购买 nike

我有一些元素数量可变的列表。每个列表都已排序,但排序算法未知。我想将这些列表合并成一个大列表,其中包含所有列表的顺序相同,没有重复。

示例输入:

  1. XS,M,L,XL
  2. S,M,XXL
  3. XXS,XS,S,L

预期结果:

  • XXS,XS,S,M,L,XL,XXL

预期的结果是通过匹配输入序列来获得的,以便获得包含正确顺序的每个输入序列的元素的合并结果,如下所示:

    XS   M L XL
S M XXL
XXS XS S L
-------------------
XXS XS S M L XL XXL

如果有位置不明确的元素,函数应该通知。在这里,它将是 XXL(它可以留在 M、L 或 XL 之后),我需要在 XL 之后手动指定它的位置(因为在这里我知道排序算法并且可以提供帮助)。我考虑过定义每两个元素对,每对按原始列表中的顺序排列。从这个可以构建完整的列表。

最佳答案

这可以通过 Topological Sort 来解决算法。

如果您将每个输入序列视为通过有向图的路径,则拓扑排序将从左到右对您的节点集进行排序,使每个有向边都指向右侧。 Diagram of a directed graph after topological sorting

Topological Sorting 上的维基百科页面包括此算法,该算法首先由 Arthur Kahn 于 1962 年描述:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)

这个算法,正如所写的那样,如果它发现不明确的序列实际上并不会失败,但是通过在循环的开头插入一个检查很容易添加,就像这样:

...
while S is non-empty do
if S contains more than 1 item
return error (inputs are ambiguous)
remove a node n from S
...

我不知道您使用的是哪种语言,但我将这个 PHP 实现放在一起作为概念证明:

function mergeSequences($sequences, $detectAmbiguity = false) {

// build a list of nodes, with each node recording a list of all incoming edges
$nodes = array();
foreach ($sequences as $seq) {
foreach ($seq as $i => $item) {
if (!isset($nodes[$item])) $nodes[$item] = array();
if ($i !== 0) {
$nodes[$item][] = $seq[$i-1];
}
}
}

// build a list of all nodes with no incoming edges
$avail = array();
foreach ($nodes as $item => $edges) {
if (count($edges) == 0) {
$avail[] = $item;
unset($nodes[$item]);
}
}

$sorted = array();
$curr = '(start)';
while (count($avail) > 0) {

// optional: check for ambiguous sequence
if ($detectAmbiguity && count($avail) > 1) {
throw new Exception("Ambiguous sequence: {$curr} can be followed by " . join(' or ', $avail));
}

// get the next item and add it to the sorted list
$curr = array_pop($avail);
$sorted[] = $curr;

// remove all edges from the currently selected items to all others
foreach ($nodes as $item => $edges) {
$nodes[$item] = array_diff($edges, array($curr));
if (count($nodes[$item]) == 0) {
$avail[] = $item;
unset($nodes[$item]);
}
}

}

if (count($nodes) > 0) {
throw new Exception('Sequences contain conflicting information. Cannot continue after: ' . join(', ', $sorted));
}

return $sorted;
}

你可以这样调用函数:

$input = array(
array('XS', 'M', 'L', 'XL'),
array('S', 'M', 'XXL'),
array('XXS', 'XS', 'S', 'L'),
);
echo(join(', ', mergeSequences($input)));
echo(join(', ', mergeSequences($input, true)));

得到如下输出:

XXS, XS, S, M, XXL, L, XL
Uncaught exception 'Exception' with message 'Ambiguous sequence: M can be followed by L or XXL'

关于algorithm - 合并一些排序顺序未知的列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4645874/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com