获取包含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的LIST(按重复排序),那就给你了

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种组合!).

如果方法混淆了你(这是一个递归方法,所以它有点难以理解)或者如果你想要解决第二个组合问题,请随意问.此外,这种方法效率有点低,因为它重新计算了所有子列表的组合,因此对于很长的列表来说它不可行.如果你真的想要效率,你可以将已经计算过的元组存储在全局列表中.

Answer 2

如果你想在Python中使用它,你不需要知道如何编程!

import itertools
for p in itertools.permutations('abc123', 4):
    print ''.join(p)