代码之家 › 专栏 › 技术社区 › Chander Shivdasani

排列字符串

permutation algorithm string java

Chander Shivdasani · 技术社区 · 13 年前

给定字符串,打印其所有排列。为了做到这一点,我想出了以下程序。

public static char[] swap(char[] input, int i, int j) {
        char temp;
        temp = input[i];
        input[i] = input[j];
        input[j] = temp;

        return input;

    }

    /**
     * 
     * @param args
     */

    public static void permuteStrings(char[] inputString, int start, int finish ) {
        //Base case: When there is only single element, print the string
        if(start == finish) 
            System.out.println(inputString);
        else {
            //Recursive case: Swap first element with all the elements and permute on the 
                           // rest of string.
            for(int i = start; i <= finish; i++) {
                inputString = swap(inputString, start, i);
                permuteStrings(inputString, i + 1, finish);
                inputString = swap(inputString,start, i); //restoring the original string
            }
        }
    }

但是,对于给定的输入ABC,它打印的所有内容都是

ABC
BAC

我似乎搞不清问题出在哪里

2 回复 | 直到 13 年前

Chander Shivdasani 13 年前

解决了问题。问题出现在函数调用中:

permuteStrings(inputString, i + 1, finish); 。

正确的方法是:

permuteStrings(inputString, start + 1, finish);

Nikhil_10 12 年前

使用递归

public static void permutation(String str) 
{ 
permutation("", str); 
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) 
 System.out.println(prefix);
else 
{
    for (int i = 0; i < n; i++)
     permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}

推荐文章