如何從Python中的字符串列表中創建長度爲100個字符的所有可能句子

Question

我試圖從給定的字符串列表中創建長度爲100個字符的句子。長度必須是正好一百個字符。我們還必須使用排列查找所有可能的句子。每個單詞之間必須有一個空格，並且不允許有重複單詞。名單如下：

['saintliness', 'wearyingly', 'shampoo', 'headstone', 'dripdry', 'elapse', 'redaction', 'allegiance', 'expressionless', 'awesomeness', 'hearkened', 'aloneness', 'beheld', 'courtship', 'swoops', 'memphis', 'attentional', 'pintsized', 'rustics', 'hermeneutics', 'dismissive', 'delimiting', 'proposes', 'between', 'postilion', 'repress', 'racecourse', 'matures', 'directions', 'bloodline', 'despairing', 'syrian', 'guttering', 'unsung', 'suspends', 'coachmen', 'usurpation', 'convenience', 'portal', 'deferentially', 'tarmacadam', 'underlay', 'lifetime', 'nudeness', 'influences', 'unicyclists', 'endangers', 'unbridled', 'kennedy', 'indian', 'reminiscent', 'ravish', 'republics', 'nucleic', 'acacia', 'redoubled', 'minnows', 'bucklers', 'decays', 'garnered', 'aussies', 'harshen', 'monogram', 'consignments', 'continuum', 'pinion', 'inception', 'immoderate', 'reiterated', 'hipster', 'stridently', 'relinquished', 'microphones', 'righthanders', 'ethereally', 'glutted', 'dandies', 'entangle', 'selfdestructive', 'selfrighteous', 'rudiments', 'spotlessly', 'comradeinarms', 'shoves', 'presidential', 'amusingly', 'schoolboys', 'phlogiston', 'teachable', 'letting', 'remittances', 'armchairs', 'besieged', 'monophthongs', 'mountainside', 'aweless', 'redialling', 'licked', 'shamming', 'eigenstate'] 

方法：

我的第一個方法是使用回溯和排列生成所有的句子。但是我認爲，由於我的名單如此之大，因此複雜程度會過高。

有沒有其他的方法可以在這裏使用或者我可以在這裏使用的一些內置函數/包？什麼是最好的方式在Python中做到這一點？任何指針在這裏都會有所幫助。

Answer 1

你不能這樣做。

想一想：即使選擇4個字你已經有100×99×98×97的可能性，差不多有1億個。

考慮到你的單詞的長度，至少有8個單詞將適合在句子中。有100×99×98×93的可能性。那大概是7×10^15，這是一個完全不可行的數字。

Answer 2

簡化一下：將所有字符串從「xxx」更改爲「xxx」。然後將句子長度設置爲101.這允許您使用len（x）而不是len（x）+1，並消除句子中最後一個單詞的邊緣情況。當你遍歷，並從左到右建立句子時，你可以根據你剛剛構建的句子排除可能溢出長度的單詞。

UPDATE：

認爲這是一個基礎n個問題，其中n是你的單詞數。創建一個用0初始化的向量[注意：它只是固定的大小來說明]：

acc = [0, 0, 0, 0]

這是您的「累加器」。

現在構建你的句子：

dict[acc[0]] + dict[acc[1]] + dict[acc[2]] + dict[acc[3]]

所以，你得到able able able able

現在增加在ACC最顯著 「數字」。這由「curpos」表示。這裏CURPOS是3

[0, 0, 0, 1]

現在你able able able baker

你保持撞到ACC [CURPOS]直到你打[0, 0, 0, n]現在你已經患上了「開展」。 「向左」通過遞減曲線爲2.遞增acc [曲線]。如果它沒有「執行」，「往右走」通過增加curpos並設置acc [curpos] = 0。如果你已經得到一個執行，你可以通過減少curpos爲1來做「向左」。

這是一種回溯形式（例如「走左」），但不需要樹。只是這個acc矢量和一個狀態機有三種狀態：goleft，goright，test/trunc/output/inc。

