这个问题困扰我好几天了,不知道怎么解决。我已经非常努力地自己解决它,但现在我非常感谢一些帮助和正确方向的指示。
问题:
给定一组数字,以及每个数字可以大于或小于下一个数字的最大限制,根据限制确定数字的有效排序数。
示例:
数字:20、30、36、40
一个数字可以大于以下数字的最大数量:16
一个数字可以小于以下数字的最大数量:8
这里会有 3 个有效顺序:
36 40 30 20
40 36 30 20
40 30 36 20
我已经设计出一种使用递归和树生成所有有效排列的方法,但不幸的是,在列表中有许多有效顺序的情况下,它花费的时间太长(我相信接近 n!运行时间)。我觉得好像有一种更快、更数学的方法可以使用我只是没有看到的组合学来解决这个问题。任何建议将不胜感激,谢谢!
编辑: 这是我想出的置换算法的代码。代码的最后一部分使用我上面给出的示例对其进行了测试。它是用 Python 3.6 编写的。
class block:
def __init__(self, val, children):
self.val = val
self.children = children
# Gets all the possible children of the current head within the limits
def get_children(head, nums, b, visited, u, d):
global total
if all(visited):
total += 1
return
for i in range(b):
if not visited[i]:
if head.val - nums[i] <= d and nums[i] - head.val <= u:
head.children.append(block(nums[i], []))
visited[i] = True
get_children(head.children[-1], nums, b, visited, u, d)
visited[i] = False
# Display all the valid permutations of the current head
def show(head, vals, b):
vals.append(head.val)
if head.children == [] and len(vals) == b:
print(*vals)
return
for child in head.children:
show(child, vals[:], b)
# Test it out with the sample
b, nums, u, d = 4, [20, 30, 36, 40], 8, 16
visited = [False for x in range(b)]
total = 0
heads = []
for i in range(b):
heads.append(block(nums[i], []))
visited[i] = True
get_children(heads[-1], nums, b, visited, u, d)
visited[i] = False
show(heads[-1], [], b)
print(total)
这打印:
36 40 30 20
40 30 36 20
40 36 30 20
3
最佳答案
用 10 个相同的数字尝试您的方法导致运行时间为 35 秒。
我注意到的第一件事是该函数只需要列表头中的最后一个条目,因此该函数可以简化为采用整数而不是列表。以下代码进行了三种简化:
- 为 head 传递一个整数而不是列表
- 将总计更改为返回值而不是全局值
- 避免存储 child (因为只需要订单数)
简化后的代码如下:
def get_children(head, nums, b, visited, u, d):
if all(visited):
return 1
t = 0
for i in range(b):
if not visited[i]:
if head - nums[i] <= d and nums[i] - head <= u:
head2 = nums[i]
visited[i] = True
t += get_children(head2, nums, b, visited, u, d)
visited[i] = False
return t
# Test it out with the sample
nums, u, d = [20, 30, 36, 40], 8, 16
b = len(nums)
visited = [False for x in range(b)]
total = 0
for i in range(b):
head = nums[i]
visited[i] = True
total += get_children(head, nums, b, visited, u, d)
visited[i] = False
print(total)
列出 10 个相同的数字需要 7 秒。
我注意到的第二件事是(对于特定的测试用例)get_children 的返回值仅取决于 visited 中为 True 的事物和 head 的值。
因此我们可以缓存结果以避免重新计算它们:
cache={}
# Gets all the possible children of the current head within the limits
def get_children(head, nums, b, visited, u, d):
if all(visited):
return 1
key = head,sum(1<<i for i,v in enumerate(visited) if v)
result = cache.get(key,None)
if result is not None:
return result
t = 0
for i in range(b):
if not visited[i]:
if head - nums[i] <= d and nums[i] - head <= u:
head2 = nums[i]
visited[i] = True
t += get_children(head2, nums, b, visited, u, d)
visited[i] = False
cache[key] = t
return t
此版本只需要 0.03 秒即可列出 10 个相同的数字(即比原始版本快 1000 倍。)
如果您正在执行多个具有不同 b/u/d 值的测试用例,您应该在每个测试用例开始时重置缓存(即 cache={})。
关于algorithm - 计算满足要求的可能排列数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52654796/