无法生成字符串的所有排列(迭代)

Question

所以我正在进行一些Java练习,最近引起我注意的一个是尝试生成String使用迭代的所有排列.在线有很多例子 - 但是,很多例子看起来非常复杂,我无法遵循.

我尝试使用自己的方法,当使用长度为3的字符串进行测试时,它可以正常工作.方法是(对于每个字母)继续沿着字符串移动一个字母,用它前面的任何字母交换它.例如

index:  012
string: abc 

(iteration 1) swap 'a' (index 0) with letter after it 'b' (index 0+1) : bac
(iteration 2) swap 'a' (index 1) with letter after it 'c' (index 1+1) : bca
(iteration 3) swap 'a' (index 2) with letter after it 'b' (index 0)   : acb
current permutations: abc (original), bac, bca, acb

(iteration 3) swap 'b' (index 1) with letter after it 'c' (index 1+1) : acb
(iteration 4) swap 'b' (index 2) with letter after it 'a' (index 0)   : bca
(iteration 5) swap 'b' (index 0) with letter after it 'c' (index 1)   : cba
current permutations: abc (original), bac, bca, acb, acb, cba

...

这就是我在Java中实现它的方式:

String str = "abc"; // string to permute
char[] letters = str.toCharArray(); // split string into char array
int setLength = factorial(letters.length); // amount of permutations = n!
HashSet<String> permutations = new HashSet<String>(); // store permutations in Set to avoid duplicates
permutations.add(str); // add original string to set

// algorithm as described above
for (int i = 0; i < setLength; i++) {
    for (int j = 0; j < letters.length; j++) {
        int k;
        if (j == letters.length - 1) {
            k = 0;
        } else {
            k = j + 1;
        }
        letters = swap(letters, j, k);
        String perm = new String(letters);
        permutations.add(perm);
    }
} 

问题是如果我输入一个长度为4的字符串,我最终会得到12个排列(4x3) - 如果我输入一个长度为5的字符串,我最终会得到20个排列(5x4).

我可以对此算法进行简单修改以获得所有可能的排列吗？或者这种特殊方法仅适用于长度为3的字符串？

感谢任何反馈!

Answer 1

假设输入是"abcd".这就是您的算法的工作方式

BACD

BACD

BCAD

BCDA

如果仔细观察,"a"将被定位在所有索引处,随后的连续字母将被替换为"a".但是,在您的算法生成"bacd"之后 - 它也应该跟着"badc",这将从您的输出中丢失.

对于长度为4的字符串,当您将排列数计算为阶乘时,您可以理解第一个位置可以被4个字符占用,然后是3个,2个和1个.但是,在前两个位置被占用的情况下"ba"第三个位置有两种可能性,即c和d.当您的算法正确找到"cd"时,它无法找到"dc" - 因为,循环不会将问题分解为更多的子问题,即"cd"有两个排列,分别为"cd"和"dc".

因此,随着字符串长度的增加,您的排列和实际答案的数量差异将会增加.

为了轻松地将问题分解为子问题并解决它,许多算法使用递归.

但是,您可以查看生成字符串的所有可能排列的列表,以获得良好的迭代答案.

此外,随着字符串长度的增加,不建议计算排列数.