「去右」後的曲線將回到「最顯着」的位置。也就是說，從acc [0到curpos - 1]構造的句子長度（長度爲，沒有添加最後一個單詞）小於100.如果它太長（例如已經超過100），請執行「向左」 。如果太短（例如，您必須添加另一個單詞以接近[足夠]到100），請執行「向右」

當您得到執行和curpos == 0時，您已完成

我最近將此設計爲「吸血鬼號碼挑戰」的解決方案，所需的遍歷非常相似。

Answer 3

你問題的規模太大了，但是如果1）你的實際問題在範圍上小得多，和/或2）你有很多時間和一個非常快的計算機，你可以使用遞歸生成這些排列發電機。

def f(string, list1): 
    for word in list1: 
     new_string = string + (' ' if string else '') + word 
     # If there are other constraints that will allow you to prune branches, 
     # you can add those conditions here and break out of the for loop 
     if len(new_string) >= 100: 
      yield new_string[:100] 
     else: 
      list2 = list1[:] 
      list2.remove(word) 
      for item in f(new_string, list2): 
       yield item 

x = f('', list1) 
for sentence in x: 
    check(sentence) 

一個需要注意的是，這可能會產生相同的句子，如果在最後兩個詞被截斷看起來相同。

Answer 4

我不打算提供一個完整的解決方案，但我會通過我的思考。

約束：

• 超過100個字符的完整列表的排列可以立即拋出。 （好吧，99 + len(longest_word))。）
• 你基本上是在處理列表中元素的冪集的一個子集。

鑑於：

• 構建發電機組，但丟棄超出最高
• 篩選最終定爲完全符合您的需求

因此判處任何句子你可以有以下幾種：

def construct_sentences(dictionary: list, length: int) -> list: 
    if not dictionary: 
     return [(0, [])] 
    else: 
     word = dictionary[0] 
     word_length = len(word) + 1 
     subset_length = length - word_length 
     sentence_subset = construct_sentences(dictionary[1:], subset_length) 
     new_sentences = [] 
     for sentence_length, sentence in sentence_subset: 
      if sentence_length + word_length <= length: 
       new_sentences = new_sentences + [(sentence_length + word_length, sentence + [word])] 
     return new_sentences + sentence_subset 

我使用元組來寫下列表的長度，並使其易於比較。上述函數的結果會給出一個句子的列表，這些句子的長度都小於長度（當考慮潛在的排列組合時，這是一個關鍵因素：100很短，因此排列的數量很容易被丟棄）。下一步將是簡單地filter任何不夠長的句子（即100個字符）。

請注意，在這一點上你有每一個可能的列表過濾你的標準，但該列表可能會被重新排序2^n方式。不過，這變成了一個更易於管理的情況。有100個單詞的列表，平均每個單詞不超過9個字符，句子中的平均單詞數量等於10. 2^10不是世界上最糟糕的情況...

您必須修改它爲你的截斷情況，當然，但這會讓你進入球場。除非我完全錯過了什麼，這是總是可能。我倍加認爲有些事情是錯的，因爲運行這會產生令人驚訝的短名單。

Answer 5

此問題類似於partitioning in number theory的問題。

該問題的複雜性可以（可能）使用一些在問題陳述編碼的約束降低：

1. 在單詞列表中的單詞的長度。
2. 重複字長：例如，長度爲8的字重複X次。

這裏是一個可能的一般方法（將採取一些精煉）：

• 找到所有的分區使用僅在單詞列表中的單詞長度100號。 （你可以從字長和它們的重複開始，而不是通過暴力強制所有可能的分區。）

• 過濾掉重複長度值超出列表中單詞重複長度值的分區。

• 將單詞組合應用到分區上。一組長度相等的單詞將被映射到分區中的長度值。例如，假設你有分區(15+15+15+10+10+10+10+5+5+5)，那麼你可以爲3個以上的所有長度15個單詞生成組合，4個以上的長度爲10個單詞，3個以上的長度爲5個單詞。（我忽略了空間分離問題​​）。

• 在所有分區上生成所有組合的排列。