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


当前回答

使用位操作可以很容易地做到这一点。“我们都知道,任何给定的有N个元素的集合有2N个可能的子集。如果我们用一个位来表示子集中的每个元素呢?位可以是0或1,因此我们可以用它来表示对应的元素是否属于这个给定的子集。所以每个位模式代表一个子集。”(复制文本)

private void getPermutation(String str)
        {
            if(str==null)
                return;
            Set<String> StrList = new HashSet<String>();
            StringBuilder strB= new StringBuilder();
            for(int i = 0;i < (1 << str.length()); ++i)
            {
                strB.setLength(0); //clear the StringBuilder
                for(int j = 0;j < str.length() ;++j){
                    if((i & (1 << j))>0){  // to check whether jth bit is set
                        strB.append(str.charAt(j));
                    }
                }
                if(!strB.toString().isEmpty())
                    StrList.add(strB.toString());
            }
            System.out.println(Arrays.toString(StrList.toArray()));
        }

其他回答

使用递归。

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

串的排列:

public static void main(String args[]) {
    permu(0,"ABCD");
}

static void permu(int fixed,String s) {
    char[] chr=s.toCharArray();
    if(fixed==s.length())
        System.out.println(s);
    for(int i=fixed;i<s.length();i++) {
        char c=chr[i];
        chr[i]=chr[fixed];
        chr[fixed]=c;
        permu(fixed+1,new String(chr));
    }   
}
/** Returns an array list containing all
 * permutations of the characters in s. */
public static ArrayList<String> permute(String s) {
    ArrayList<String> perms = new ArrayList<>();
    int slen = s.length();
    if (slen > 0) {
        // Add the first character from s to the perms array list.
        perms.add(Character.toString(s.charAt(0)));

        // Repeat for all additional characters in s.
        for (int i = 1;  i < slen;  ++i) {

            // Get the next character from s.
            char c = s.charAt(i);

            // For each of the strings currently in perms do the following:
            int size = perms.size();
            for (int j = 0;  j < size;  ++j) {

                // 1. remove the string
                String p = perms.remove(0);
                int plen = p.length();

                // 2. Add plen + 1 new strings to perms.  Each new string
                //    consists of the removed string with the character c
                //    inserted into it at a unique location.
                for (int k = 0;  k <= plen;  ++k) {
                    perms.add(p.substring(0, k) + c + p.substring(k));
                }
            }
        }
    }
    return perms;
}

没有递归的Java实现

public Set<String> permutate(String s){
    Queue<String> permutations = new LinkedList<String>();
    Set<String> v = new HashSet<String>();
    permutations.add(s);

    while(permutations.size()!=0){
        String str = permutations.poll();
        if(!v.contains(str)){
            v.add(str);
            for(int i = 0;i<str.length();i++){
                String c = String.valueOf(str.charAt(i));
                permutations.add(str.substring(i+1) + c +  str.substring(0,i));
            }
        }
    }
    return v;
}

下面是一个java实现:

/* All Permutations of a String */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Complexity O(n*n!) */
class Ideone
{
     public static ArrayList<String> strPerm(String str, ArrayList<String> list)
     {
        int len = str.length();
        if(len==1){
            list.add(str);
            return list;
        }

        list = strPerm(str.substring(0,len-1),list);
        int ls = list.size();
        char ap = str.charAt(len-1);
        for(int i=0;i<ls;i++){
            String temp = list.get(i);
            int tl = temp.length();
            for(int j=0;j<=tl;j++){
                list.add(temp.substring(0,j)+ap+temp.substring(j,tl));  
            }
        }

        while(true){
            String temp = list.get(0);
            if(temp.length()<len)
                list.remove(temp);
            else
                break;
        }

        return list;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        String str = "abc";
        ArrayList<String> list = new ArrayList<>();

        list = strPerm(str,list);
        System.out.println("Total Permutations : "+list.size());
        for(int i=0;i<list.size();i++)
            System.out.println(list.get(i));

    }
}

http://ideone.com/nWPb3k