散列 [1,9] 有序排列的最佳方法
Best way to hash ordered permutation of [1,9]
我正在尝试实现一种方法来防止再次生成 8 拼图的访问状态。
我最初的方法是将每个访问过的模式保存在一个列表中，并在每次算法想要生成子节点时进行线性检查。
现在我想通过列表访问在 O(1) 时间内完成此操作。 8 拼图中的每个模式都是 1 到 9 之间数字的有序排列（9 是空白块），例如 125346987 是：
1 2 5
3 4 6
_ 8 7
这种所有可能排列的数量约为 363,000（9！）。将这些数字散列到该大小列表的索引的最佳方法是什么？
看起来你只对你是否已经访问过排列感兴趣。
你应该使用 set。它授予您感兴趣的 O(1) look-up。
您可以将 N 项的排列映射到其在 N 项的所有排列列表（按字典顺序排列）中的索引。
下面是执行此操作的一些代码，以及它为 4 字母序列的所有排列分别生成一次索引 0 到 23 的演示。
import itertools
def fact(n):
r = 1
for i in xrange(n):
r *= i + 1
return r
def I(perm):
if len(perm) == 1:
return 0
return sum(p < perm[0] for p in perm) * fact(len(perm) - 1) + I(perm[1:])
for p in itertools.permutations('abcd'):
print p, I(p)
理解代码的最好方法是证明其正确性。对于长度为 n 的数组，有 (n-1)！数组中最小元素最先出现的排列，(n-1)！第二小的元素首先出现的排列，依此类推。
因此，要找到给定排列的索引，请计算有多少项小于排列中的第一项，然后将其乘以 (n-1)!。然后递归地添加排列的剩余部分的索引，被认为是（n-1）个元素的排列。基本情况是当你有一个长度为 1 的排列时。显然只有一个这样的排列，所以它的索引是 0.
一个有效的例子：[1324].
[1324]：首先出现 1，这是数组中的最小元素，因此给出 0 * (3!)- 删除 1 得到
[324]。第一个元素是 3。有一个元素更小，因此我们得到 1 * (2!).
- 删除 3 得到
[24]。第一个元素是 2。这是剩余的最小元素，因此我们得到 0 * (1!).
- 删除 2 得到
[4]。只有一个元素，所以我们使用基本情况并得到 0。
相加得到0*3！ + 1*2！ + 0*1！ + 0 = 1*2！ = 2。因此 [1324] 在 4 个排列的排序列表中位于索引 2。这是正确的，因为在索引 0 处是 [1234]，索引 1 是 [1243]，并且字典顺序的下一个排列是我们的 [1324].
请注意，如果您键入 hash(125346987)，它会 returns 125346987。这是有原因的，因为将整数散列为整数以外的任何值都没有意义。
你应该做的是，当你找到一个模式时，将它添加到字典而不是列表中。这将提供您需要的快速查找，而不是像现在这样遍历列表。
假设您找到了模式 125346987，您可以这样做：
foundPatterns = {}
#some code to find the pattern
foundPatterns[1] = 125346987
#more code
#test if there?
125346987 in foundPatterns.values()
True
如果您必须总是有O(1)，那么位数组似乎可以完成这项工作。您只需要存储 363,000 个元素，这似乎是可行的。但请注意，在实践中它并不总是更快。最简单的实现如下：
创建数据结构
visited_bitset = [False for _ in xrange(373000)]
测试当前状态，如果还没有访问则添加
if !visited[current_state]:
visited_bitset[current_state] = True
我相信您需要一个函数来将排列映射到数组索引。这本字典将数字 1-9 的所有排列映射到 0 到 9 的值！-1。
import itertools
index = itertools.count(0)
permutations = itertools.permutations(range(1, 10))
hashes = {h:next(index) for h in permutations}
例如，哈希 [(1,2,5,3,4,6,9,8,7)] 给出的值为 1445。
如果您需要在字符串而不是元组中使用它们，请使用：
permutations = [''.join(x) for x in itertools.permutations('123456789')]
或作为整数：
permutations = [int(''.join(x)) for x in itertools.permutations('123456789')]
保罗的 可能有效。
Elisha 的 是完全有效的散列函数，可以保证散列函数中不会发生冲突。 9! 将是保证无冲突哈希函数的纯粹最小值，但是（除非有人纠正我，Paul 可能有）我不相信存在将每个板映射到域中的值的函数 [0, 9!]，更不用说哈希函数了O(1).
如果您有 1GB 的内存来支持 864197532（又名 987654321-12346789）索引的布尔数组。您保证（计算上）O(1) 要求。
实际上（意思是当你在真实系统中 运行 时）说这不是缓存友好的，但在理论上这个解决方案肯定会起作用。即使确实存在一个完美的函数，也怀疑它是否对缓存友好。
使用像 set 或 hashmap 这样的预构建（对不起，我有一段时间没有编程 Python，所以不记得数据类型）必须有一个摊销 0(1).但是，将其中之一与 n % RANDOM_PRIME_NUM_GREATER_THAN_100000 等次优哈希函数一起使用可能会提供最佳解决方案。
首先。 没有什么比布尔值列表更快的了。您的任务总共有 9! == 362880 种可能的排列，这是要存储在内存中的相当少量的数据：
visited_states = [False] * math.factorial(9)
或者，您可以使用 array 字节，它稍微慢一些（虽然不是很多）并且内存占用要低得多（至少是数量级）。但是，考虑到下一步，使用数组节省的任何内存可能价值不大。
其次。 您需要将您的特定排列转换为它的索引。有一些算法可以做到这一点，关于这个主题的最好的 Whosebug 问题之一可能是这个：
Finding the index of a given permutation
你有固定的排列大小n == 9，所以无论算法有多复杂，在你的情况下它都等同于 O(1)。
然而，为了产生更快的结果，您可以 pre-populate 一个映射字典，它将为您提供 O(1) 查找：
all_permutations = map(lambda p: ''.join(p), itertools.permutations('123456789'))
permutation_index = dict((perm, index) for index, perm in enumerate(all_permutations))
这本词典将消耗大约 50 Mb 的内存，这...实际上并没有那么多。特别是因为您只需要创建一次。
完成所有这些后，检查您的特定组合是通过以下方式完成的：
visited = visited_states[permutation_index['168249357']]
以相同的方式将其标记为已访问：
visited_states[permutation_index['168249357']] = True
请注意，使用任何置换索引算法都会比映射字典慢得多。这些算法中的大多数都具有 O(n2) 复杂性，在您的情况下，即使不考虑额外的 python 代码本身，它的性能也会降低 81 倍。因此，除非您有严重的内存限制，否则使用映射字典可能是最好的解决方案 speed-wise.
附录。 正如 Palec 所指出的，实际上根本不需要 visited_states 列表 - 完全可以存储 True/False 直接在 permutation_index 字典中的值，这节省了一些内存和额外的列表查找。
使用
我已经为这个特定案例开发了一个启发式函数。它不是完美的散列，因为映射不在 [0,9!-1] 之间，而是在 [1,767359] 之间，但它是 O(1).
假设我们已经有一个文件/保留内存/767359 位设置为 0 的任何内容（例如，mem = [False] * 767359）。让 8puzzle 模式映射到 python 字符串（例如，'125346987'）。然后，哈希函数由：
def getPosition( input_str ):
data = []
opts = range(1,10)
n = int(input_str[0])
opts.pop(opts.index(n))
for c in input_str[1:len(input_str)-1]:
k = opts.index(int(c))
opts.pop(k)
data.append(k)
ind = data[3]<<14 | data[5]<<12 | data[2]<<9 | data[1]<<6 | data[0]<<3 | data[4]<<1 | data[6]<<0
output_str = str(ind)+str(n)
output = int(output_str)
return output
即，为了检查 8puzzle pattern = 125346987 是否已经被使用，我们需要：
pattern = '125346987'
pos = getPosition(pattern)
used = mem[pos-1] #mem starts in 0, getPosition in 1.
如果使用完美的哈希算法，我们需要 9 个！位来存储布尔值。在这种情况下，我们需要多 2 倍 (767359/9! = 2.11)，但回想一下，它甚至还不到 1Mb（勉强 100KB）。
请注意，该函数很容易反转。
检查
我可以从数学上向您证明为什么这样做有效以及为什么不会发生任何冲突，但由于这是一个编程论坛，所以我们只 运行 它用于每个可能的排列并检查所有哈希值 (位置）确实不同：
def getPosition( input_str ):
data = []
opts = range(1,10)
n = int(input_str[0])
opts.pop(opts.index(n))
for c in input_str[1:len(input_str)-1]:
k = opts.index(int(c))
opts.pop(k)
data.append(k)
ind = data[3]<<14 | data[5]<<12 | data[2]<<9 | data[1]<<6 | data[0]<<3 | data[4]<<1 | data[6]<<0
output_str = str(ind)+str(n)
output = int(output_str)
return output
#CHECKING PURPOSES
def addperm(x,l):
return [ l[0:i] + [x] + l[i:] for i in range(len(l)+1) ]
def perm(l):
if len(l) == 0:
return [[]]
return [x for y in perm(l[1:]) for x in addperm(l[0],y) ]
#We generate all the permutations
all_perms = perm([ i for i in range(1,10)])
print "Number of all possible perms.: "+str(len(all_perms)) #indeed 9! = 362880
#We execute our hash function over all the perms and store the output.
all_positions = [];
for permutation in all_perms:
perm_string = ''.join(map(str,permutation))
all_positions.append(getPosition(perm_string))
#We wan't to check if there has been any collision, i.e., if there
#is one position that is repeated at least twice.
print "Number of different hashes: "+str(len(set(all_positions)))
#also 9!, so the hash works properly.
它是如何工作的？
这背后的想法与一棵树有关：一开始它有 9 个分支到 9 个节点，每个节点对应一个数字。从这些节点中的每一个节点，我们都有 8 个分支到 8 个节点，每个节点对应一个数字，除了它的父节点，然后是 7，依此类推。
我们首先将输入字符串的第一个数字存储在一个单独的变量中，然后将其从 'node' 列表中弹出，因为我们已经采用了与第一个数字对应的分支。
那么我们有8个分支，我们选择与我们的第二个数字对应的那个。请注意，由于有 8 个分支，我们需要 3 位来存储我们选择的分支的索引，并且它可以采用的最大值是 111 对于第 8 个分支（我们将分支 1-8 映射到二进制 000-111).一旦我们选择并存储了分支索引，我们就会将该值弹出，以便下一个节点列表不再包含该数字。
我们以相同的方式处理分支 7、6 和 5。请注意，当我们有 7 个分支时，我们仍然需要 3 位，但最大值将为 110。当我们有 5 个分支时，索引最多为二进制 100.
然后我们得到 4 个分支，我们注意到这可以只用 2 位存储，对于 3 个分支也是如此。对于 2 个分支，我们只需要 1 位，而对于最后一个分支，我们不需要任何位：只有一个分支指向最后一位数字，这将是我们 1-9 原始列表中的剩余数字。
到目前为止，我们所拥有的是：第一个数字存储在一个单独的变量中，以及一个包含 7 个索引的列表，代表分支。前 4 个索引可以用 3bits 表示，后面的 2 个索引可以用 2bits 表示，最后一个索引用 1bits 表示。
想法是以位形式连接所有这些索引以创建更大的数字。由于我们有 17 位，因此这个数字最多为 2^17=131072。现在我们只需将我们存储的第一个数字添加到该数字的末尾（这个数字最多为 9），我们可以创建的最大数字是 1310729.
但我们可以做得更好：回想一下，当我们有 5 个分支时，我们需要 3 位，尽管最大值是二进制 100。如果我们安排我们的位，让那些有更多 0 的人排在第一位会怎么样？如果是这样，在最坏的情况下，我们的最终位数将是以下内容的串联：
100 10 101 110 111 11 1
十进制为76735。然后我们像以前一样进行（在末尾添加 9），我们得到我们可能生成的最大数字是 767359，这是我们需要的位数，对应于输入字符串 987654321，而最小的可能数字是 1 对应于输入字符串 123456789.
即将结束：有人可能想知道为什么我们将第一个数字存储在一个单独的变量中并将其添加到末尾。原因是如果我们保留它那么开始的分支数将是 9，因此为了存储第一个索引 (1-9) 我们将需要 4 位（0000 到 1000).这会使我们的映射效率大大降低，因为在这种情况下，最大可能的数量（以及因此所需的内存量）将是
1000 100 10 101 110 111 11 1
十进制为 1125311（1.13Mb 对 768Kb）。很有趣的是，比率 1.13M/0.768K = 1.47 与四位的比率有关，而不是仅添加一个十进制值 (2^4/10 = 1.6)，这很有意义（差异是由于事实上，使用第一种方法我们没有完全使用 4 位）。
一个 space 以及此问题的查找有效结构是一个 trie 类型的结构，因为它将 使用通用的 space 进行任何词典匹配
排列。
即 space 在 1234 中用于“123”，在 1235 中将相同。
为简单起见，让我们假设 0 替换示例中的“_”。
存储
- 您的 trie 将是一棵布尔树，根节点将是一个空节点，然后每个节点将包含 9 个布尔标志设置为 false 的子节点，这 9 个子节点指定数字 0 到 8 和 _ 。
- 您可以在遇到排列时随时创建 trie，并通过将 bool 设置为 true 将遇到的数字存储为 trie 中的布尔值。
查找
- 根据排列的数字从根节点遍历子节点，如果节点被标记为真，则说明该排列之前发生过。查找的复杂度仅为 9 个节点跳数。
以下是 trie 查找 4 位数示例的方式：
Python 特里
这个 trie 可以很容易地存储在布尔列表中，比如 myList。
其中 myList[0] 是根，如此处的概念所述：
https://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html
列表中的最终 trie 大约为 9+9^2+9^3....9^8 位，即所有查找小于 10 MB。
我正在尝试实现一种方法来防止再次生成 8 拼图的访问状态。
我最初的方法是将每个访问过的模式保存在一个列表中，并在每次算法想要生成子节点时进行线性检查。
现在我想通过列表访问在 O(1) 时间内完成此操作。 8 拼图中的每个模式都是 1 到 9 之间数字的有序排列（9 是空白块），例如 125346987 是：
1 2 5
3 4 6
_ 8 7
这种所有可能排列的数量约为 363,000（9！）。将这些数字散列到该大小列表的索引的最佳方法是什么？
看起来你只对你是否已经访问过排列感兴趣。
你应该使用 set。它授予您感兴趣的 O(1) look-up。
您可以将 N 项的排列映射到其在 N 项的所有排列列表（按字典顺序排列）中的索引。
下面是执行此操作的一些代码，以及它为 4 字母序列的所有排列分别生成一次索引 0 到 23 的演示。
import itertools
def fact(n):
r = 1
for i in xrange(n):
r *= i + 1
return r
def I(perm):
if len(perm) == 1:
return 0
return sum(p < perm[0] for p in perm) * fact(len(perm) - 1) + I(perm[1:])
for p in itertools.permutations('abcd'):
print p, I(p)
理解代码的最好方法是证明其正确性。对于长度为 n 的数组，有 (n-1)！数组中最小元素最先出现的排列，(n-1)！第二小的元素首先出现的排列，依此类推。
因此，要找到给定排列的索引，请计算有多少项小于排列中的第一项，然后将其乘以 (n-1)!。然后递归地添加排列的剩余部分的索引，被认为是（n-1）个元素的排列。基本情况是当你有一个长度为 1 的排列时。显然只有一个这样的排列，所以它的索引是 0.
一个有效的例子：[1324].
[1324]：首先出现 1，这是数组中的最小元素，因此给出 0 * (3!)- 删除 1 得到
[324]。第一个元素是 3。有一个元素更小，因此我们得到 1 * (2!). - 删除 3 得到
[24]。第一个元素是 2。这是剩余的最小元素，因此我们得到 0 * (1!). - 删除 2 得到
[4]。只有一个元素，所以我们使用基本情况并得到 0。
相加得到0*3！ + 1*2！ + 0*1！ + 0 = 1*2！ = 2。因此 [1324] 在 4 个排列的排序列表中位于索引 2。这是正确的，因为在索引 0 处是 [1234]，索引 1 是 [1243]，并且字典顺序的下一个排列是我们的 [1324].
请注意，如果您键入 hash(125346987)，它会 returns 125346987。这是有原因的，因为将整数散列为整数以外的任何值都没有意义。
你应该做的是，当你找到一个模式时，将它添加到字典而不是列表中。这将提供您需要的快速查找，而不是像现在这样遍历列表。
假设您找到了模式 125346987，您可以这样做：
foundPatterns = {}
#some code to find the pattern
foundPatterns[1] = 125346987
#more code
#test if there?
125346987 in foundPatterns.values()
True
如果您必须总是有O(1)，那么位数组似乎可以完成这项工作。您只需要存储 363,000 个元素，这似乎是可行的。但请注意，在实践中它并不总是更快。最简单的实现如下：
创建数据结构
visited_bitset = [False for _ in xrange(373000)]
测试当前状态，如果还没有访问则添加
if !visited[current_state]:
visited_bitset[current_state] = True
我相信您需要一个函数来将排列映射到数组索引。这本字典将数字 1-9 的所有排列映射到 0 到 9 的值！-1。
import itertools
index = itertools.count(0)
permutations = itertools.permutations(range(1, 10))
hashes = {h:next(index) for h in permutations}
例如，哈希 [(1,2,5,3,4,6,9,8,7)] 给出的值为 1445。
如果您需要在字符串而不是元组中使用它们，请使用：
permutations = [''.join(x) for x in itertools.permutations('123456789')]
或作为整数：
permutations = [int(''.join(x)) for x in itertools.permutations('123456789')]
保罗的
Elisha 的9! 将是保证无冲突哈希函数的纯粹最小值，但是（除非有人纠正我，Paul 可能有）我不相信存在将每个板映射到域中的值的函数 [0, 9!]，更不用说哈希函数了O(1).
如果您有 1GB 的内存来支持 864197532（又名 987654321-12346789）索引的布尔数组。您保证（计算上）O(1) 要求。
实际上（意思是当你在真实系统中 运行 时）说这不是缓存友好的，但在理论上这个解决方案肯定会起作用。即使确实存在一个完美的函数，也怀疑它是否对缓存友好。
使用像 set 或 hashmap 这样的预构建（对不起，我有一段时间没有编程 Python，所以不记得数据类型）必须有一个摊销 0(1).但是，将其中之一与 n % RANDOM_PRIME_NUM_GREATER_THAN_100000 等次优哈希函数一起使用可能会提供最佳解决方案。
首先。 没有什么比布尔值列表更快的了。您的任务总共有 9! == 362880 种可能的排列，这是要存储在内存中的相当少量的数据：
visited_states = [False] * math.factorial(9)
或者，您可以使用 array 字节，它稍微慢一些（虽然不是很多）并且内存占用要低得多（至少是数量级）。但是，考虑到下一步，使用数组节省的任何内存可能价值不大。
其次。 您需要将您的特定排列转换为它的索引。有一些算法可以做到这一点，关于这个主题的最好的 Whosebug 问题之一可能是这个：
Finding the index of a given permutation
你有固定的排列大小n == 9，所以无论算法有多复杂，在你的情况下它都等同于 O(1)。
然而，为了产生更快的结果，您可以 pre-populate 一个映射字典，它将为您提供 O(1) 查找：
all_permutations = map(lambda p: ''.join(p), itertools.permutations('123456789'))
permutation_index = dict((perm, index) for index, perm in enumerate(all_permutations))
这本词典将消耗大约 50 Mb 的内存，这...实际上并没有那么多。特别是因为您只需要创建一次。
完成所有这些后，检查您的特定组合是通过以下方式完成的：
visited = visited_states[permutation_index['168249357']]
以相同的方式将其标记为已访问：
visited_states[permutation_index['168249357']] = True
请注意，使用任何置换索引算法都会比映射字典慢得多。这些算法中的大多数都具有 O(n2) 复杂性，在您的情况下，即使不考虑额外的 python 代码本身，它的性能也会降低 81 倍。因此，除非您有严重的内存限制，否则使用映射字典可能是最好的解决方案 speed-wise.
附录。 正如 Palec 所指出的，实际上根本不需要 visited_states 列表 - 完全可以存储 True/False 直接在 permutation_index 字典中的值，这节省了一些内存和额外的列表查找。
使用
我已经为这个特定案例开发了一个启发式函数。它不是完美的散列，因为映射不在 [0,9!-1] 之间，而是在 [1,767359] 之间，但它是 O(1).
假设我们已经有一个文件/保留内存/767359 位设置为 0 的任何内容（例如，mem = [False] * 767359）。让 8puzzle 模式映射到 python 字符串（例如，'125346987'）。然后，哈希函数由：
def getPosition( input_str ):
data = []
opts = range(1,10)
n = int(input_str[0])
opts.pop(opts.index(n))
for c in input_str[1:len(input_str)-1]:
k = opts.index(int(c))
opts.pop(k)
data.append(k)
ind = data[3]<<14 | data[5]<<12 | data[2]<<9 | data[1]<<6 | data[0]<<3 | data[4]<<1 | data[6]<<0
output_str = str(ind)+str(n)
output = int(output_str)
return output
即，为了检查 8puzzle pattern = 125346987 是否已经被使用，我们需要：
pattern = '125346987'
pos = getPosition(pattern)
used = mem[pos-1] #mem starts in 0, getPosition in 1.
如果使用完美的哈希算法，我们需要 9 个！位来存储布尔值。在这种情况下，我们需要多 2 倍 (767359/9! = 2.11)，但回想一下，它甚至还不到 1Mb（勉强 100KB）。
请注意，该函数很容易反转。
检查
我可以从数学上向您证明为什么这样做有效以及为什么不会发生任何冲突，但由于这是一个编程论坛，所以我们只 运行 它用于每个可能的排列并检查所有哈希值 (位置）确实不同：
def getPosition( input_str ):
data = []
opts = range(1,10)
n = int(input_str[0])
opts.pop(opts.index(n))
for c in input_str[1:len(input_str)-1]:
k = opts.index(int(c))
opts.pop(k)
data.append(k)
ind = data[3]<<14 | data[5]<<12 | data[2]<<9 | data[1]<<6 | data[0]<<3 | data[4]<<1 | data[6]<<0
output_str = str(ind)+str(n)
output = int(output_str)
return output
#CHECKING PURPOSES
def addperm(x,l):
return [ l[0:i] + [x] + l[i:] for i in range(len(l)+1) ]
def perm(l):
if len(l) == 0:
return [[]]
return [x for y in perm(l[1:]) for x in addperm(l[0],y) ]
#We generate all the permutations
all_perms = perm([ i for i in range(1,10)])
print "Number of all possible perms.: "+str(len(all_perms)) #indeed 9! = 362880
#We execute our hash function over all the perms and store the output.
all_positions = [];
for permutation in all_perms:
perm_string = ''.join(map(str,permutation))
all_positions.append(getPosition(perm_string))
#We wan't to check if there has been any collision, i.e., if there
#is one position that is repeated at least twice.
print "Number of different hashes: "+str(len(set(all_positions)))
#also 9!, so the hash works properly.
它是如何工作的？
这背后的想法与一棵树有关：一开始它有 9 个分支到 9 个节点，每个节点对应一个数字。从这些节点中的每一个节点，我们都有 8 个分支到 8 个节点，每个节点对应一个数字，除了它的父节点，然后是 7，依此类推。
我们首先将输入字符串的第一个数字存储在一个单独的变量中，然后将其从 'node' 列表中弹出，因为我们已经采用了与第一个数字对应的分支。
那么我们有8个分支，我们选择与我们的第二个数字对应的那个。请注意，由于有 8 个分支，我们需要 3 位来存储我们选择的分支的索引，并且它可以采用的最大值是 111 对于第 8 个分支（我们将分支 1-8 映射到二进制 000-111).一旦我们选择并存储了分支索引，我们就会将该值弹出，以便下一个节点列表不再包含该数字。
我们以相同的方式处理分支 7、6 和 5。请注意，当我们有 7 个分支时，我们仍然需要 3 位，但最大值将为 110。当我们有 5 个分支时，索引最多为二进制 100.
然后我们得到 4 个分支，我们注意到这可以只用 2 位存储，对于 3 个分支也是如此。对于 2 个分支，我们只需要 1 位，而对于最后一个分支，我们不需要任何位：只有一个分支指向最后一位数字，这将是我们 1-9 原始列表中的剩余数字。
到目前为止，我们所拥有的是：第一个数字存储在一个单独的变量中，以及一个包含 7 个索引的列表，代表分支。前 4 个索引可以用 3bits 表示，后面的 2 个索引可以用 2bits 表示，最后一个索引用 1bits 表示。
想法是以位形式连接所有这些索引以创建更大的数字。由于我们有 17 位，因此这个数字最多为 2^17=131072。现在我们只需将我们存储的第一个数字添加到该数字的末尾（这个数字最多为 9），我们可以创建的最大数字是 1310729.
但我们可以做得更好：回想一下，当我们有 5 个分支时，我们需要 3 位，尽管最大值是二进制 100。如果我们安排我们的位，让那些有更多 0 的人排在第一位会怎么样？如果是这样，在最坏的情况下，我们的最终位数将是以下内容的串联：
100 10 101 110 111 11 1
十进制为76735。然后我们像以前一样进行（在末尾添加 9），我们得到我们可能生成的最大数字是 767359，这是我们需要的位数，对应于输入字符串 987654321，而最小的可能数字是 1 对应于输入字符串 123456789.
即将结束：有人可能想知道为什么我们将第一个数字存储在一个单独的变量中并将其添加到末尾。原因是如果我们保留它那么开始的分支数将是 9，因此为了存储第一个索引 (1-9) 我们将需要 4 位（0000 到 1000).这会使我们的映射效率大大降低，因为在这种情况下，最大可能的数量（以及因此所需的内存量）将是
1000 100 10 101 110 111 11 1
十进制为 1125311（1.13Mb 对 768Kb）。很有趣的是，比率 1.13M/0.768K = 1.47 与四位的比率有关，而不是仅添加一个十进制值 (2^4/10 = 1.6)，这很有意义（差异是由于事实上，使用第一种方法我们没有完全使用 4 位）。
一个 space 以及此问题的查找有效结构是一个 trie 类型的结构，因为它将 使用通用的 space 进行任何词典匹配 排列。 即 space 在 1234 中用于“123”，在 1235 中将相同。
为简单起见，让我们假设 0 替换示例中的“_”。
存储
- 您的 trie 将是一棵布尔树，根节点将是一个空节点，然后每个节点将包含 9 个布尔标志设置为 false 的子节点，这 9 个子节点指定数字 0 到 8 和 _ 。
- 您可以在遇到排列时随时创建 trie，并通过将 bool 设置为 true 将遇到的数字存储为 trie 中的布尔值。
查找
- 根据排列的数字从根节点遍历子节点，如果节点被标记为真，则说明该排列之前发生过。查找的复杂度仅为 9 个节点跳数。
以下是 trie 查找 4 位数示例的方式：
Python 特里 这个 trie 可以很容易地存储在布尔列表中，比如 myList。 其中 myList[0] 是根，如此处的概念所述：
https://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html
列表中的最终 trie 大约为 9+9^2+9^3....9^8 位，即所有查找小于 10 MB。