4

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

我有一个包含 26 个字母（'A' - 'Z'）的池，每个字母可以根据需要多次使用。我想用这些字母创建列表；每个列表将有 10 个字母长，其中没有重复，我想保证，如果我比较生成的任何两个列表，就会有一个共同的字母。

问题：

  • 有没有一种简单的方法来做到这一点（即，通过使用库函数）？
  • 在给定池大小 (pool_size) 和列表长度 (list_length) 的情况下，我可以计算可以创建的最大列表数吗？

任何指向相关材料的指针将不胜感激；我不需要一个实现，只需要在某个地方放置我的阿基米德杠杆（可以理解为：我需要一个基础才能建立我的想法）。

“给我一个立足点，我会移动地球。” - 阿基米德

更新：我多么天真地认为字母表足以使用。让我们将池扩展至 300 个符号，但将列表长度保持为 10。这行得通吗？

4

2 回答 2

6

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

随机选择一个字母并将其放在两个列表中。然后再挑选 18 个不同的字母，并在每个列表中随机放入 9 个。然后您的列表将如下所示：

ABCDEFGHIJ
AKLMNOPQRS

如果您添加第三个列表，则不可能满足您的约束，因为只有七个未使用的字母。第三个列表必须与您不允许的其他列表之一共享至少两个字母。

更新

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

一般来说，对于n符号和长度列表，您可以通过使用上述算法x轻松生成至少列表（选择 1 个字母并将其添加到所有列表中。因此，对于 300 个符号和长度为 10 的列表，可以提供 33 个列表。floor((n-1)/(x-1))

但是可以通过使用不同的算法来改进这一点。例如，如果 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

现在不可能在不违反规则之一的情况下添加更多列表。

于 2012-10-24T18:54:08.540 回答
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)
于 2012-10-24T20:42:55.157 回答