生成列表中只有一個共同的項目

在Python中，我正在探索一個想法，但我不確定如何正確實現它。生成列表中只有一個共同的項目

我有26個字母（'A' - 'Z'），每個字母可以根據需要多次使用。我想用這些字母創建列表;每個列表將是10個字母長，其中沒有重複，我想保證，如果我比較任何兩個列表生成，將有正好一個字母的共同點。

問題：

有一個簡單的方法來做到這一點（即，通過使用庫函數）？
根據池的大小（pool_size）和列表的長度（list_length），我可以計算出我能夠創建的最大列表數量嗎？

任何指向相關材料的指針將不勝感激;我並不需要太多的實施來建立我的阿基米德槓桿（讀作：我需要一個基礎，然後才能構建我的想法）。「給我一個地方站立，我會移動地球。」 - 阿基米德

UPDATE：我多麼天真地認爲字母表足以應付。讓我們將該池擴展爲300個符號，但將列表保持爲10.這是否有效？

來源

2012-10-24 taserian

如果你只有26個字母（AZ），每個列表的長度爲10個字母，然後在生成第三個列表時，它至少與其他列表中的一個具有多於一個字母。 – voithos

只有26個字母可供選擇，它只能生成兩個列表。

隨機選擇一個字母，並將其放在兩個列表中。然後再選擇18個不同的字母，並在每個列表中隨機放置9個字母。然後，你的列表將是這個樣子：

ABCDEFGHIJ 
AKLMNOPQRS

如果添加第三個列表這是不可能的，因爲只有七個未信件，以滿足您的約束。第三份名單必須與其他名單中至少有兩封信一起分享，這是你不允許的。

更新

這隻能部分地回答了你的更新問題，但我會後也無妨，因爲它可以幫助你或他人找到最佳的解決方案。

通常與n符號和長度x可以很容易地通過使用上述（採摘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

現在不可能在不違反規則的情況下添加更多列表。

來源

2012-10-24 18:54:08

你也可以很容易地按順序循環訪問池，並使用最後一個字母兩次：'ABCDEFGHIJ'，'JKLMNOPQRST'。 – voithos

這就是我要找的;當我第一次嘗試這個時，我在更新之後生成了像第一個例子那樣的列表，但我意識到必須有更多。有沒有一種可以產生類似於第二種的廣義算法？ – taserian

@taserian：我對如何解決這個問題有一些模糊的想法，但是我想知道是否有人可以提出一些巧妙的建議......希望別人能發表一個很簡單並且可以同時解決問題的好答案。 = 26，x = 2'和'n = 10，x = 4'。 –

這是我找到的所有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×= 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-24 20:42:55 sarwar

第二種算法有時比第一種算法的結果少，例如在n = 10 x = 4的情況下，如Mark Byers所示。 –

生成列表中只有一個共同的項目

回答

相關問題