最大可能的字母矩形

Question

编写一个程序，找到可能的最大字母矩形，使得每一行都形成单词（从左到右），每一列都形成单词（从上到下）。

我发现这是一个有趣的问题。虽然听起来像作业，但它并不是（我不在学校）。我只是为了好玩而做这个。

Example

From cat, car, ape, api, rep, tip we get the following rectangle (which is a square):

c a r
a p e
t i p

我的初步想法是构建某种前缀树，以便可以检索所有以特定字符串开头的单词。当我们已经有两个或更多单词（无论是从上到下还是从左到右）并且需要找到下一个要添加的单词时，这将非常有用。

还有其他的想法吗？

编辑

这是否可以用三维长方体来完成？

如果对角线上需要有有效的单词（点子归功于user645466），如何优化算法？

- Adrian

---

这听起来像是一个很有趣的笑话，可以用来玩Scrabble游戏。 - David Brigada

@Adrian：另请参阅Bananagrams。 - David Brigada

可能是NP难问题，这样可以吸引人群的注意。 ;) - Venki

添加对角线。这可能真的是NP难问题 :) - user645466

@templatetypedef评论者“d”提出了从3SAT简化的方法。个人认为，使用精确覆盖作为源问题可能会更容易一些。 - Per

Answer 1

让D成为字典。固定m和n。我们可以将寻找一个m×n矩形的问题构建为约束满足问题（CSP）。

回溯与约束传播的结合是解决CSP的一种非常常见的方法。粗略地说，回溯意味着我们选择一个变量，猜测它的值，并递归地解决一个少一个变量的子问题，而约束传播则意味着尝试减少每个变量的可能性数量（可能为零，这意味着没有解决方案）。

例如，我们可以通过选择x_1,1=Q来开始一个3×3网格。

Q??
???
???

使用英语字典，x_1,2和x_2,1 的唯一可能性是 U（在之前的Scrabble“单词”中）。

解决CSP的艺术在于平衡回溯和约束传播。如果我们根本不传播约束，那么我们只是使用暴力方法。如果我们完美地传播约束，那么我们就不需要回溯，但解决NP难问题的传播算法本身可能非常昂贵。

在这个问题中，在每个回溯节点上使用大型字典会变得很昂贵，除非我们有很好的数据结构支持。我将概述一种方法，该方法使用trie或DAWG快速计算由前缀扩展到完整单词的字母集。

在每个回溯节点上，我们分配的变量集合是Young表。换句话说，直到其上方和左侧的变量被分配之前，没有变量被分配。在下面的图表中， . 表示一个已分配的变量，* 和？表示未分配的变量。

.....*
...*??
...*??
..*???
*?????

被标记为*的变量是下一个被赋值的候选变量。选择多个选项而不是每次选择一个固定的变量的优点在于，某些变量排序可能比其他变量排序好得多。

对于每个*，在trie / DAWG中进行两次查找，一次水平查找，一次垂直查找，并计算可以接下来出现的字母集合的交集。一种经典策略是选择具有最少可能性的变量，以便我们更快地达到矛盾。我喜欢这种策略，因为当存在零可能性的变量时，它会自然地修剪，并且当存在一个变量时，它会自然地传播。通过缓存结果，我们可以使评估每个节点非常快速。

- Per

---

如果我理解正确的话，通过“缓存结果”，您是指矩形中每个位置可能的字母列表以及可能对应于两个位置（紧靠左侧和紧靠上方）的前缀树节点。每当回溯并更改先前的决策时，该缓存应该无效；因此，它不像记忆化那样强大，其中您永远不会针对相同的参数重新计算。无论如何，即使处理仅 16,000 个单词也会出现极快的运行时增长，几乎需要一个小时，而似乎没有希望处理数百万个单词。 - max

Answer 2

给定一个给定长度的单词字典，创建两个新的字典：第一个包含所有单字母前缀（可以是给定长度的单词的第一个字母的所有字母），第二个包含所有双字母前缀（可以是给定长度的单词的前两个字母的所有序列）。您也可以进行三重前缀，但您可能不需要超过那个范围。

1. 从字典中选择一个单词，称之为X。这将是矩阵的第一行。

2. 使用您制作的便捷列表检查X[1]、X[2]、...、X[N]是否都是有效的单个字母前缀。如果是，请继续进行步骤3；否则返回步骤1。

3. 从字典中选择一个单词，称之为Y。这将是矩阵的第二行。

4. 使用您制作的便捷列表检查X[1] Y[1]、X[2] Y[2]、...、X[N] Y[N]是否都是有效的双字母前缀。如果是，请继续进行步骤5；否则返回步骤3。如果这是字典中的最后一个单词，则返回步骤1。

   ...

   2(N-1). 从字典中选择一个单词，称之为Z。这将是矩阵的第N行。

   2N. 检查X[1] Y[1] ... Z[1]、X[2] Y[2] ... Z[2]、...、X[N] Y[N] ... Z[N]是否都是字典中的单词。如果是，恭喜您，完成了！否则返回步骤2(N-1)。如果这是字典中的最后一个单词，则返回步骤2(n-3)。

逻辑是逐行构建单词矩形，选择行的单词，然后检查列是否可以用单词完成。这比逐个字母添加要快得多。

- PengOne

---

你把这个算法专门针对我的3x3示例做了吗？如果我误导了你，很抱歉，我是在寻找一个n x m的矩形。我问这个问题是因为我看到了一个单字母前缀列表和一个双字母前缀列表，这对于一个3x3的矩形是有意义的。不过我喜欢这种推理方式，它可以被概括。 - Adrian

@Adrian，很容易地可以推广到找到一个nxn的解决方案。 - PengOne

你能解释一下单字母和双字母前缀是什么吗？我可能没有理解正确。 - Adrian

@Adrian 我对它进行了通用情况的修订，并添加了前缀列表的解释（例如，你的示例中单字母前缀为A,C,R,T，双字母前缀为AP,CA,RE,TI）。 - PengOne

Answer 3

创建一个Bag[]，用于存储长度为index的单词，然后为每个长度的wordList创建一个Trie数组，每个数组对应一个Trie。

   Rectangle makeRectangle(length, height, rectangle)
    {
        if ( length == rectangle.length()) check if complete and return;
        checkIfPartialComplete - check columns for valid prefixes
        for ( i from 1 to grouplist[i-1])
        {
            newRectangle = append word[i] to rectangle 
            return makeRectangle(l,h, rectangle with appended word) if not equal to null
        }
    }


boolean checkPartial(int l, Trie trie)
{
    for ( int i =0 ; i < l; i++)
    {
        String col = getColumn(i);
        if (!trie.contains(col))
        {
            return false;
        }
    }
    return true;
}
boolean checkComplete(int l, Bag<String> lengthGroup)
{
    for ( int i=0; i < l ; i++)
    {
        String col = getColumn(i);
        if (!lengthGroup.contains(col))
        {
            return false;
        }
    }
    return true;
}

- Nataraj

---

从CCI书中摘录 - everlasto