0

我正在寻找一种算法（最佳）来生成单词的所有可能组合。

例如：

给定单词love，将输出以下内容：

生成词：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

给定单词bell（注意关于重复l），将输出以下内容：

生成词：12 bell blel blle ebll elbl ellb lbel lble lebl lelb llbe lleb

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

4

3 回答 3

1

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

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

Java 代码：（源自基本排列生成器）

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);
         }
      }
   }
}

测试。

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

于 2013-07-17T08:18:46.480 回答
1
  1. 取单词中的字母总数n，然后找到n！。
  2. 计算每个字母出现的次数。对于重复多次的每个字母，除以（重复次数）！

示例：“香蕉”

2 个 n，3 个 a，共 6 个字母

答案 = 6!/(2!*3!) = 60

于 2013-07-17T20:16:26.217 回答
0

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

于 2015-02-16T14:28:21.383 回答