生成恰好有一个共同项的列表

Question

生成恰好有一个共同项的列表

python

4

在Python中，我正在探索一个想法，但我不确定如何正确实现它。

我有一个由26个字母（'A' - 'Z'）组成的池，每个字母可以使用任意次数。我想使用这些字母创建列表; 每个列表将包含10个字母，并且内部没有重复项，并且我希望确保如果比较生成的任何两个列表，它们将仅有一个相同的字母。

问题：

1. 有没有简单的方法来做到这一点（即通过使用库函数）？ 2. 可以根据池的大小（pool_size）和列表长度（list_length）计算能够创建的最大列表数量吗？

任何相关资料的指针都将不胜感激；我不需要实现，只是需要一个放置浮标的地方（读作：在构建我的想法之前，我需要一个基础）。

“给我一个支点，我就可以撬动地球。”-阿基米德

更新：我多么天真，认为字母表足够工作。让我们将池扩大到300个符号，但将列表保持在长度为10。那行吗？

- taserian

2

如果你只有26个字母（A-Z），每个列表都有10个字母，那么当你生成第三个列表时，它肯定会与其他列表中的至少一个字母重复。 - voithos

2个回答

1

这是我找到的适用于所有Set和Line Length值的通用解决方案。第一个假设您不希望两个解决方案共享相同的公共元素，但您希望每个解决方案与其他每个解决方案都有一个共同元素。给定一个无限的选择池，解决方案的总数受每个解决方案的长度限制。

SET_LENGTH = 10
CHOICE_LENGTH = 300

data = set(range(CHOICE_LENGTH))
solutions =[]
solution_sets = []
used = set()

while True:
    new_solution = []
    #Try to get unique values from each previous set
    try:
        for sol_set in solution_sets:
            while True:
                candidate = sol_set.pop()
                if not candidate in used:
                    new_solution.append(candidate)
                    used.update([candidate])
                    break
    except KeyError, e:
        print e
        break
    #Fill with new data until the line is long enough
    try:
        while len(new_solution) < SET_LENGTH:
            new_solution.append(data.pop())
    except KeyError, e:
        print e
        break
    solutions.append(new_solution)
    solution_sets.append(set(new_solution))
#Show the results
for solution in solutions:
    print solution
print "Orphans %s" % len(data)

例如，n = 300，x = 10，则产生以下结果：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[1, 10, 19, 20, 21, 22, 23, 24, 25, 26]
[2, 11, 19, 27, 28, 29, 30, 31, 32, 33]
[3, 12, 20, 32, 34, 35, 36, 37, 38, 39]
[4, 13, 21, 33, 34, 40, 41, 42, 43, 44]
[5, 14, 22, 27, 36, 40, 45, 46, 47, 48]
[6, 15, 23, 28, 37, 41, 45, 49, 50, 51]
[7, 16, 24, 29, 38, 42, 47, 49, 52, 53]
[8, 17, 25, 30, 39, 43, 48, 50, 52, 54]
[9, 18, 26, 31, 35, 44, 46, 51, 53, 54]
Orphans 245

如果您不关心有多少解决方案共享相同的公共元素，那么这将更加容易：

SET_LENGTH = 2
CHOICE_LENGTH = 300

data = set(range(CHOICE_LENGTH))
solutions =[]
alpha = data.pop()
while True:
    new_solution = [alpha]
    try:
        [new_solution.append(data.pop()) for x in range(SET_LENGTH-1)]
    except KeyError, e:
        break
    solutions.append(new_solution)

for solution in solutions:
    print solution
print "Solutions: %s" % len(solutions)
print "Orphans: %s" % len(data)

- sarwar

第二个算法有时会比第一个算法给出更少的结果，例如在n=10 x=4的情况下，这是由Mark Byers证明的。 - Janne Karila

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Byers · Accepted Answer

只有26个字母可供选择，因此只能生成两个列表。

随机选择一个字母并将其放入两个列表中。然后再选择18个不同的字母，将其中9个随机放入每个列表中。此时你的列表大致如下：

ABCDEFGHIJ
AKLMNOPQRS

如果您添加第三个列表，由于只有七个未使用的字母，因此无法满足您的约束条件。第三个列表将不得不与另一个列表共享至少两个字母，这是被禁止的。

更新

这只是部分回答您更新后的问题，但我会发布它，因为它可能会帮助您或其他人找到最佳解决方案。

通常情况下，对于长度为x的n个符号和列表，您可以使用上述算法（选择1个字母并将其添加到所有列表中）轻松生成至少floor((n-1)/(x-1))个列表。因此，对于300个符号和长度为10的列表，这将给出33个列表。

但是，通过使用不同的算法可能可以改进这一点。例如，如果n为10，x为4，则上述算法仅提供三个列表：

ABCD
AEFG
AHIJ

但是一种更有效地重复使用字母的算法可以生成五个列表：

ABCD
AEFG
BEHI
CFHJ
DGIJ

我使用了贪心算法生成这些列表：对于每个新列表，尽量从先前的列表中重用不同的字母，这意味着你需要尽可能少地添加新字母。

第二个列表从第一个列表中重用了一个字母，并添加了三个新字母。第三个列表从前两个列表中分别重用了一个不同的字母，因此只引入了两个新字母。第四个列表重用了已经出现过的三个字母，并添加了一个新字母。最后一个列表现在可以从前面的每个列表中重用一个字母，而不需要添加任何新字母。

更新2 贪心算法肯定不是最优解决方案。

让我们试一下：n = 26，x = 2

简单的解决方案给出了最优的25个列表：

AB
AC
AD
..
AZ

然而，贪心算法只生成3个列表：

AB
AC
BC

现在已经不可能再添加任何列表，否则将违反其中的规则。