优化算法生成一个单词的所有组合（顺序字母事项） [英] Optimal algorithm for generating all combinations (order of letter matters) of a word
问题描述
我在寻找一种算法（最佳），用于产生一个单词的所有可能的组合。
例如：
由于字爱，以下将输出：
产生的字：24 elov ELVO eolv eovl evlo EVOL leov 左旋 loev 爱 lveo lvoe oelv oevl OLEV olve OVEL ovle VELO VEOL vleo vloe voel 田鼠
由于字钟（注意有关该重复的→的），以下将输出：
产生的字：12 钟 BLEL blle ebll elbl ellb lbel lble LEBL lelb llbe lleb
我有我自己的算法生成一个给定单词的所有组合。我基本上实现组合树。这也是迄今为止多个COM prehensive但它消耗了大量的时间和空间。
一个可以产生置换（不包括重复的约束），对于每一个字符，交换该字符的第一个字符和递归排除的第一个字符。
现在，如果我们要排除重复，我们只需要确保我们不要把相同的字符在第一个位置两次。这样做可以通过排序字符（因此重复的字符是一个接一个），并跳过任意字符那以前一样它的一个或相同的字符在目标位置来进行。
Java的code：（从
进口java.util.Arrays中;
进口java.util.Scanner中;
公共类NewMain
{
公共静态无效的主要（字串[] args）
{
扫描仪SC =新的扫描仪（System.in）;
的System.out.println（请输入字符串：）;
字符串s = sc.nextLine（）;
的char [] C = s.toCharArray（）;
Arrays.sort（C）;
的System.out.println（这是所有的排列：）;
NewMain.c = C;
计数= 0;
置换（0）;
的System.out.println（+计数排列=数）;
}
静态的char []℃;
静态诠释计数;
静态无效掉期（INT POS1，INT POS2）
{
字符临时= C [POS1]
C [POS1] = C [POS2]
C [POS2] =气温;
}
公共静态无效的置换（INT启动）
{
如果（开始== c.length）
{
的System.out.println（C）;
算上++;
}
的for（int i =启动; I＆LT; c.length;我++）
{
如果（我==开始||（C [i] = C [I-1]安培;！＆安培;！C [i] = C [开始]））
{
掉期（启动，I）;
置换（START + 1）;
掉期（启动，I）;
}
}
}
}
测试。
现在这仍然不是特别有效的，如果还有的太的许多重复的字符。我能想到的改进方法之一是通过具有计数的每个字符（也许在一个链表（计数的链接列表的形式），所以我们能迅速清除已经达到0计数，并把它们插入回之后），并类似于上面，我们产生从左至右，通过仅处理在每个递归步骤每次计数一次跳过重复。字符
I am looking for an algorithm (optimal) for generating all possible combinations of a word.
For example:
Given the word love, the following would be outputted:
Generated words: 24 elov elvo eolv eovl evlo evol leov levo loev love lveo lvoe oelv oevl olev olve ovel ovle velo veol vleo vloe voel vole
Given the word bell (note about the repeating l), the following would be outputted:
Generated words: 12 bell blel blle ebll elbl ellb lbel lble lebl lelb llbe lleb
I have my own algorithm in generating all combinations of a given word. I am basically implementing a combination tree. This is so far more comprehensive yet it consumes a lot of space and time.
One can generate permutations (excluding the duplicate constraint) by, for each character, swapping that character with the first character and recursing by excluding the first character.
Now if we want to exclude duplicates, we simply need to make sure we don't put the same character in the first position twice. Doing this can be done by sorting the characters (so the duplicate characters are next to one another) and skipping over any character that's the same as the one before it or the same as the character at the target position.
Java code: (derived from 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.
Now this is still not particularly efficient if there are too many duplicate characters. One way I can think of to improve on this is by having a count for each character (maybe in the form of a linked-list (a linked-list of counts) so we can quickly remove counts that have reached 0, and insert them back afterwards) and, similar to above, we generate characters from left to right, skipping over duplicates by only processing each count once at each recursive step.
这篇关于优化算法生成一个单词的所有组合（顺序字母事项）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
