查找对列表进行排序的替换
Find a substitution that sorts the list
考虑以下词语：
PINEAPPLE
BANANA
ARTICHOKE
TOMATO
目标是在不移动单词本身的情况下对其进行排序（按字典顺序），而是使用字母替换。在这个例子中，我可以把字母P换成A，A换成P，所以：
AINEPAALE
BPNPNP
PRTICHOKE
TOMPTO
这是一个按字典顺序排列的列表。如果你切换字母，字母将在所有单词中切换。值得注意的是，您可以使用整个字母表，只使用列表中单词中的字母。
我花了相当多的时间来解决这个问题，但除了暴力破解（尝试所有字母开关组合）之外我想不出任何其他办法，也无法想出定义 的条件当列表可以排序时.
更多示例：
ABC
ABB
ABD
可以变成
ACB
ACC
ACD
满足条件
- 提取列表中每个单词的所有首字母。 (P,B,A,T)
- 对列表进行排序。 (A,B,P,T)
- 将单词中出现的所有第一个字母替换为排序列表中的第一个字符。
将所有单词中的 P(Pineapple) 替换为 A.
将所有单词中的 B 替换为 B。
将所有单词中的 A 替换为 P。
将所有单词中的 T 替换为 T。
这将为您提供预期的结果。
编辑：
- 比较两个相邻的字符串。如果一个 比另一个大，则找到第一次出现的字符不匹配并交换并用交换后的字符替换所有单词。
- 像冒泡排序一样对整个列表重复此操作。
例子-
ABC < ABB
第一个字符不匹配出现在第 3 个位置。所以我们用 B 交换所有 C。
更新： 最初的分析是错误的，并且在一些 class 的测试用例上失败了，正如 指出的那样。
我相信这可以用 topological sort 的形式解决。您的初始单词列表定义了某组字母的偏序或有向图。您希望找到一个替代品来线性化这个字母图。让我们使用您的一个重要示例：
P A R K O V I S T E
P A R A D O N T O Z A
P A D A K
A B B A
A B E C E D A
A B S I N T
让x <* y表示substitution(x) < substitution(y)一些字母（或单词）x和y。我们想要整体word1 <* word2 <* word3 <* word4 <* word5 <* word6，但是在字母方面，我们只需要查看每对相邻的单词并找到同一列中的第一对不同字符：
K <* A (from PAR[K]OVISTE <* PAR[A]DONTOZA)
R <* D (from PA[R]ADONTOZA <* PA[D]AK)
P <* A (from [P]ADAK <* [A]BBA)
B <* E (from AB[B]A <* AB[E]CEDA)
E <* S (from AB[E]CEDA <* AB[S]INT)
如果我们没有发现不匹配的字母，那么有 3 种情况：
- 单词 1 和单词 2 相同
- 单词 1 是单词 2 的前缀
- 单词 2 是单词 1 的前缀
在情况 1 和情况 2 中，单词已经按字典顺序排列，因此我们不需要执行任何替换（尽管我们可能会这样做）并且它们不会添加我们需要遵守的额外限制。在情况 3 中，根本没有替代方法可以解决这个问题（想想 ["DOGGO", "DOG"]），所以没有可能的解决方案，我们可以提前退出。
否则，我们根据得到的偏序信息构建对应的有向图，并进行拓扑排序。如果排序过程表明不可能进行线性化，那么就没有对单词列表进行排序的解决方案。否则，你会得到类似的东西：
P <* K <* R <* B <* E <* A <* D <* S
根据您实现拓扑排序的方式，您可能会得到不同的线性排序。现在您只需要为每个字母分配一个符合此顺序且本身按字母顺序排序的替换。一个简单的选择是将线性顺序与按字母顺序排序的自身配对，并将其用作替代：
P <* K <* R <* B <* E <* A <* D <* S
| | | | | | | |
A < B < D < E < K < P < R < S
但如果您愿意，可以实施不同的替换规则。
这是 Python 中的概念验证：
import collections
import itertools
# a pair of outgoing and incoming edges
Edges = collections.namedtuple('Edges', 'outgoing incoming')
# a mapping from nodes to edges
Graph = lambda: collections.defaultdict(lambda: Edges(set(), set()))
def substitution_sort(words):
graph = build_graph(words)
if graph is None:
return None
ordering = toposort(graph)
if ordering is None:
return None
# create a substitition that respects `ordering`
substitutions = dict(zip(ordering, sorted(ordering)))
# apply substititions
return [
''.join(substitutions.get(char, char) for char in word)
for word in words
]
def build_graph(words):
graph = Graph()
# loop over every pair of adjacent words and find the first
# pair of corresponding characters where they differ
for word1, word2 in zip(words, words[1:]):
for char1, char2 in zip(word1, word2):
if char1 != char2:
break
else: # no differing characters found...
if len(word1) > len(word2):
# ...but word2 is a prefix of word1 and comes after;
# therefore, no solution is possible
return None
else:
# ...so no new information to add to the graph
continue
# add edge from char1 -> char2 to the graph
graph[char1].outgoing.add(char2)
graph[char2].incoming.add(char1)
return graph
def toposort(graph):
"Kahn's algorithm; returns None if graph contains a cycle"
result = []
working_set = {node for node, edges in graph.items() if not edges.incoming}
while working_set:
node = working_set.pop()
result.append(node)
outgoing = graph[node].outgoing
while outgoing:
neighbour = outgoing.pop()
neighbour_incoming = graph[neighbour].incoming
neighbour_incoming.remove(node)
if not neighbour_incoming:
working_set.add(neighbour)
if any(edges.incoming or edges.outgoing for edges in graph.values()):
return None
else:
return result
def print_all(items):
for item in items:
print(item)
print()
def test():
test_cases = [
('PINEAPPLE BANANA ARTICHOKE TOMATO', True),
('ABC ABB ABD', True),
('AB AA AB', False),
('PARKOVISTE PARADONTOZA PADAK ABBA ABECEDA ABSINT', True),
('AA AB CA', True),
('DOG DOGGO DOG DIG BAT BAD', False),
('DOG DOG DOGGO DIG BIG BAD', True),
]
for words, is_sortable in test_cases:
words = words.split()
print_all(words)
subbed = substitution_sort(words)
if subbed is not None:
assert subbed == sorted(subbed), subbed
print_all(subbed)
else:
print('<no solution>')
print()
print('expected solution?', 'yes' if is_sortable else 'no')
print()
if __name__ == '__main__':
test()
现在，它并不理想——例如，即使原始单词列表已经排序，它仍然执行替换——但它似乎可以工作。虽然我无法正式证明它有效，所以如果你找到反例，请告诉我！
让我们暂时假设特定情况下可能会出现该问题。此外，为简单起见，假设所有单词都是不同的（如果两个单词相同，则它们必须相邻并且可以忽略一个）。
然后问题变成了拓扑排序，虽然细节和可疑狗的答案略有不同，遗漏了一些情况。
考虑一个包含 26 个节点的图，标记为 A 到 Z。每对单词为偏序贡献一个有向边；这对应于单词不同的第一个字符。例如，ABCEF和ABRKS这两个词的顺序，第一个不同的是第三个字符，所以sigma(C) < sigma(R)。
结果可以通过对该图进行拓扑排序，并将排序中的第一个节点替换为 A，第二个节点替换为 B，依此类推。
请注意，这也提供了一个有用的衡量方法，可以衡量问题何时无法解决。当两个词相同但不相邻（在 "cluster" 中），当一个词是另一个词的前缀但在它之后，或者当图有一个循环并且拓扑排序是不可能的时候，就会发生这种情况。
这里是 Python 中的一个功能齐全的解决方案，包括检测何时无法解决问题的特定实例。
def topoSort(N, adj):
stack = []
visited = [False for _ in range(N)]
current = [False for _ in range(N)]
def dfs(v):
if current[v]: return False # there's a cycle!
if visited[v]: return True
visited[v] = current[v] = True
for x in adj[v]:
if not dfs(x):
return False
current[v] = False
stack.append(v)
return True
for i in range(N):
if not visited[i]:
if not dfs(i):
return None
return list(reversed(stack))
def solve(wordlist):
N = 26
adj = [set([]) for _ in range(N)] # adjacency list
for w1, w2 in zip(wordlist[:-1], wordlist[1:]):
idx = 0
while idx < len(w1) and idx < len(w2):
if w1[idx] != w2[idx]: break
idx += 1
else:
# no differences found between the words
if len(w1) > len(w2):
return None
continue
c1, c2 = w1[idx], w2[idx]
# we want c1 < c2 after the substitution
adj[ord(c1) - ord('A')].add(ord(c2) - ord('A'))
li = topoSort(N, adj)
sub = {}
for i in range(N):
sub[chr(ord('A') + li[i])] = chr(ord('A') + i)
return sub
def main():
words = ['PINEAPPLE', 'BANANA', 'ARTICHOKE', 'TOMATO']
print('Before: ' + ' '.join(words))
sub = solve(words)
nwords = [''.join(sub[c] for c in w) for w in words]
print('After : ' + ' '.join(nwords))
if __name__ == '__main__':
main()
编辑：这个解决方案的时间复杂度是可证明的最优 O(S)，其中 S 是输入的长度。为此感谢 suspicious dog；原来的时间复杂度是O(N^2 L).
考虑以下词语：
PINEAPPLE
BANANA
ARTICHOKE
TOMATO
目标是在不移动单词本身的情况下对其进行排序（按字典顺序），而是使用字母替换。在这个例子中，我可以把字母P换成A，A换成P，所以：
AINEPAALE
BPNPNP
PRTICHOKE
TOMPTO
这是一个按字典顺序排列的列表。如果你切换字母，字母将在所有单词中切换。值得注意的是，您可以使用整个字母表，只使用列表中单词中的字母。
我花了相当多的时间来解决这个问题，但除了暴力破解（尝试所有字母开关组合）之外我想不出任何其他办法，也无法想出定义 的条件当列表可以排序时.
更多示例：
ABC
ABB
ABD
可以变成
ACB
ACC
ACD
满足条件
- 提取列表中每个单词的所有首字母。 (P,B,A,T)
- 对列表进行排序。 (A,B,P,T)
- 将单词中出现的所有第一个字母替换为排序列表中的第一个字符。
将所有单词中的 P(Pineapple) 替换为 A.
将所有单词中的 B 替换为 B。
将所有单词中的 A 替换为 P。
将所有单词中的 T 替换为 T。
这将为您提供预期的结果。
编辑：
- 比较两个相邻的字符串。如果一个 比另一个大，则找到第一次出现的字符不匹配并交换并用交换后的字符替换所有单词。
- 像冒泡排序一样对整个列表重复此操作。
例子-
ABC < ABB
第一个字符不匹配出现在第 3 个位置。所以我们用 B 交换所有 C。
更新： 最初的分析是错误的，并且在一些 class 的测试用例上失败了，正如
我相信这可以用 topological sort 的形式解决。您的初始单词列表定义了某组字母的偏序或有向图。您希望找到一个替代品来线性化这个字母图。让我们使用您的一个重要示例：
P A R K O V I S T E
P A R A D O N T O Z A
P A D A K
A B B A
A B E C E D A
A B S I N T
让x <* y表示substitution(x) < substitution(y)一些字母（或单词）x和y。我们想要整体word1 <* word2 <* word3 <* word4 <* word5 <* word6，但是在字母方面，我们只需要查看每对相邻的单词并找到同一列中的第一对不同字符：
K <* A (from PAR[K]OVISTE <* PAR[A]DONTOZA)
R <* D (from PA[R]ADONTOZA <* PA[D]AK)
P <* A (from [P]ADAK <* [A]BBA)
B <* E (from AB[B]A <* AB[E]CEDA)
E <* S (from AB[E]CEDA <* AB[S]INT)
如果我们没有发现不匹配的字母，那么有 3 种情况：
- 单词 1 和单词 2 相同
- 单词 1 是单词 2 的前缀
- 单词 2 是单词 1 的前缀
在情况 1 和情况 2 中，单词已经按字典顺序排列，因此我们不需要执行任何替换（尽管我们可能会这样做）并且它们不会添加我们需要遵守的额外限制。在情况 3 中，根本没有替代方法可以解决这个问题（想想 ["DOGGO", "DOG"]），所以没有可能的解决方案，我们可以提前退出。
否则，我们根据得到的偏序信息构建对应的有向图，并进行拓扑排序。如果排序过程表明不可能进行线性化，那么就没有对单词列表进行排序的解决方案。否则，你会得到类似的东西：
P <* K <* R <* B <* E <* A <* D <* S
根据您实现拓扑排序的方式，您可能会得到不同的线性排序。现在您只需要为每个字母分配一个符合此顺序且本身按字母顺序排序的替换。一个简单的选择是将线性顺序与按字母顺序排序的自身配对，并将其用作替代：
P <* K <* R <* B <* E <* A <* D <* S
| | | | | | | |
A < B < D < E < K < P < R < S
但如果您愿意，可以实施不同的替换规则。
这是 Python 中的概念验证：
import collections
import itertools
# a pair of outgoing and incoming edges
Edges = collections.namedtuple('Edges', 'outgoing incoming')
# a mapping from nodes to edges
Graph = lambda: collections.defaultdict(lambda: Edges(set(), set()))
def substitution_sort(words):
graph = build_graph(words)
if graph is None:
return None
ordering = toposort(graph)
if ordering is None:
return None
# create a substitition that respects `ordering`
substitutions = dict(zip(ordering, sorted(ordering)))
# apply substititions
return [
''.join(substitutions.get(char, char) for char in word)
for word in words
]
def build_graph(words):
graph = Graph()
# loop over every pair of adjacent words and find the first
# pair of corresponding characters where they differ
for word1, word2 in zip(words, words[1:]):
for char1, char2 in zip(word1, word2):
if char1 != char2:
break
else: # no differing characters found...
if len(word1) > len(word2):
# ...but word2 is a prefix of word1 and comes after;
# therefore, no solution is possible
return None
else:
# ...so no new information to add to the graph
continue
# add edge from char1 -> char2 to the graph
graph[char1].outgoing.add(char2)
graph[char2].incoming.add(char1)
return graph
def toposort(graph):
"Kahn's algorithm; returns None if graph contains a cycle"
result = []
working_set = {node for node, edges in graph.items() if not edges.incoming}
while working_set:
node = working_set.pop()
result.append(node)
outgoing = graph[node].outgoing
while outgoing:
neighbour = outgoing.pop()
neighbour_incoming = graph[neighbour].incoming
neighbour_incoming.remove(node)
if not neighbour_incoming:
working_set.add(neighbour)
if any(edges.incoming or edges.outgoing for edges in graph.values()):
return None
else:
return result
def print_all(items):
for item in items:
print(item)
print()
def test():
test_cases = [
('PINEAPPLE BANANA ARTICHOKE TOMATO', True),
('ABC ABB ABD', True),
('AB AA AB', False),
('PARKOVISTE PARADONTOZA PADAK ABBA ABECEDA ABSINT', True),
('AA AB CA', True),
('DOG DOGGO DOG DIG BAT BAD', False),
('DOG DOG DOGGO DIG BIG BAD', True),
]
for words, is_sortable in test_cases:
words = words.split()
print_all(words)
subbed = substitution_sort(words)
if subbed is not None:
assert subbed == sorted(subbed), subbed
print_all(subbed)
else:
print('<no solution>')
print()
print('expected solution?', 'yes' if is_sortable else 'no')
print()
if __name__ == '__main__':
test()
现在，它并不理想——例如，即使原始单词列表已经排序，它仍然执行替换——但它似乎可以工作。虽然我无法正式证明它有效，所以如果你找到反例，请告诉我！
让我们暂时假设特定情况下可能会出现该问题。此外，为简单起见，假设所有单词都是不同的（如果两个单词相同，则它们必须相邻并且可以忽略一个）。
然后问题变成了拓扑排序，虽然细节和可疑狗的答案略有不同，遗漏了一些情况。
考虑一个包含 26 个节点的图，标记为 A 到 Z。每对单词为偏序贡献一个有向边；这对应于单词不同的第一个字符。例如，ABCEF和ABRKS这两个词的顺序，第一个不同的是第三个字符，所以sigma(C) < sigma(R)。
结果可以通过对该图进行拓扑排序，并将排序中的第一个节点替换为 A，第二个节点替换为 B，依此类推。
请注意，这也提供了一个有用的衡量方法，可以衡量问题何时无法解决。当两个词相同但不相邻（在 "cluster" 中），当一个词是另一个词的前缀但在它之后，或者当图有一个循环并且拓扑排序是不可能的时候，就会发生这种情况。
这里是 Python 中的一个功能齐全的解决方案，包括检测何时无法解决问题的特定实例。
def topoSort(N, adj):
stack = []
visited = [False for _ in range(N)]
current = [False for _ in range(N)]
def dfs(v):
if current[v]: return False # there's a cycle!
if visited[v]: return True
visited[v] = current[v] = True
for x in adj[v]:
if not dfs(x):
return False
current[v] = False
stack.append(v)
return True
for i in range(N):
if not visited[i]:
if not dfs(i):
return None
return list(reversed(stack))
def solve(wordlist):
N = 26
adj = [set([]) for _ in range(N)] # adjacency list
for w1, w2 in zip(wordlist[:-1], wordlist[1:]):
idx = 0
while idx < len(w1) and idx < len(w2):
if w1[idx] != w2[idx]: break
idx += 1
else:
# no differences found between the words
if len(w1) > len(w2):
return None
continue
c1, c2 = w1[idx], w2[idx]
# we want c1 < c2 after the substitution
adj[ord(c1) - ord('A')].add(ord(c2) - ord('A'))
li = topoSort(N, adj)
sub = {}
for i in range(N):
sub[chr(ord('A') + li[i])] = chr(ord('A') + i)
return sub
def main():
words = ['PINEAPPLE', 'BANANA', 'ARTICHOKE', 'TOMATO']
print('Before: ' + ' '.join(words))
sub = solve(words)
nwords = [''.join(sub[c] for c in w) for w in words]
print('After : ' + ' '.join(nwords))
if __name__ == '__main__':
main()
编辑：这个解决方案的时间复杂度是可证明的最优 O(S)，其中 S 是输入的长度。为此感谢 suspicious dog；原来的时间复杂度是O(N^2 L).