在Python中,我正在寻找一个想法,但我不确定如何正确实现它.
我有一个26个字母的池('A' - 'Z'),每个字母可以根据需要多次使用.我想用这些字母创建列表; 每个列表长10个字母,里面没有重复,我想保证如果我比较生成的任何两个列表,就会有一个共同的字母.
问题:
任何指向相关材料的指针都将受到赞赏; 我不需要在某个地方实现我的阿基米德杠杆(读作:我需要一个基础才能构建我的想法).
"给我一个站立的地方,我会移动地球." - 阿基米德
更新:我认为字母表足以与之合作是多么天真.让我们将池扩展为300个符号,但保持列表的长度为10.这有用吗？
只有26个字母可供选择,它只能生成两个列表.
随机选择一个字母并将其放在两个列表中.然后选择18个不同的字母,并在每个列表中随机放置9个字母.然后你的列表看起来像这样:
ABCDEFGHIJ
AKLMNOPQRS
如果添加第三个列表,则无法满足约束条件,因为只有七个未使用的字母.第三个列表必须与其他列表中的一个共享至少两个字母,您不允许这样做.
更新
这只会部分回答您更新的问题,但无论如何我都会发布,因为它可能会帮助您或其他人找到最佳解决方案.
通常使用n符号和长度列表,x您可以floor((n-1)/(x-1))使用上述算法轻松生成至少列表(选择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
现在不可能在不违反其中一条规则的情况下添加更多列表.