Alien Dictionary

请问有大神可以解释一下alien dictionary怎么找所有可能的排序吗？看地里都是说用backtracking，可是小弟我还是不太理解



补充内容 (2019-9-27 01:59):
alien dictionary all possible orderingy

zhimingli123 发表于 2019-9-27 00:00
比如 [a, bc, d], 就得返回 abdc, abcd, acbd, abcd. 这都是可能也valid的order，怎么样才可以把这些都找 ..

1. import collections
   
2. def alienOrder(words):
   
3.     g = collections.defaultdict(set)
   
4.     ind = collections.defaultdict(int)
   
5.    
   
6.     for i in range(1, len(words)):
   
7.         for j in range(min(len(words[i-1]), len(words[i]))):
   
8.             if words[i-1][j] != words[i][j]:
   
9.                 g[words[i-1][j]].add(words[i][j])
   
10.                 ind[words[i][j]] += 1
    
11.                 break
    
12.     start = []
    
13.     res = []
    
14.     char_set = set("".join(w for w in words))
    
15.     for c in char_set:
    
16.         if ind[c] == 0:
    
17.             start.append(c)
    
18. 
    
19.     def dfs(usable, indegree, path):
    
20.         if not usable:
    
21.             if len(path) == len(char_set):
    
22.                 res.append(path)
    
23.             return
    
24.         for i in range(len(usable)):
    
25.             cur = usable[i]
    
26.             tmp = dict(indegree)
    
27.             new_usable = []
    
28.             for nei in g[cur]:
    
29.                 tmp[nei] -= 1
    
30.                 if tmp[nei] == 0:
    
31.                     new_usable.append(nei)
    
32.             dfs(usable[:i] + usable[i+1:] + new_usable, tmp, path + cur)
    
33. 
    
34.     dfs(start, ind ,"")        
    
35.     return res
    
36. 
    
37. print(alienOrder(["wrt","wrf","er","ett","rftt"])) #['wertf']
    
38. print(alienOrder(["a", "bc", "d"])) #['acbd', 'abcd', 'abdc', 'cabd']
    
39. print(alienOrder(["yx", "yz"])) #['xyz', 'xzy', 'yxz']

复制代码

这样？

这个问题数学上称作“偏序集的线性扩展”（Linear Extensions of Partial Order Set），参考这里：http://mathworld.wolfram.com/LinearExtension.html

首先问题本身是#P-complete的，时间复杂度与所生成的order数量有关，而最坏情况下order数量是指数级的

但是仍然有办法区分在这个问题上一些算法的好坏，就是给定一个输入，记不同字符的个数为K，记最终生成的全部order数量为 N

那么有三种级别的算法：

(1) Naive方法：基于Kahn拓扑排序算法改一改，时间复杂度 K^2 * N

（我在下面写了一份naive方法的代码..）

(2) An Algorithm to Generate All Topological Sorting Arrangement：思想类似于非递归生成全排序的Heap算法，时间复杂度 K * N

(3) Generating Linear Extensions Fast：号称时间复杂度为 常数 * N

----

Naive方法代码：

1. import java.util.ArrayList;
   
2. import java.util.HashMap;
   
3. import java.util.HashSet;
   
4. import java.util.StringJoiner;
   
5. 
   
