java - 获取字符串或组合的所有可能排列，包括 Java 中的重复字符

Question

我一直在尝试生成一个列表，其中包含所有可能的 4 个字符的字符串，这些字符串可以由任何给定的字符集组成。我使用了一个函数从一组字符中生成每 4 个字符的组合，但每个字符只使用过一次。我需要使用给定字符集的所有可能组合，例如:

String[] elements = {"a", "b", "c", "1", "2", "3"};
int[] indices;
CombinationGenerator x = new CombinationGenerator (elements.length, 4);
StringBuffer combination;
while (x.hasMore ()) {
  combination = new StringBuffer ();
  indices = x.getNext ();
  for (int i = 0; i < indices.length; i++) {
      combination.append (elements[indices[i]]);
  }
  System.out.println (combination.toString ());
}

使用 here 中的 CombinationGenerator 类, 这将返回每个唯一的 4 字符组合，例如:

'abcd' , 'abc1', 'acb2', 'acb1'

但是，我想要使用给定字符创建的所有可能的字符串。例如:

'aaaa', 'aaab', 'abc1', 'aac1', '11c2'

我已经尝试了我能够找到或想出的每一种递归和排列方法，但除了像上面那样生成所有组合，然后生成每个组合的每个排列之外，我很难得到任何进一步的方法，但我可以'找出如何使用重复字符创建一组组合。

任何帮助，甚至只是关于如何完成的理论都会有所帮助。

Answer 1

您必须更具体地说明您希望函数获得什么。 “组合”有很多不同的定义，您还没有指定您想要有序组合还是无序组合。

从数学上讲，如果您有 n 个元素并且想要一个包含 k 个元素的 LIST(按重复顺序排列)，这会给您

n ^ k

组合。 (原始示例中有 6 ^ 4 = 1296 种组合，数量很多!)。但是，如果您有 n 个元素并且想要一个包含 k 个元素的 MULTISET(无序且重复)，那么您可以

(n + k - 1)! / (k! * (n - 1)!)

组合和是一个更难的枚举。

如果 k 很小，您可以使用有限数量的 for 循环生成第一个，但随着 k 的增长，这会很快变得很麻烦。这强烈暗示需要递归方法:

public static String[] getAllLists(String[] elements, int lengthOfList)
{
    //initialize our returned list with the number of elements calculated above
    String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)];

    //lists of length 1 are just the original elements
    if(lengthOfList == 1) return elements; 
    else
    {
        //the recursion--get all lists of length 3, length 2, all the way up to 1
        String[] allSublists = getAllLists(elements, lengthOfList - 1);

        //append the sublists to each element
        int arrayIndex = 0;

        for(int i = 0; i < elements.length; i++)
        {
            for(int j = 0; j < allSublists.length; j++)
            {
                //add the newly appended combination to the list
                allLists[arrayIndex] = elements[i] + allSublists[j];
                arrayIndex++;
            }
        }

        return allLists;
    }
}

此方法不仅会生成所有列表，而且会按顺序枚举它们。也就是说，输出将是

aaaa
aaab
aaac
aaa1
aaa2
aaa3
aaba
aabb
aabc
aab1
...
3323
333a
333b
333c
3331
3332
3333

使用您的原始输入。它还可以生成任意长度的单词(要非常小心!仅使用长度为 8 的单词，我就得到了 1,679,616 种组合!)。

如果该方法让您感到困惑(这是一种递归方法，因此有点难以遵循)或者如果您想解决第二个组合问题，请随时提出。此外，此方法有些低效，因为它会重新计算所有子列表的组合，因此它不适用于非常长的列表。如果您真的想要效率，您可以将已计算的元组存储在全局列表中。