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


当前回答

下面是两个c#版本(仅供参考): 1. 打印所有排列 2. 返回所有排列

算法的基本要点是(可能下面的代码更直观-尽管如此,下面的代码是做什么的一些解释): -从当前索引到集合的其余部分,交换当前索引处的元素 -递归地获得下一个索引中剩余元素的排列 -恢复秩序,通过重新交换

注意:上述递归函数将从起始索引中调用。

private void PrintAllPermutations(int[] a, int index, ref int count)
        {
            if (index == (a.Length - 1))
            {
                count++;
                var s = string.Format("{0}: {1}", count, string.Join(",", a));
                Debug.WriteLine(s);
            }
            for (int i = index; i < a.Length; i++)
            {
                Utilities.swap(ref a[i], ref a[index]);
                this.PrintAllPermutations(a, index + 1, ref count);
                Utilities.swap(ref a[i], ref a[index]);
            }
        }
        private int PrintAllPermutations(int[] a)
        {
            a.ThrowIfNull("a");
            int count = 0;
            this.PrintAllPermutations(a, index:0, count: ref count);
            return count;
        }

版本2(与上面相同-但返回排列而不是打印)

private int[][] GetAllPermutations(int[] a, int index)
        {
            List<int[]> permutations = new List<int[]>();
            if (index == (a.Length - 1))
            {
                permutations.Add(a.ToArray());
            }

            for (int i = index; i < a.Length; i++)
            {
                Utilities.swap(ref a[i], ref a[index]);
                var r = this.GetAllPermutations(a, index + 1);
                permutations.AddRange(r);
                Utilities.swap(ref a[i], ref a[index]);
            }
            return permutations.ToArray();
        }
        private int[][] GetAllPermutations(int[] p)
        {
            p.ThrowIfNull("p");
            return this.GetAllPermutations(p, 0);
        }

单元测试

[TestMethod]
        public void PermutationsTests()
        {
            List<int> input = new List<int>();
            int[] output = { 0, 1, 2, 6, 24, 120 };
            for (int i = 0; i <= 5; i++)
            {
                if (i != 0)
                {
                    input.Add(i);
                }
                Debug.WriteLine("================PrintAllPermutations===================");
                int count = this.PrintAllPermutations(input.ToArray());
                Assert.IsTrue(count == output[i]);
                Debug.WriteLine("=====================GetAllPermutations=================");
                var r = this.GetAllPermutations(input.ToArray());
                Assert.IsTrue(count == r.Length);
                for (int j = 1; j <= r.Length;j++ )
                {
                    string s = string.Format("{0}: {1}", j,
                        string.Join(",", r[j - 1]));
                    Debug.WriteLine(s);
                }
                Debug.WriteLine("No.OfElements: {0}, TotalPerms: {1}", i, count);
            }
        }

其他回答

我定义了左右两个字符串。一开始,左边是输入字符串,右边是“”。我递归地从左边选择所有可能的字符,并将其添加到右边的末尾。然后,在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);
        }
    }

}

我希望这能有所帮助。

改进的代码相同

    static String permutationStr[];
    static int indexStr = 0;

    static int factorial (int i) {
        if (i == 1)
            return 1;
        else
            return i * factorial(i-1);
    }

    public static void permutation(String str) {
        char strArr[] = str.toLowerCase().toCharArray();
        java.util.Arrays.sort(strArr);

        int count = 1, dr = 1;
        for (int i = 0; i < strArr.length-1; i++){
            if ( strArr[i] == strArr[i+1]) {
                count++;
            } else {
                dr *= factorial(count);
                count = 1;
            }       
        }
        dr *= factorial(count);

        count = factorial(strArr.length) / dr;

        permutationStr = new String[count];

        permutation("", str);

        for (String oneStr : permutationStr){
            System.out.println(oneStr);
        }
    }

    private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0) {
            for (int i = 0; i < indexStr; i++){
                if(permutationStr[i].equals(prefix))
                    return;
            }        
            permutationStr[indexStr++] = prefix;
        } else {
            for (int i = 0; i < n; i++) {
                permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
            }
        }
    }

这是一个具有O(n!)时间复杂度的算法,具有纯递归和直观。

public class words {
static String combinations;
public static List<String> arrlist=new ArrayList<>();
public static void main(String[] args) {
    words obj = new words();

    String str="premandl";
    obj.getcombination(str, str.length()-1, "");
    System.out.println(arrlist);

}


public void getcombination(String str, int charIndex, String output) {

    if (str.length() == 0) {
        arrlist.add(output);
        return ;
    }

    if (charIndex == -1) {
        return ;
    }

    String character = str.toCharArray()[charIndex] + "";
    getcombination(str, --charIndex, output);

    String remaining = "";

    output = output + character;

    remaining = str.substring(0, charIndex + 1) + str.substring(charIndex + 2);

    getcombination(remaining, remaining.length() - 1, output);

}

}

//插入每个字符到数组列表中

static ArrayList al = new ArrayList();

private static void findPermutation (String str){
    for (int k = 0; k < str.length(); k++) {
        addOneChar(str.charAt(k));
    }
}

//insert one char into ArrayList
private static void addOneChar(char ch){
    String lastPerStr;
    String tempStr;
    ArrayList locAl = new ArrayList();
    for (int i = 0; i < al.size(); i ++ ){
        lastPerStr = al.get(i).toString();
        //System.out.println("lastPerStr: " + lastPerStr);
        for (int j = 0; j <= lastPerStr.length(); j++) {
            tempStr = lastPerStr.substring(0,j) + ch + 
                    lastPerStr.substring(j, lastPerStr.length());
            locAl.add(tempStr);
            //System.out.println("tempStr: " + tempStr);
        }
    }
    if(al.isEmpty()){
        al.add(ch);
    } else {
        al.clear();
        al = locAl;
    }
}

private static void printArrayList(ArrayList al){
    for (int i = 0; i < al.size(); i++) {
        System.out.print(al.get(i) + "  ");
    }
}
import java.io.*;
public class Anagram {

public static void main(String[] args) {
      java.util.Scanner sc=new java.util.Scanner(System.in);
            PrintWriter p=new PrintWriter(System.out,true);
            p.println("Enter Word");
            String a[],s="",st;boolean flag=true;
            int in[],n,nf=1,i,j=0,k,m=0;
            char l[];
            st=sc.next();
            p.println("Anagrams");
            p.println("1 . "+st);
            l=st.toCharArray();
            n=st.length();
            for(i=1;i<=n;i++){
                nf*=i;
            }

            i=1;
            a=new String[nf];
            in=new int[n];
            a[0]=st;
            while(i<nf){
                for(m=0;m<n;m++){
                    in[m]=n;
                }j=0;
                while(j<n){
                    k=(int)(n*Math.random());

                    for(m=0;m<=j;m++){
                        if(k==in[m]){
                            flag=false;
                            break;          
                        }
                    }
                    if(flag==true){
                        in[j++]=k;
                    }flag=true;
                }s="";
                for(j=0;j<n;j++){
                    s+=l[in[j]];
                }

                //Removing same words
                for(m=0;m<=i;m++){
                        if(s.equalsIgnoreCase(a[m])){
                            flag=false;
                            break;          
                        }
                    }
                    if(flag==true){
                        a[i++]=s;
                        p.println(i+" . "+a[i-1]);
                    }flag=true;

            }

    }
}