获取字符串或组合的所有可能排列，包括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 ());
}

从此处使用CombinationGenerator类，它将返回每个唯一的4个字符的组合，例如：

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

但是，我希望可以使用给定的字符创建所有可能的字符串。例如：

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

我已经尝试过能够找到或想出的每种递归和置换方法，但是除了生成如上所述的所有组合，然后生成每种组合的每种置换，我都想做更多的事情，但是我无法工作了解如何使用重复的字符创建一组组合。

任何帮助，甚至只是有关如何实现的理论都将有所帮助。

Answer 1

您将必须对要获得的功能进行更具体的说明。“组合”有许多不同的定义，您还没有指定要组合还是无序。

从数学上讲，如果您有n个元素并希望列出k个元素（按重复顺序排列），则可以

n ^ k

组合。（在您的原始示例中，6 ^ 4 = 1296个组合，很多！）。但是，如果您有n个元素，并且想要一个k个元素的MULTISET（无序重复），那么您可以

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

组合，并且很难枚举。

如果k很小，则可以生成数量有限的for循环的第一个，但是随着k的增加，这很快变得很麻烦。这强烈暗示需要使用RECURSIVE方法：

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个组合！）。

如果该方法使您感到困惑（这是递归方法，那么很难遵循），或者如果您想解决第二个组合问题，请随时提出。另外，此方法效率不高，因为它会重新计算所有子列表的组合，因此对于真正的长列表而言，它是不可行的。如果您确实想要效率，可以将已经计算出的元组存储在全局列表中。