给定一个 3x3 矩阵：
|1 2 3|
|4 5 6|
|7 8 9|
我想通过按照以下规则连接此矩阵中的数字来计算所有组合：
- 组合宽度介于 3 和 9 之间
- 一个号码只使用一次
- 您只能连接相邻的号码
例如：123、258、2589、123654等，
例如 1238 不是一个好的组合，因为 3 和 8 不相邻。123和321的组合是不一样的。
我希望我的描述是清楚的。
如果有人有任何想法，请告诉我。其实我不知道如何开始:D。谢谢
这是一个搜索问题。您可以使用直接的深度优先搜索和递归编程来快速解决问题。如下所示：
func search(matrix[N][M], x, y, digitsUsed[10], combination[L]) {
if length(combination) between 3 and 9 {
add this combination into your solution
}
// four adjacent directions to be attempted
dx = {1,0,0,-1}
dy = {0,1,-1,0}
for i = 0; i < 4; i++ {
next_x = x + dx[i]
next_y = y + dy[i]
if in_matrix(next_x, next_y) and not digitsUsed[matrix[next_x][next_y]] {
digitsUsed[matrix[next_x][next_y]] = true
combination += matrix[next_x][next_y]
search(matrix, next_x, next_y, digitsUsed, combination)
// At this time, sub-search starts with (next_x, next_y) has been completed.
digitsUsed[matrix[next_x][next_y]] = false
}
}
}
因此，您可以为矩阵中的每个网格运行搜索函数，并且解决方案中的每个组合彼此不同，因为它们从不同的网格开始。
此外，我们不需要记录指示矩阵中的一个网格已被遍历或未遍历的状态，因为每个数字只能使用一次，因此已遍历的网格将永远不会再次遍历，因为它们的数字已经包含在组合中。
下面是Python 3中作为递归深度优先探索的可能实现：
def find_combinations(data, min_length, max_length):
# Matrix of booleans indicating what values have been used
visited = [[False for _ in row] for row in data]
# Current combination
comb = []
# Start recursive algorithm at every possible position
for i in range(len(data)):
for j in range(len(data[i])):
# Add initial combination element and mark as visited
comb.append(data[i][j])
visited[i][j] = True
# Start recursive algorithm
yield from find_combinations_rec(data, min_length, max_length, visited, comb, i, j)
# After all combinations with current element have been produced remove it
visited[i][j] = False
comb.pop()
def find_combinations_rec(data, min_length, max_length, visited, comb, i, j):
# Yield the current combination if it has the right size
if min_length <= len(comb) <= max_length:
yield comb.copy()
# Stop the recursion after reaching maximum length
if len(comb) >= max_length:
return
# For each neighbor of the last added element
for i2, j2 in ((i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j)):
# Check the neighbor is valid and not visited
if i2 < 0 or i2 >= len(data) or j2 < 0 or j2 >= len(data[i2]) or visited[i2][j2]:
continue
# Add neighbor and mark as visited
comb.append(data[i2][j2])
visited[i2][j2] = True
# Produce combinations for current starting sequence
yield from find_combinations_rec(data, min_length, max_length, visited, comb, i2, j2)
# Remove last added combination element
visited[i2][j2] = False
comb.pop()
# Try it
data = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
min_length = 3
max_length = 9
for comb in find_combinations(data, min_length, max_length):
print(c)
输出：
[1, 2, 3]
[1, 2, 3, 6]
[1, 2, 3, 6, 5]
[1, 2, 3, 6, 5, 4]
[1, 2, 3, 6, 5, 4, 7]
[1, 2, 3, 6, 5, 4, 7, 8]
[1, 2, 3, 6, 5, 4, 7, 8, 9]
[1, 2, 3, 6, 5, 8]
[1, 2, 3, 6, 5, 8, 7]
[1, 2, 3, 6, 5, 8, 7, 4]
[1, 2, 3, 6, 5, 8, 9]
[1, 2, 3, 6, 9]
[1, 2, 3, 6, 9, 8]
[1, 2, 3, 6, 9, 8, 5]
[1, 2, 3, 6, 9, 8, 5, 4]
[1, 2, 3, 6, 9, 8, 5, 4, 7]
...
查看所有组合并获取连接的组合：
import itertools
def coords(n):
"""Coordinates of number n in the matrix."""
return (n - 1) // 3, (n - 1) % 3
def adjacent(a, b):
"""Check if a and b are adjacent in the matrix."""
ai, aj = coords(a)
bi, bj = coords(b)
return abs(ai - bi) + abs(aj - bj) == 1
def connected(comb):
"""Check if combination is connected."""
return all(adjacent(a, b) for a, b in zip(comb, comb[1:]))
for width in range(3, 10):
for comb in itertools.permutations(range(1, 10), width):
if connected(comb):
print(comb)