如何找到二项式系数的某个子集

Question

假设我们有一个长度为n的数组。我们将这个数组命名为

keys[n] = {...}

我要找的是由"n选3"给出的子集的某个数组。命名为

combination[?][3] = {...}

这个数组需要满足以下条件:

• 数组中每个元素的3个键的长度为2的每个子集组合("3选择2")必须至少出现在另一个组合元素

• 每个键必须在组合中至少出现一个元素(实际上是两个元素，因为前面的条件)

• 组合的长度必须尽可能的小(所以不所有满足以上两个条件的解，我们需要进行选择最小长度)

• 可选:组合每次都是随机的，但仍然是最小长度

• 可选:中每个元素的3个键中没有长度为2的子集数组组合("3选择2")出现的频率特别高别人。

下面是一个例子:

1. Let keys[5] = {1,2,3,4,5};

2. 4选择3"收益率以下10个子集:{1,2,3},{1,2,4},{1、2、5},{1,3,4},{1,3,5},{1,4,5},{2、3、4},{2,4,5},{2、3、5},{3、4、5}

3. 这样一个解决方案是:{1,2,3},{1,2,4},{1,3,4},{2、3、5},{2,4,5},{3、4、5}(至少我没有找到更短)

我一整天都在想办法解决这个问题。我只想出了一个非常复杂的算法，甚至不能工作。

有谁知道如何解决这个问题，甚至只是你可能称之为这个问题吗?

Answer 1

这是单个封面的原始解决方案(哎呀)。

一些解决方案比其他解决方案更有可能，但它仍然是相当随机的。如果没有很多回溯发生的话，它是很快的。比如13，跑得很快。但是8运行得很慢，因为最短的解决方案有11个三元组，并且在接受10之前它必须一次又一次地失败。

思想是A*搜索最短可能的解决方案。代码中解释了一些技术细节。

请注意，它为5找到了以下解决方案:[[1, 2, 5], [1, 3, 4], [2, 3, 5], [2, 4, 5]]这比您的短。

import math
import heapq
import random
def min_cover (n):
# Small helper function.
def next_pair(pair):
i, j = pair
if j < n:
return [i, j+1]
elif i+1 < n:
return [i+1, i+2]
else:
raise StopIteration
# Another small helper function.
def pair_in(pair, groups):
i, j = pair
while groups is not None:
if i in groups[0] and j in groups[0]:
return True
groups = groups[1]
return False
numbers = [_ for _ in range(1, n+1)]
# Queue will be a priority queue of:
# [
#    min_pairs_at_finish,
#    neg_pair,
#    calculation_for_min_pairs_at_finish,
#    random_to_avoid_more_comparisons,
#    last_pair,
#    [triple, [triple, [triple, ...[None], ...]]]
# ]
#
# The difference between min_pairs and its calculation
# is subtle.  In the end, the number of pairs is a
# multiple of 3.  So if we've calculated a minimum
# of 10 airs, we ACTUALLY can't finish with less than 12.
#
# The reason for the ordering is as follows.
#
#     min_pairs_at_finish: We want as few as possible.
#     neg_pair: Prefer continuing solutions that are far along.
#     calculation_for_min_pairs_at_finish: Closer to done is better
#     random_to_avoid_more_comparisons: Comparing complex data
#       is slow.  Don't.  Bonus, this randomizes the answer!
#     last_pair: Where to continue from.
#     groups: The solution so far. This data structure efficiently
#       reuses memory between different partial solutions.
#
queue = [[0, [-1, -1], n*(n-1)/2, 0, [1, 1], None]]
while 0 < len(queue):
min_cost, neg_pair, min_calc_cost, r, pair, groups = heapq.heappop(queue)
try:
pair = next_pair(pair)
while pair_in(pair, groups):
pair = next_pair(pair)
for k in numbers:
if k != pair[0] and k != pair[1]:
extra = 0
if pair_in([pair[0], k], groups):
extra += 1
if pair_in([pair[1], k], groups):
extra += 1
next_item = [
3 * math.ceil((min_cost + extra)/3),
[-pair[0], -pair[1]],
min_cost + extra,
random.random(),
pair,
[sorted([pair[0], pair[1], k]), groups],
]
heapq.heappush(queue, next_item)
except StopIteration:
answer = []
while groups is not None:
answer.append(groups[0])
groups = groups[1]
return list(reversed(answer))
print(min_cover(5))
queue = [[0, n*(n-1)/2, 0, [1, 1], None]]
while 0 < len(queue):
min_cost, min_calc_cost, r, pair, groups = heapq.heappop(queue)
try:
pair = next_pair(pair)
while pair_in(pair, groups):
pair = next_pair(pair)
for k in numbers:
if k != pair[0] and k != pair[1]:
extra = 0
if pair_in([pair[0], k], groups):
extra += 1
if pair_in([pair[1], k], groups):
extra += 1
next_item = [
3 * math.ceil((min_cost + extra)/3),
min_cost + extra,
random.random(),
pair,
[sorted([pair[0], pair[1], k]), groups],
]
heapq.heappush(queue, next_item)
except StopIteration:
answer = []
while groups is not None:
answer.append(groups[0])
groups = groups[1]
return list(reversed(answer))
print(min_cover(5))