6. class AlienDictionary {
   
7.   // 有向图
   
8.   private HashSet<Character> vertices = new HashSet<>();
   
9.   private HashMap<Character, HashSet<Character>> edges = new HashMap<>();
   
10. 
    
11.   // 枚举拓扑序时使用的数据结构
    
12.   char[] topologyOrder;
    
13.   ArrayList<String> topologyOrderList;
    
14.   boolean[] isVisited;
    
15.   int[] indegrees;
    
16.   
    
17.   public void AddVertex(char vertex) {
    
18.     vertices.add(vertex);
    
19.     edges.computeIfAbsent(vertex, k -> new HashSet<>());
    
20.   }
    
21.   
    
22.   public void AddEdge(char src, char dst) {
    
23.     edges.get(src).add(dst);
    
24.   }
    
25.   
    
26.   public ArrayList<String> EnumerateTopologyOrder() {
    
27.     // 枚举拓扑序时使用的数据结构
    
28.     topologyOrder = new char[vertices.size()];
    
29.     topologyOrderList = new ArrayList<>();
    
30.     isVisited = new boolean[256];
    
31.     indegrees = new int[256];
    
32. 
    
33.     // 初始化 indegrees
    
34.     for (char vertex : vertices) {
    
35.       for (char neighbor : edges.get(vertex)) {
    
36.         ++indegrees[(int)neighbor];
    
37.       }
    
38.     }
    
39.    
    
40.     // 开始递归枚举
    
41.     for (char v : vertices) {
    
42.       if (indegrees[(int)v] == 0) {
    
43.         EnumerateTopologyOrderInternal(0, v);
    
44.       }
    
45.     }
    
46.     return topologyOrderList;
    
47.   }
    
48.   
    
49.   private void EnumerateTopologyOrderInternal(int index, char vertex) {
    
50.     topologyOrder[index++] = vertex;
    
51.     if (index == vertices.size()) {
    
52.       StringJoiner sj = new StringJoiner(" < ");
    
53.       for (char c : topologyOrder) {
    
54.         sj.add(String.valueOf(c));
    
55.       }
    
56.       topologyOrderList.add(sj.toString());
    
57.       return;
    
58.     }
    
59.     for (char neighbor : edges.get(vertex)) {
    
60.       --indegrees[(int)neighbor];      
    
61.     }
    
62.     isVisited[(int)vertex] = true;
    
63.     for (char candidate : vertices) {
    
64.       if (!isVisited[(int)candidate] && indegrees[(int)candidate] == 0) {
    
65.         EnumerateTopologyOrderInternal(index, candidate);
    
66.       }
    
67.     }
    
68.     isVisited[(int)vertex] = false;
    
69.     for (char neighbor : edges.get(vertex)) {
    
70.       ++indegrees[(int)neighbor];      
    
71.     }
    
72.   }
    
73. }
    
74. 
    
75. 
    
76. public class Main {
    
77.   private static int FindFirstDiffPos(String lhs, String rhs) {
    
78.     for (int i = 0; i < Math.min(lhs.length(), rhs.length()); ++i) {
    
79.       if (lhs.charAt(i) != rhs.charAt(i)) {
    
80.         return i;
    
81.       }
    
82.     }
    
83.     return -1;
    
84.   }
    
85.   
    
86.   public static AlienDictionary CreateAlienDictionary(String[] words) {
    
87.     AlienDictionary dict = new AlienDictionary();
    
88.     if (words.length == 0) {
    
89.       return dict;
    
90.     }
    
91.     for (char c : words[0].toCharArray()) {
    
92.       dict.AddVertex(c);
    
93.     }   
    
94.     for (int i = 1; i < words.length; ++i) {
    
95.       for (char c : words[i].toCharArray()) {
    
96.         dict.AddVertex(c);
    
97.       }
    
98.       int pos = FindFirstDiffPos(words[i-1], words[i]);
    
99.       if (pos >= 0) {
    
100.         dict.AddEdge(words[i-1].charAt(pos), words[i].charAt(pos));
     
101.       }
     
102.     }
     
103.     return dict;
     
104.   }  
     
105.   
     
106.   public static void main(String[] args) {
     
107.     AlienDictionary dict = CreateAlienDictionary(
     
108.         new String[] {
     
109.             "a",
     
110.             "b",
     
111.             "cd",
     
112.             "cdb",
     
113.             "cde",
     
114.         });
     
115. 
     
116.     for (String order : dict.EnumerateTopologyOrder()) {
     
117.       System.out.println(order);
     
118.     }
     
119.    
     
120.     // 输出 (注意到输入里面d与其他字符不存在任何偏序关系，所以d可以出现在任何地方):
     
121.     //
     
122.     // a < b < c < d < e
     
123.     // a < b < c < e < d
     
124.     // a < b < d < c < e
     
125.     // a < b < d < e < c
     
126.     // a < b < e < c < d
     
127.     // a < b < e < d < c
     
128.     // a < d < b < c < e
     
129.     // a < d < b < e < c
     
130.     // d < a < b < c < e
     
131.     // d < a < b < e < c
     
132.   }  
     
133. }
     

复制代码

[/i][/i][/i]

这题是topological sort吧..先把dictionary扫一遍用Map先得到topological ordering，然后从indegree为0的character开始进行BFS就行了...看看discussion, 都挺清楚的

nyubladestealth 发表于 2019/09/27 09:30:33
这题是topological sort吧..先把dictionary扫一遍用Map先得到topological ordering，然后从indegree为0的character开始进行BFS就行了.....

可是没有详细说找所有possible ordering的，你这个方法只是basic的求一个possibility的吧

字典不给你全部排序你怎么求？ 他给你什么就是什么了。。

337845818 发表于 2019/09/27 12:21:49
字典不给你全部排序你怎么求？ 他给你什么就是什么了。。

比如 [a, bc, d], 就得返回 abdc, abcd, acbd, abcd. 这都是可能也valid的order，怎么样才可以把这些都找出来，不只是return一个valid的