检测订购是否可行 [英] Detecting if the ordering is possible

问题描述

我们将由多人给出逗号分隔的字符串。现在那些人可能不记得所有的字符串了。但是他们提供的任何顺序都是正确的



例如：

人1：W7，W8，W1，W9

Person2：W8，W9，W2

Person3：W2，W10



**现在我们的角色是检测以上是否全部提到的订单可能**



例如：

第1名：W7，W8

第2名：W8，W9 ，W10

Person3：W10，W7



现在上述订购是不可能的，因为根据person1-W7来到W8之前。对于Person2：W8在W10之前。这意味着W7在W10之前出现。但这与Person3相矛盾，他说W7在W10之后出现





我想要什么？



我不想要代码，但是如何处理这个问题需要一些帮助



< b>我尝试了什么：



我想了很多。但坦率地说，无法想到一个明确的解决方案！



我以为我们可以为它后面和它之前的单词的每个单词保留一个列表。但维护和更新这样的列表太重了！

解决方案

考虑一个序列，例如

W7，W8 ，W1，W9

任何项目都有前面的项目以及以下项目。

例如 W8 有

• 前项 {W7 }
• 以下项目 {W1，W9}

请注意前面项目或以下项目可以是空集。



现在你可以比较两个序列（比如序列 A 和 B ）：对于每个项目序列 A 您可能有两种情况：

1. 您没有按顺序找到相同的项目 B
2. 您按顺序找到相同的项目 B

如果情况1没有不匹配，你可以继续使用下一项序列 A 。



如果是2哟你必须确保在以下项中找不到序列 A 的前面项目中的任何项目序列 B （反之：序列 A 的以下项目中的任何项目都不能在序列 B 的前面的项目中找到。如果情况并非如此，则表示不匹配且两个序列不兼容。



如果两个序列兼容然后你可以合并它们以获得保留项目顺序的合并序列。然后可以将合并的序列与另一个输入序列进行比较，依此类推。



我认为它不是一个智能算法，但它可以工作。

We will be given comma separated strings by multiple people. Now those people may not remember all the strings. But whatever order they provide will be correct

For ex :
Person1 : W7, W8, W1, W9
Person2 : W8, W9, W2
Person3 : W2, W10

**Now our role is to detect whether all the above mentioned orders possible**

For ex :
Person1 : W7, W8
Person2 : W8, W9, W10
Person3 : W10, W7

Now the above ordering is not possible because according to person1 - W7 comes before W8. Acc to Person2 : W8 comes before W10. That means W7 comes before W10. But this contradicts with Person3 who says W7 comes after W10


What I want ?

I don't want the code but some help as to how to approach this question

What I have tried:

I thought about it a lot. But frankly was unable to think of a clear solution!

I thought we could maintain a list for each word of the words that come after it and before it. But maintaining and updating such a list is too heavy !

解决方案

Consider a sequence, e.g.
W7,W8,W1,W9
Any item has preceding items as well as following items.
For instance W8 has

• preceding items {W7}
• following items {W1,W9}

Please note either preceding items or following items could be the empty set.

Now you can compare two sequences (say sequence A and B): for every item of the sequence A you may have two cases:

1. You don't find the same item in sequence B
2. You find the same item in sequence B

In case 1 there is no mismatch, and you can go on with next item of sequence A.

In case 2 you have to make sure that any item in the preceding items of sequence A cannot be found in the following items of sequence B (and viceversa: any item in the following items of sequence A cannot be found in the preceding items of sequence B). If this is not the case then ther is a mismatch and the two sequences are incompatible.

If two sequences are compatible then you can merge them in order to obtain a merged sequence that preserves items order. The merged sequence could in turn be compared with another input sequence, and so on.

I think it isn't a smart algorithm, however it could work.

这篇关于检测订购是否可行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！