3

我正在尝试实现一种方法来防止再次生成 8 个拼图的已访问状态。
我最初的方法是将每个访问过的模式保存在一个列表中，并在每次算法想要生成一个孩子时进行线性检查。
现在我想O(1)通过列表访问及时做到这一点。8 拼图中的每个模式都是 1 到 9 之间数字的有序排列（9 是空白块），例如 125346987 是：

1 2 5
3 4 6
_ 8 7

此类所有可能排列的数量约为 363,000（9！）。将这些数字散列到该大小列表的索引的最佳方法是什么？

4

9 回答 9

7

您可以将 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]，并且按字典顺序排列的下一个排列是 our [1324]。

于 2015-12-29T13:23:35.353 回答
2

我相信您正在要求一个将排列映射到数组索引的函数。该字典将数字 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')]
于 2016-01-05T21:08:55.453 回答
1

看起来您只对您是否已经访问过排列感兴趣。

您应该使用set. 它授予O(1)您感兴趣的查找。

于 2015-12-29T12:27:10.397 回答
1

采用

我为这种特定情况开发了一个启发式函数。这不是一个完美的散列，因为映射不是在 之间[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！位来存储布尔值。在这种情况下，我们需要多 2767359/9! = 2.11倍（

请注意，该函数很容易可逆。

查看

我可以从数学上证明为什么它有效以及为什么不会发生任何冲突，但由于这是一个编程论坛，让我们针对所有可能的排列运行它并检查所有哈希值（位置）是否确实不同：

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，依此类推。

我们首先将输入字符串的第一个数字存储在一个单独的变量中，然后将其从“节点”列表中弹出，因为我们已经获取了与第一个数字对应的分支。

然后我们有8个分支，我们选择与我们的第二个数字对应的一个。请注意，由于有 8 个分支，我们需要 3 位来存储我们选择的分支的索引，它可以采用的最大值是111第 8 个分支（我们将分支 1-8 映射到 binary 000-111）。一旦我们选择并存储了分支索引，我们就会弹出该值，以便下一个节点列表不再包含该数字。

我们以相同的方式处理分支 7、6 和 5。请注意，当我们有 7 个分支时，我们仍然需要 3 位，尽管最大值将为110。当我们有 5 个分支时，索引最多为 binary 100。

然后我们得到 4 个分支，我们注意到这可以只用 2 位存储，对于 3 个分支也是如此。对于 2 个分支，我们只需要 1 位，而对于最后一个分支，我们不需要任何位：只有一个分支指向最后一位，这将是我们 1-9 原始列表中的剩余部分。

所以，到目前为止，我们所拥有的：存储在单独变量中的第一个数字和代表分支的 7 个索引的列表。前4个索引可以用3bit表示，后面2个索引可以用2bit表示，最后一个索引用1bit表示。

这个想法是以位形式连接所有这些索引以创建更大的数字。由于我们有 17 位，所以这个数字最多为2^17=131072. 现在我们只需将我们存储的第一个数字添加到该数字的末尾（这个数字最多为 9），我们可以创建的最大数字是1310729.

但我们可以做得更好：回想一下，当我们有 5 个分支时，我们需要 3 位，尽管最大值是 binary 100。如果我们安排我们的位，让那些有更多 0 的位在前呢？如果是这样，在最坏的情况下，我们的最终位数将是：

100 10 101 110 111 11 1

十进制是76735. 然后我们像以前一样继续（在末尾添加 9），我们得到我们可能生成的最大数字是767359，这是我们需要的位数，对应于输入 string 987654321，而最小可能的数字是1对应于输入 string 123456789。

刚刚结束：有人可能想知道为什么我们将第一个数字存储在一个单独的变量中并在最后添加它。原因是如果我们保留它，那么开头的分支数将是 9，因此为了存储第一个索引 (1-9)，我们将需要 4 位 ( 0000to 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 位）。

于 2016-01-07T08:23:44.467 回答
1

对于这个问题，空间以及查找有效的结构是 trie 类型的结构，因为它将在任何排列中使用公共空间来进行字典匹配。即在 1234 和 1235 中用于“123”的空间将是相同的。

为简单起见，让我们假设 0 在您的示例中替换 '_'。

存储

  • 您的 trie 将是一棵布尔树，根节点将是一个空节点，然后每个节点将包含 9 个子节点，布尔标志设置为 false，9 个子节点指定数字 0 到 8 和 _ 。
  • 您可以在遇到排列时随时创建 trie，并将遇到的数字作为布尔值存储在 trie 中，方法是将 bool 设置为 true。

抬头

  • 根据排列的位数从根遍历到子树，如果节点被标记为真，则表示排列已经发生过。查找的复杂度只有 9 个节点跳。

以下是 trie 查找 4 位示例的方式：

在此处输入图像描述

Python trie 这个 trie 可以很容易地存储在一个布尔值列表中，比如 myList。其中 myList[0] 是根，如此处的概念所述：

https://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html

列表中的最终尝试将是大约 9+9^2+9^3....9^8 位，即所有查找都小于 10 MB。

于 2016-01-07T08:50:33.663 回答
0

请注意，如果您键入 hash(125346987)，它会返回 125346987。这是有原因的，因为将整数散列到除整数之外的任何值都没有意义。

您应该做的是，当您找到一个模式时，将其添加到字典而不是列表中。这将提供您需要的快速查找，而不是像现在这样遍历列表。

所以说你找到了你可以做的模式 125346987：

foundPatterns = {}
#some code to find the pattern
foundPatterns[1] = 125346987
#more code
#test if there?
125346987 in foundPatterns.values()
True
于 2016-01-02T19:31:57.693 回答
0

如果您必须始终拥有O(1)，那么似乎位数组可以完成这项工作。您只需要存储 363,000 个元素，这似乎是可行的。尽管请注意，在实践中它并不总是更快。最简单的实现如下所示：

创建数据结构

visited_bitset = [False for _ in xrange(373000)]

测试当前状态并添加如果尚未访问

if !visited[current_state]:
    visited_bitset[current_state] = True
于 2016-01-02T23:19:03.497 回答
0

保罗的回答可能会奏效。

Elisha 的答案是完全有效的散列函数，可以保证散列函数中不会发生冲突。这9!将是保证无冲突哈希函数的纯粹最小值，但是（除非有人纠正我，保罗可能有）我不相信存在将每个板映射到域中的值的[0, 9!]函数，更不用说哈希函数了仅此而已O(1)。

如果您有 1GB 的内存来支持 864197532（又名 987654321-12346789）索引的布尔数组。您保证（计算）O(1)要求。

实际上（意味着当您在真实系统中运行时）说这不会对缓存友好，但在纸面上这个解决方案肯定会起作用。即使确实存在完美的功能，也怀疑它是否也是缓存友好的。

set使用类似or的预构建hashmap（抱歉，我有一段时间没有编写 Python，所以不记得数据类型了）必须具有 amortized 0(1). 但是使用其中一个具有次优哈希函数的n % RANDOM_PRIME_NUM_GREATER_THAN_100000可能会提供最佳解决方案。

于 2016-01-05T22:15:24.873 回答
0

第一的。没有什么比布尔值列表更快的了。您的任务总共有9! == 362880可能的排列，这是要存储在内存中的相当少量的数据：

visited_states = [False] * math.factorial(9)

或者，您可以使用稍微慢一些（虽然不是很多）并且内存占用要低得多（至少是一个数量级）的字节数组。然而，考虑到下一步，使用数组节省的内存可能没什么价值。

第二。您需要将您的特定排列转换为它的索引。有一些算法可以做到这一点，关于这个主题的最好的 StackOverflow 问题之一可能是这个：

查找给定排列的索引

你有固定的排列大小n == 9，所以无论算法有什么复杂性，在你的情况下它都相当于 O(1) 。

然而，为了产生更快的结果，您可以预先填充一个映射字典，这将为您提供 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(n 2 ) 复杂性，在您的情况下，即使不考虑额外的 python 代码本身，它也会导致性能下降 81 倍。因此，除非您有大量的内存限制，否则使用映射字典可能是速度方面的最佳解决方案。

附录。正如 Palec 所指出的，visited_states实际上根本不需要 list - 完全可以将True/False值直接存储在permutation_index字典中，这样可以节省一些内存和额外的列表查找。

于 2016-01-06T12:04:36.943 回答