找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?


当前回答

我定义了左右两个字符串。一开始,左边是输入字符串,右边是“”。我递归地从左边选择所有可能的字符,并将其添加到右边的末尾。然后,在left-charAt(I)和right+charAt(I)上调用递归函数。我定义了一个类来跟踪生成的排列。

import java.util.HashSet;
import java.util.Set;

public class FindPermutations {

    static class Permutations {
        Set<String> permutations = new HashSet<>();
    }

    /**
     * Building all the permutations by adding chars of left to right one by one.
     *
     * @param left         The left string
     * @param right        The right string
     * @param permutations The permutations
     */
    private void findPermutations(String left, String right, Permutations permutations) {
        int n = left.length();
        if (n == 0) {
            permutations.permutations.add(right);
        }
        for (int i = 0; i < n; i++) {
            findPermutations(left.substring(0, i) + left.substring(i + 1, n), right + left.charAt(i), permutations);
        }
    }

    /**
     * Gets all the permutations of a string s.
     *
     * @param s The input string
     * @return all the permutations of a string s
     */
    public Permutations getPermutations(String s) {
        Permutations permutations = new Permutations();
        findPermutations(s, "", permutations);
        return permutations;
    }

    public static void main(String[] args) {
        FindPermutations findPermutations = new FindPermutations();
        String s = "ABC";
        Permutations permutations = findPermutations.getPermutations(s);
        printPermutations(permutations);
    }

    private static void printPermutations(Permutations permutations) {
        for (String p : permutations.permutations) {
            System.out.println(p);
        }
    }

}

我希望这能有所帮助。

其他回答

其中一个简单的解决方案是使用两个指针继续递归地交换字符。

public static void main(String[] args)
{
    String str="abcdefgh";
    perm(str);
}
public static void perm(String str)
{  char[] char_arr=str.toCharArray();
    helper(char_arr,0);
}
public static void helper(char[] char_arr, int i)
{
    if(i==char_arr.length-1)
    {
        // print the shuffled string 
            String str="";
            for(int j=0; j<char_arr.length; j++)
            {
                str=str+char_arr[j];
            }
            System.out.println(str);
    }
    else
    {
    for(int j=i; j<char_arr.length; j++)
    {
        char tmp = char_arr[i];
        char_arr[i] = char_arr[j];
        char_arr[j] = tmp;
        helper(char_arr,i+1);
        char tmp1 = char_arr[i];
        char_arr[i] = char_arr[j];
        char_arr[j] = tmp1;
    }
}
}

下面是一个简单的Java递归解决方案:

public static ArrayList<String> permutations(String s) {
    ArrayList<String> out = new ArrayList<String>();
    if (s.length() == 1) {
        out.add(s);
        return out;
    }
    char first = s.charAt(0);
    String rest = s.substring(1);
    for (String permutation : permutations(rest)) {
        out.addAll(insertAtAllPositions(first, permutation));
    }
    return out;
}
public static ArrayList<String> insertAtAllPositions(char ch, String s) {
    ArrayList<String> out = new ArrayList<String>();
    for (int i = 0; i <= s.length(); ++i) {
        String inserted = s.substring(0, i) + ch + s.substring(i);
        out.add(inserted);
    }
    return out;
}

让我们以输入abc为例。

从集合(["c"])中的最后一个元素(c)开始,然后将最后第二个元素(b)添加到它的前面,末尾和中间的每个可能位置,使其["bc", "cb"],然后以同样的方式将后面的下一个元素(a)添加到集合中的每个字符串中,使其:

"a" + "bc" = ["abc", "bac", "bca"]  and  "a" + "cb" = ["acb" ,"cab", "cba"] 

因此整个排列:

["abc", "bac", "bca","acb" ,"cab", "cba"]

代码:

public class Test 
{
    static Set<String> permutations;
    static Set<String> result = new HashSet<String>();

    public static Set<String> permutation(String string) {
        permutations = new HashSet<String>();

        int n = string.length();
        for (int i = n - 1; i >= 0; i--) 
        {
            shuffle(string.charAt(i));
        }
        return permutations;
    }

    private static void shuffle(char c) {
        if (permutations.size() == 0) {
            permutations.add(String.valueOf(c));
        } else {
            Iterator<String> it = permutations.iterator();
            for (int i = 0; i < permutations.size(); i++) {

                String temp1;
                for (; it.hasNext();) {
                    temp1 = it.next();
                    for (int k = 0; k < temp1.length() + 1; k += 1) {
                        StringBuilder sb = new StringBuilder(temp1);

                        sb.insert(k, c);

                        result.add(sb.toString());
                    }
                }
            }
            permutations = result;
            //'result' has to be refreshed so that in next run it doesn't contain stale values.
            result = new HashSet<String>();
        }
    }

    public static void main(String[] args) {
        Set<String> result = permutation("abc");

        System.out.println("\nThere are total of " + result.size() + " permutations:");
        Iterator<String> it = result.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

使用递归。

当输入是空字符串时,唯一的排列就是空字符串。尝试将字符串中的每个字母作为第一个字母,然后使用递归调用找到其余字母的所有排列。

import java.util.ArrayList;
import java.util.List;

class Permutation {
    private static List<String> permutation(String prefix, String str) {
        List<String> permutations = new ArrayList<>();
        int n = str.length();
        if (n == 0) {
            permutations.add(prefix);
        } else {
            for (int i = 0; i < n; i++) {
                permutations.addAll(permutation(prefix + str.charAt(i), str.substring(i + 1, n) + str.substring(0, i)));
            }
        }
        return permutations;
    }

    public static void main(String[] args) {
        List<String> perms = permutation("", "abcd");

        String[] array = new String[perms.size()];
        for (int i = 0; i < perms.size(); i++) {
            array[i] = perms.get(i);
        }

        int x = array.length;

        for (final String anArray : array) {
            System.out.println(anArray);
        }
    }
}

一个java实现打印给定字符串的所有排列,考虑重复字符,只打印唯一字符,如下所示:

import java.util.Set;
import java.util.HashSet;

public class PrintAllPermutations2
{
    public static void main(String[] args)
    {
        String str = "AAC";

    PrintAllPermutations2 permutation = new PrintAllPermutations2();

    Set<String> uniqueStrings = new HashSet<>();

    permutation.permute("", str, uniqueStrings);
}

void permute(String prefixString, String s, Set<String> set)
{
    int n = s.length();

    if(n == 0)
    {
        if(!set.contains(prefixString))
        {
            System.out.println(prefixString);
            set.add(prefixString);
        }
    }
    else
    {
        for(int i=0; i<n; i++)
        {
            permute(prefixString + s.charAt(i), s.substring(0,i) + s.substring(i+1,n), set);
        }
    }
}
}