---

这是一个解决双重覆盖问题的方法，实际上是使用相同的技术。

import math
import heapq
import random
def min_double_cover (n):
# Small helper function.
def next_pair(pair):
i, j = pair
if j < n:
return [i, j+1]
elif i+1 < n:
return [i+1, i+2]
else:
raise StopIteration
# Another small helper function.
def double_pair_in(pair, groups):
i, j = pair
answer = 0
while groups is not None:
if i in groups[0] and j in groups[0]:
answer += 1
if 2 <= answer:
return True
groups = groups[1]
return False
def triple_in(triple, groups):
i, j, k = triple
while groups is not None:
if i in groups[0] and j in groups[0] and k in groups[0]:
return True
groups = groups[1]
return False
numbers = [_ for _ in range(1, n+1)]
# Queue will be a priority queue of:
# [
#    min_pairs_at_finish,
#    neg_pair,
#    calculation_for_min_pairs_at_finish,
#    random_to_avoid_more_comparisons,
#    last_pair,
#    [triple, [triple, [triple, ...[None], ...]]]
# ]
#
# The difference between min_pairs and its calculation
# is subtle.  In the end, the number of pairs is a
# multiple of 3.  So if we've calculated a minimum
# of 10 airs, we ACTUALLY can't finish with less than 12.
#
# The reason for the ordering is as follows.
#
#     min_pairs_at_finish: We want as few as possible.
#     neg_pair: Prefer continuing solutions that are far along.
#     calculation_for_min_pairs_at_finish: Closer to done is better
#     random_to_avoid_more_comparisons: Comparing complex data
#       structures is slow.  Don't.
#     last_pair: Where to continue from.
#     groups: The solution so far. This data structure efficiently
#       reuses memory between different partial solutions.
#
queue = [[0, [-1, -2], n*(n-1), 0, [1, 2], None]]
while 0 < len(queue):
min_cost, neg_pair, min_calc_cost, r, pair, groups = heapq.heappop(queue)
try:
while double_pair_in(pair, groups):
pair = next_pair(pair)
for k in numbers:
if k != pair[0] and k != pair[1] and not triple_in([pair[0], pair[1], k], groups):
extra = 0
if double_pair_in([pair[0], k], groups):
extra += 1
if double_pair_in([pair[1], k], groups):
extra += 1
next_item = [
3 * math.ceil((min_cost + extra)/3),
[-pair[0], -pair[1]],
min_cost + extra,
random.random(),
pair,
[sorted([pair[0], pair[1], k]), groups],
]
heapq.heappush(queue, next_item)
except StopIteration:
answer = []
while groups is not None:
answer.append(groups[0])
groups = groups[1]
return list(reversed(answer))
print(min_double_cover(5))

这次我根本不能运行8。不知道为什么。但是很多其他的数字是快的。

---

的一个潜在错误的答案,这是一个改变,让它完成:

