如何从Python中的字符串列表创建所有可能的长度为100个字符的句子

Question

我试图从给定的字符串列表中创建一个长度为100个字符的句子。长度必须正好是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

简化一点：将所有字符串从“xxx”改为“xxx”。然后将句子长度设置为101。这允许您使用len（x）而不是len（x）+1，并消除了句子中最后一个单词的边大小写。当您遍历并从左到右构建句子时，您可以根据您刚刚构建的句子来消除会溢出长度的单词。在

更新：

把这看作是一个以n为基数的问题，其中n是单词的数量。创建一个用0初始化的向量[注意：它只是固定大小来说明]：

acc = [0, 0, 0, 0]

这是你的“累加器”。在

现在构造你的句子：

^{pr2}$

所以，你得到able able able able

现在递增acc中最有效的“数字”。这用“curpos”表示。这里curpos是3。在

[0, 0, 0, 1]

现在你得到able able able baker

你一直按acc[curpos]直到你点击[0, 0, 0, n]现在你得到了一个“执行”通过将curpos减为2来向左移动。增量acc[curpos]。如果不“执行”，则通过递增curpos并设置acc[curpos]=0来右转。如果你得到了一个执行，你会做一个“向左走”，将curpos减为1。在

这是回溯的一种形式（例如“向左走”），但不需要树。只有这个acc向量和一个状态机，有三个状态：goleft，goright，test/trunc/output/inc

在“右转”之后，curpos将回到“最重要”的位置。也就是说，从acc[0到curpos-1]构造的句子长度（不加最后一个单词的长度小于100。如果时间太长（例如已经超过100），请执行“向左走”。如果它太短（例如，你必须再加一个词才能接近100），做一个“向右走”

当你得到一个执行并且curpos==0，你就完成了

我最近设计了一个解决“吸血鬼数字挑战”的方法，你需要的遍历非常相似。在

Answer 2

这个问题类似于partitioning in number theory的问题。在

使用问题陈述中编码的一些约束可以（大概）降低问题的复杂性：

1. 单词列表中单词的长度。在
2. 单词长度的重复：例如长度为8的单词被重复X次。在

这里有一个可能的通用方法（需要一些改进）：

• 只使用单词列表中单词的长度来查找数字100的所有分区。（您可以从字长和它们的重复开始，而不是通过暴力强制所有可能的分区。）

• 筛选出重复长度值超过列表中单词重复长度值的分区。

• 将单词组合应用到分区上。一组长度相等的单词将映射到分区中的长度值。例如，假设您有一个分区(15+15+15+10+10+10+10+5+5+5)，那么您将生成长度为15个单词除以3，长度为10个单词除以4，长度为5个单词除以3的组合。（我忽略了空间分隔问题）。

• 在所有分区上生成所有组合的排列。

Answer 3

你做不到。

想想看：即使选择4个单词，你也有100×99×98×97的可能性，几乎有1亿个。在

考虑到你所说的话的长度，至少有8个词适合这个句子。有100×99×98…×93种可能性。大约是7×10^15，一个完全不可行的数字。在