用于生成单词的所有组合（字母顺序）的最优算法

我正在寻找用于生成单词的所有可能组合的算法（最佳）。用于生成单词的所有组合（字母顺序）的最优算法

例如：

鉴于字爱，以下将输出：

生成词：24 elov ELVO eolv eovl 器EV10 EVOL leov levo loev 爱 lveo lvoe oelv oevl OLEV olve OVEL ovle VELO VEOL vleo vloe voel 田鼠

所给词钟（注意对重复l），将输出以下内容：

生成的话：12 钟 BLEL blle ebll ELBL ellb lbel lble LEBL lelb llbe lleb

我有自己的算法生成所有组合一个给定的单词。我基本上实现了组合树。这是非常全面的，但它消耗了大量的空间和时间。

来源

2013-07-17 Lynnell Emmanuel Neri

什么是组合树？递归生成组合？ – Aravind

也许你想按字典顺序排序并在可能的情况下应用一些“nextWord”功能？ – Herokiller

我认为更适合的术语是“多重排列”。 https://en.wikipedia.org/wiki/Permutation – rliu

长后！时间，我终于得到了我的问题的答案。我使用PHP作为我的编程语言（因为它是我的选择，而不是其他任何东西），我使用了Pear Package: Math Combinatorics。

来源

2015-02-16 14:28:21

可以通过为每个字符交换该字符与第一个字符并通过排除第一个字符来递归来生成置换（不包括重复约束）。

现在，如果我们想排除重复项，我们只需确保我们不会将相同的字符放在第一个位置两次。这样做可以通过对字符进行排序（使重复字符彼此相邻）并跳过与之前的字符相同的字符或与目标位置上的字符相同的字符来完成。

Java代码：（来自a basic permutation generator派生）

import java.util.Arrays; 
import java.util.Scanner; 

public class NewMain 
{ 
    public static void main(String[] args) 
    { 
     Scanner sc = new Scanner(System.in); 
     System.out.println("Enter the string:"); 
     String s = sc.nextLine(); 
     char[] c = s.toCharArray(); 
     Arrays.sort(c); 

     System.out.println("Here are all the permutations:"); 
     NewMain.c = c; 
     count = 0; 
     permutation(0); 
     System.out.println("Number of permutations = " + count); 
    } 

    static char[] c; 
    static int count; 

    static void swap(int pos1, int pos2) 
    { 
     char temp = c[pos1]; 
     c[pos1] = c[pos2]; 
     c[pos2] = temp; 
    } 

    public static void permutation(int start) 
    { 
     if (start == c.length) 
     { 
     System.out.println(c); 
     count++; 
     } 

     for (int i = start; i < c.length; i++) 
     { 
     if (i == start || (c[i] != c[i-1] && c[i] != c[start])) 
     { 
      swap(start, i); 
      permutation(start + 1); 
      swap(start, i); 
     } 
     } 
    } 
}

Test。

现在如果还有太许多重复字符，这仍然不是特别有效。我可以想到的一种改进方法是对每个字符进行计数（可能是链接列表（链接列表的计数）），以便快速删除已达到0的计数并插入它们之后回来），和上面类似，我们从左到右生成字符，在每个递归步骤中只处理每个计数一次，跳过重复项。

来源

2013-07-17 08:18:46 Dukeling

取出单词中字母的总数n，并找到n !.
统计每个字母的出现次数。对于不止一次重复的每个字母，除以（重复次数）！

实施例： '香蕉'

2 N的，3次的，总共6个字母

回答= 6 /（2 * 3！）= 60

来源

2013-07-17 20:16:26 enderx1x

用于生成单词的所有组合（字母顺序）的最优算法

回答

相关问题