...
queue = [[0, [-1, -2], n*(n-1), 0, [1, 2], None]]
min_pairs = 3*math.ceil(n*(n-1)/3)
threshold = 1000000
next_threshold = threshold
while 0 < len(queue):
if next_threshold < len(queue):
print("Threshold reached", next_threshold)
min_pairs += 3
for x in queue:
x[0] = max(min_pairs, x[0])
heapq.heapify(queue)
next_threshold += threshold
min_cost, neg_pair, min_calc_cost, r, pair, groups = heapq.heappop(queue)
...
next_item = [
max(min_pairs, 3 * math.ceil((min_cost + extra)/3)),
[-pair[0], -pair[1]],
min_cost + extra,
random.random(),
pair,
[sorted([pair[0], pair[1], k]), groups],
]
...

---

我发现了一个bug。下面的代码现在应该是正确的。

不能快速算出的数字，比如8，似乎是那些它必须回溯到更大数量的三元组的数字。如果您只收到一次阈值消息，那么答案可能差1，但很可能是正确的。如果你得到两次，同上。

import math
import heapq
import random
def min_double_cover (n):
# Small helper function.
def next_pair(pair):
i, j = pair
if j < n:
return [i, j+1]
elif i+1 < n:
return [i+1, i+2]
else:
raise StopIteration
# Another small helper function.
def double_pair_in(pair, groups):
i, j = pair
answer = 0
while groups is not None:
if i in groups[0] and j in groups[0]:
answer += 1
if 2 <= answer:
return True
groups = groups[1]
return False
def triple_in(triple, groups):
i, j, k = triple
while groups is not None:
if i in groups[0] and j in groups[0] and k in groups[0]:
return True
groups = groups[1]
return False
numbers = [_ for _ in range(1, n+1)]
# Queue will be a priority queue of:
# [
#    min_pairs_at_finish,
#    neg_pair,
#    calculation_for_min_pairs_at_finish,
#    random_to_avoid_more_comparisons,
#    last_pair,
#    [triple, [triple, [triple, ...[None], ...]]]
# ]
#
# The difference between min_pairs and its calculation
# is subtle.  In the end, the number of pairs is a
# multiple of 3.  So if we've calculated a minimum
# of 10 pairs, we ACTUALLY can't finish with less than 12.
#
# The reason for the ordering is as follows.
#
#     min_pairs_at_finish: We want as few as possible.
#     neg_pair: Prefer continuing solutions that are far along.
#     calculation_for_min_pairs_at_finish: Closer to done is better
#     random_to_avoid_more_comparisons: Comparing complex data
#       structures is slow.  Don't.
#     last_pair: Where to continue from.
#     groups: The solution so far. This data structure efficiently
#       reuses memory between different partial solutions.
#
queue = [[0, [-1, -2], n*(n-1), 0, [1, 2], None]]
min_pairs = 3*math.ceil(n*(n-1)/3)
threshold = 100000
next_threshold = threshold
while 0 < len(queue):
if next_threshold < len(queue):
print("Threshold reached", next_threshold)
min_pairs += 3
for x in queue:
x[0] = max(min_pairs, x[0])
heapq.heapify(queue)
next_threshold += threshold
min_cost, neg_pair, min_calc_cost, r, pair, groups = heapq.heappop(queue)
try:
while double_pair_in(pair, groups):
pair = next_pair(pair)
for k in numbers:
if k != pair[0] and k != pair[1] and not triple_in([pair[0], pair[1], k], groups):
extra = 0
if double_pair_in([pair[0], k], groups):
extra += 1
if double_pair_in([pair[1], k], groups):
extra += 1
next_item = [
max(min_pairs, 3 * math.ceil((min_calc_cost + extra)/3)),
[-pair[0], -pair[1]],
min_calc_cost + extra,
random.random(),
pair,
[sorted([pair[0], pair[1], k]), groups],
]
heapq.heappush(queue, next_item)
except StopIteration:
answer = []
while groups is not None:
answer.append(groups[0])
groups = groups[1]
return list(reversed(answer))
print(min_double_cover(8))