找出弦的所有排列的优雅方法是什么。例如,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);
        }
    }

}

我希望这能有所帮助。

其他回答

使用递归。

依次尝试每个字母作为第一个字母,然后使用递归调用找到剩余字母的所有排列。 基本情况是,当输入是空字符串时,唯一的排列就是空字符串。

使用Es6的字符串排列

使用reduce()方法

Const排列= STR => { If (str.length <= 2) 返回str.length === 2 ?[str, str[1] + str[0]]: [str]; 返回str .split (") .reduce ( (acc, letter, index) => acc.concat(排列(str。Slice (0, index) + str.slice(index + 1))。Map (val =>字母+ val)), [] ); }; console.log(排列(STR));

Java中一个非常基本的解决方案是使用递归+设置(以避免重复),如果你想存储和返回解决方案字符串:

public static Set<String> generatePerm(String input)
{
    Set<String> set = new HashSet<String>();
    if (input == "")
        return set;

    Character a = input.charAt(0);

    if (input.length() > 1)
    {
        input = input.substring(1);

        Set<String> permSet = generatePerm(input);

        for (String x : permSet)
        {
            for (int i = 0; i <= x.length(); i++)
            {
                set.add(x.substring(0, i) + a + x.substring(i));
            }
        }
    }
    else
    {
        set.add(a + "");
    }
    return set;
}

//循环'整个字符数组,并保持'i'作为你的排列的基础,并像你交换[ab, ba]一样继续寻找组合

public class Permutation {
    //Act as a queue
    private List<Character> list;
    //To remove the duplicates
    private Set<String> set = new HashSet<String>();

    public Permutation(String s) {
        list = new LinkedList<Character>();
        int len = s.length();
        for(int i = 0; i < len; i++) {
            list.add(s.charAt(i));
        }
    }

    public List<String> getStack(Character c, List<Character> list) {
        LinkedList<String> stack = new LinkedList<String>();
        stack.add(""+c);
        for(Character ch: list) {
            stack.add(""+ch);
        }

        return stack;
    }

    public String printCombination(String s1, String s2) {
        //S1 will be a single character
        StringBuilder sb = new StringBuilder();
        String[] strArr = s2.split(",");
        for(String s: strArr) {
            sb.append(s).append(s1);
            sb.append(",");
        }       
        for(String s: strArr) {
            sb.append(s1).append(s);
            sb.append(",");
        }

        return sb.toString();
    }

    public void printPerumtation() {
        int cnt = list.size();

        for(int i = 0; i < cnt; i++) {
            Character c = list.get(0);
            list.remove(0);
            List<String> stack = getStack(c, list);

            while(stack.size() > 1) {
                //Remove the top two elements
                String s2 = stack.remove(stack.size() - 1);
                String s1 = stack.remove(stack.size() - 1);
                String comS = printCombination(s1, s2);
                stack.add(comS);
            }

            String[] perms = (stack.remove(0)).split(",");
            for(String perm: perms) {
                set.add(perm);
            }

            list.add(c);
        }

        for(String s: set) {
            System.out.println(s);
        }
    }
}
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));
    }
}

(通过Java编程入门)