代码之家 › 专栏 › 技术社区 › Imbue

高效的单词加扰算法

algorithm

Imbue · 技术社区 · 17 年前

我正在寻找一种有效的算法,将一组字母打乱为包含最多单词的排列。

一个简单的算法是尝试对每个置换进行评分。我相信这是O(n!),所以只对上面的6个字母尝试720种不同的排列(包括一些重复,因为这个例子有两次e)。当然,对于更多的信件,天真的解决方案很快就变得不可能了。

该算法不必实际产生最佳解决方案,但它应该在合理的时间内找到一个好的解决方案。对于我的应用程序,只需猜测( Monte Carlo )几百万个排列的效果相当差,所以这是目前需要击败的目标。

Aho-Corasick 对排列进行评分的算法。它只需在一次文本浏览中搜索字典中的每个单词,所以我认为它非常有效。这也意味着我将所有单词存储在 trie Bloom Filter .

5 回复 | 直到 8 年前

Nathan Kitchen 17 年前

这里有一个想法,灵感来自 Markov Chains :

Yevgeny Doctor 17 年前

simulated annealing ,已成功用于多个领域的复杂优化问题。基本上,你做随机爬坡,同时逐渐减少随机性。既然你已经有了Aho-Corasick的得分,那么你已经完成了大部分的工作。你所需要的只是一种生成邻居排列的方法;为此,交换一对字母这样简单的事情应该很有效。

Rodyland 17 年前

只是一些无聊的想法。

Wouter van Nifterick Andrey 17 年前

在此页面上,您可以在线生成字谜。我已经玩了一段时间了,它很有趣。它没有详细解释它是如何工作的,但参数提供了一些见解。 http://wordsmith.org/anagram/advanced.html

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

1 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

1 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

1 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

1 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

1 年前