5

已解决：我要问的是已解决，但请随时用其他方法回答。这是解读者用答案制作的字母。项目页面

我目前是一名 AP 计算机科学专业的学生。我一直在研究一个字母解扰器，它可以在字典中读取并打印输入字母集时可能出现的单词列表。为此，我制作了一张地图，Map<String,Set<String>> 其中将在“aerht”键下和相应的集合中输入“earth”。

Example How Would I generate all of these:
CAKE -> ACEK
A          C           E           K
AC        CE           EK               
ACE       CEK            
ACEK

AE       CK
AEK
ACK
AK

我遇到的问题是，一些键值没有被检查，因为目前我接受了一组数字并将字符按字母顺序排列，例如 earth->aehrt 但这会跳过诸如 aht->hat 或 eht 之类的组合 -> .

所以基本上我的问题是如何简化获取包含在这样一个键中的所有字母组合的过程。例如 earth-> aehrt,a,ae,aeh,aehr,ah,ahr,ahrt,aer,aert 等等，这样我就可以将所有这些键与我读过的字典中的键进行交叉引用。字母 [] 包含 a,e ,h,r,t 的顺序。另外，test 是一个 Set 的 ArrayList。关键是“aehrt”。

for(int z = 0; z<key.length();z++) {
    Set<String> temp = new HashSet<String>();

    //s1 = t*s0 ∪ {t} ∪ s0 = {t}
    for(String str: test.get(z)) //t*s0
                str+=letters[z];

    test.get(z).add(letters[z]); //{t}  
    test.get(z).addAll(test.get(z-1));//s0
    test.get(z).addAll(temp);
}
4

3 回答 3

3

从按字母顺序排列的键“aehrt”开始，您可以使用以下方法找到所有可能的字母组合：

  1. 从...开始：       S0 = {}
  2. 接下来，采取a：   S1 = a⋅S0 ∪ S0 ∪ {a} = {a}
  3. 接下来，采取e：   S2 = e⋅S1 ∪ S1 ∪ {e} = {ae, a, e}
  4. 接下来，采取h：   S3 = h⋅S2 ∪ S2 ∪ {h} = {aeh, ah, eh, ae, a, e, h}
  5. ETC...

一旦你拥有（整套组合），请对照你的地图检查它们。S5

public static void main(String... args){     
    Set<String> set = new TreeSet<String>();
    String key = "aehrt";

    //S1 = c*S0 ∪ {c} ∪ S0
    for(int z = 0; z < key.length();z++) {
        Set<String> temp = new HashSet<String>();
        char c = key.charAt(z);        

        for(String str: set)
            temp.add(str + c); // ∪ c*S0
        set.add(c+"");         // ∪ {c}
        set.addAll(temp);      // ∪ S0
    }

    System.out.println(set);
}

output: [a, ae, aeh, aehr, aehrt, aeht, aer, aert, aet, ah, ahr, ahrt, aht, ar, art,
         at, e, eh, ehr, ehrt, eht, er, ert, et, h, hr, hrt, ht, r, rt, t]
于 2013-12-05T05:25:36.207 回答
1

假设您有 String CAKE ：所有 4 位数字都不同。然后你会有组合4C1 + 4C2 + 4C3 + 4C4 = 2^4 - 1 = 15

CAKE CA Ak KE EC CK CE CAK AKE KEC CKE 蛋糕。

如果你写从 1 到 2^4-1 的数字，它们将是 0001 0010 0011 0100 等等。将这些数字映射到您的 String CAKE 。无论您在哪里找到 0，该字符都是空的。示例

0001 = _ _ _ E

0010 = _ _ K _

0011 = _ _ 克

0100 = _ 一个 _ _

等等。你会得到你所有的蛋糕组合。我写了一个程序来说明在java中：

public class AllCombinations {
    public static void main(String[] args) {
        char c[] = new char[] {'C','A','K','E'};
        int t = (int) Math.pow(2, c.length);
        for(int i=1;i<t;i++) {
            String s = Integer.toBinaryString(i);
            String comb = getComb(s,c);
            System.out.println(comb);
        }
    }

    private static String getComb(String s, char[] c) {
        String comb = "";
        int len = s.length();
        for(int i=0;i<s.length();i++) {
            if(s.charAt(i) == '1') {
                comb += c[len-i-1];
            }
        }
        return comb;
    }
}
于 2013-12-05T06:19:08.120 回答
0

一种方法是不断增加一个数字，其中数字的位代表您组中的字母。例如，对于“earth”，您将通过从 1 数到 31 来遍历所有非零 5 位数字。位 0 可以表示“e”或“h”；没关系。只要保持一致。

在每个步骤中，找到设置的位，并从您的组中选择相应的字母。这是可能的子组之一。（您可能需要使用 HashSet 或其他东西来消除重复...例如，如果您的组有 2 个“e”或其他东西。）因此对于“地球”，1 可能是“e”，2 可能是“a” , 3 将是“ea”，4 将是“r”，依此类推。

当您的数字大于或等于（1 << 字母的数量）时，您已经用尽了所有可能性。

请注意，这并没有给出所有可能的排序/安排，只是可能的组。希望您已经安排好您的数据，以便您可以通过包含已排序字符的字符串进行搜索。

于 2013-12-05T04:47:51.487 回答