logo标签列表

生成给定字符串的所有排列

javaalgorithm
461

如何优雅地找出字符串的所有排列组合？例如，对于字符串ba，其排列组合是ba和ab，但是对于更长的字符串，比如abcdefgh，有没有Java实现的例子呢？

3
这里有很多答案：https://dev59.com/43VD5IYBdhLWcg3wXaid。 - Marek Sapota
这是一个非常流行的问题。你可以在这里看一下：http://www.careercup.com/question?id=3861299 - JJunior
9
需要提及一个假设，字符是唯一的。例如，对于一个字符串 "aaaa" 只有一个答案。为了得到更通用的答案，您可以将字符串保存在一个集合中以避免重复。 - Afshin Moazami
1
重复字符被允许吗，还是不允许重复字符？单个字符串是否可以有多个相同字符的出现？ - Anderson Green
2
阅读理论（或者如果像我一样懒的话，可以去http://en.wikipedia.org/wiki/Permutation），并实现一个真正的算法。基本上，您可以生成元素排序的序列（它是字符串的事实是无关紧要的），并在顺序中走过，直到回到起点。避免任何涉及递归或字符串操作的内容。 - CurtainDog
显示剩余4条评论
57个回答
1

使用 ES6 实现字符串排列

使用 reduce() 方法

const permutations = str => {
  if (str.length <= 2) 
  return str.length === 2 ? [str, str[1] + str[0]] : [str];
  
  return str
    .split('')
    .reduce(
      (acc, letter, index) =>
        acc.concat(permutations(str.slice(0, index) + str.slice(index + 1)).map(val => letter + val)),
      [] 
    );
};

console.log(permutations('STR'));

1
另一种简单的方法是循环遍历字符串，选择尚未使用的字符并将其放入缓冲区，继续循环直到缓冲区大小等于字符串长度。我更喜欢这个回溯解决方案，因为：
  1. 易于理解
  2. 易于避免重复
  3. 输出已排序
这是Java代码：
List<String> permute(String str) {
  if (str == null) {
    return null;
  }

  char[] chars = str.toCharArray();
  boolean[] used = new boolean[chars.length];

  List<String> res = new ArrayList<String>();
  StringBuilder sb = new StringBuilder();

  Arrays.sort(chars);

  helper(chars, used, sb, res);

  return res;
}

void helper(char[] chars, boolean[] used, StringBuilder sb, List<String> res) {
  if (sb.length() == chars.length) {
    res.add(sb.toString());
    return;
  }

  for (int i = 0; i < chars.length; i++) {
    // avoid duplicates
    if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
      continue;
    }

    // pick the character that has not used yet
    if (!used[i]) {
      used[i] = true;
      sb.append(chars[i]);

      helper(chars, used, sb, res);

      // back tracking
      sb.deleteCharAt(sb.length() - 1);
      used[i] = false;
    }
  }
}

输入字符串: 1231

输出列表: {1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211}

注意输出结果已排序且没有重复项。

1
这里有另一种更简单的字符串排列方法。
public class Solution4 {
public static void main(String[] args) {
    String  a = "Protijayi";
  per(a, 0);

}

static void per(String a  , int start ) {
      //bse case;
    if(a.length() == start) {System.out.println(a);}
    char[] ca = a.toCharArray();
    //swap 
    for (int i = start; i < ca.length; i++) {
        char t = ca[i];
        ca[i] = ca[start];
        ca[start] = t;
        per(new String(ca),start+1);
    }

}//per

}
1
以下是一个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);
        }
    }
}
}
1

递归并非必要，甚至可以直接计算任何排列，此解决方案使用泛型来对任何数组进行排列。

这里提供了关于该算法的良好信息。

对于C#开发人员，这里提供了更有用的实现。

public static void main(String[] args) {
    String word = "12345";

    Character[] array = ArrayUtils.toObject(word.toCharArray());
    long[] factorials = Permutation.getFactorials(array.length + 1);

    for (long i = 0; i < factorials[array.length]; i++) {
        Character[] permutation = Permutation.<Character>getPermutation(i, array, factorials);
        printPermutation(permutation);
    }
}

private static void printPermutation(Character[] permutation) {
    for (int i = 0; i < permutation.length; i++) {
        System.out.print(permutation[i]);
    }
    System.out.println();
}

这个算法计算每个排列的时间和空间复杂度为O(N)。
public class Permutation {
    public static <T> T[] getPermutation(long permutationNumber, T[] array, long[] factorials) {
        int[] sequence = generateSequence(permutationNumber, array.length - 1, factorials);
        T[] permutation = generatePermutation(array, sequence);

        return permutation;
    }

    public static <T> T[] generatePermutation(T[] array, int[] sequence) {
        T[] clone = array.clone();

        for (int i = 0; i < clone.length - 1; i++) {
            swap(clone, i, i + sequence[i]);
        }

        return clone;
    }

    private static int[] generateSequence(long permutationNumber, int size, long[] factorials) {
        int[] sequence = new int[size];

        for (int j = 0; j < sequence.length; j++) {
            long factorial = factorials[sequence.length - j];
            sequence[j] = (int) (permutationNumber / factorial);
            permutationNumber = (int) (permutationNumber % factorial);
        }

        return sequence;
    }

    private static <T> void swap(T[] array, int i, int j) {
        T t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    public static long[] getFactorials(int length) {
        long[] factorials = new long[length];
        long factor = 1;

        for (int i = 0; i < length; i++) {
            factor *= i <= 1 ? 1 : i;
            factorials[i] = factor;
        }

        return factorials;
    }
}
1
字符串的排列：
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));
    }   
}
1
如果有人想要生成排列组合以便进行其他操作，而不仅仅是通过无返回值方法打印它们，请参考以下代码：
static List<int[]> permutations(int n) {

    class Perm {
        private final List<int[]> permutations = new ArrayList<>();

        private void perm(int[] array, int step) {
            if (step == 1) permutations.add(array.clone());
            else for (int i = 0; i < step; i++) {
                perm(array, step - 1);
                int j = (step % 2 == 0) ? i : 0;
                swap(array, step - 1, j);
            }
        }

        private void swap(int[] array, int i, int j) {
            int buffer = array[i];
            array[i] = array[j];
            array[j] = buffer;
        }

    }

    int[] nVector  = new int[n];
    for (int i = 0; i < n; i++) nVector [i] = i;

    Perm perm = new Perm();
    perm.perm(nVector, n);
    return perm.permutations;

}
1
//将每个字符插入到ArrayList中
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) + "  ");
    }
}
我认为这个答案并不有用，因为它没有解释，并且使用了与其他一些提供解释的答案相同的算法。 - Bernhard Barker
1
//Rotate and create words beginning with all letter possible and push to stack 1

//Read from stack1 and for each word create words with other letters at the next location by rotation and so on 

/*  eg : man

    1. push1 - man, anm, nma
    2. pop1 - nma ,  push2 - nam,nma
       pop1 - anm ,  push2 - amn,anm
       pop1 - man ,  push2 - mna,man
*/

public class StringPermute {

    static String str;
    static String word;
    static int top1 = -1;
    static int top2 = -1;
    static String[] stringArray1;
    static String[] stringArray2;
    static int strlength = 0;

    public static void main(String[] args) throws IOException {
        System.out.println("Enter String : ");
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader bfr = new BufferedReader(isr);
        str = bfr.readLine();
        word = str;
        strlength = str.length();
        int n = 1;
        for (int i = 1; i <= strlength; i++) {
            n = n * i;
        }
        stringArray1 = new String[n];
        stringArray2 = new String[n];
        push(word, 1);
        doPermute();
        display();
    }

    public static void push(String word, int x) {
        if (x == 1)
            stringArray1[++top1] = word;
        else
            stringArray2[++top2] = word;
    }

    public static String pop(int x) {
        if (x == 1)
            return stringArray1[top1--];
        else
            return stringArray2[top2--];
    }

    public static void doPermute() {

        for (int j = strlength; j >= 2; j--)
            popper(j);

    }

    public static void popper(int length) {
        // pop from stack1 , rotate each word n times and push to stack 2
        if (top1 > -1) {
            while (top1 > -1) {
                word = pop(1);
                for (int j = 0; j < length; j++) {
                    rotate(length);
                    push(word, 2);
                }
            }
        }
        // pop from stack2 , rotate each word n times w.r.t position and push to
        // stack 1
        else {
            while (top2 > -1) {
                word = pop(2);
                for (int j = 0; j < length; j++) {
                    rotate(length);
                    push(word, 1);
                }
            }
        }

    }

    public static void rotate(int position) {
        char[] charstring = new char[100];
        for (int j = 0; j < word.length(); j++)
            charstring[j] = word.charAt(j);

        int startpos = strlength - position;
        char temp = charstring[startpos];
        for (int i = startpos; i < strlength - 1; i++) {
            charstring[i] = charstring[i + 1];
        }
        charstring[strlength - 1] = temp;
        word = new String(charstring).trim();
    }

    public static void display() {
        int top;
        if (top1 > -1) {
            while (top1 > -1)
                System.out.println(stringArray1[top1--]);
        } else {
            while (top2 > -1)
                System.out.println(stringArray2[top2--]);
        }
    }
}
1
public class StringPermutation {

// Function to print all the permutations of str
static void printPermutn(String str, String ans) {

    // If string is empty
    if (str.length() == 0) {
        System.out.print(ans + " ");
        return;
    }

    for (int i = 0; i < str.length(); i++) {

        // ith character of str
        char ch = str.charAt(i);

        // Rest of the string after excluding
        // the ith character
        String ros = str.substring(0, i) + str.substring(i + 1);

        // Recurvise call
        printPermutn(ros, ans + ch);
    }
}


public static void main(String[] args) {
    String s = "ABC";
    printPermutn(s, "");
}

}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接