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


当前回答

使用递归。

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

其他回答

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class hello {
    public static void main(String[] args) throws IOException {
        hello h = new hello();
        h.printcomp();
    }
      int fact=1;
    public void factrec(int a,int k){
        if(a>=k)
        {fact=fact*k;
        k++;
        factrec(a,k);
        }
        else
        {System.out.println("The string  will have "+fact+" permutations");
        }
        }
    public void printcomp(){
        String str;
        int k;
        Scanner in = new Scanner(System.in);
        System.out.println("enter the string whose permutations has to b found");
        str=in.next();
        k=str.length();
        factrec(k,1);
        String[] arr =new String[fact];
        char[] array = str.toCharArray();
        while(p<fact)
        printcomprec(k,array,arr);
            // if incase u need array containing all the permutation use this
            //for(int d=0;d<fact;d++)         
        //System.out.println(arr[d]);
    }
    int y=1;
    int p = 0;
    int g=1;
    int z = 0;
    public void printcomprec(int k,char array[],String arr[]){
        for (int l = 0; l < k; l++) {
            for (int b=0;b<k-1;b++){
            for (int i=1; i<k-g; i++) {
                char temp;
                String stri = "";
                temp = array[i];
                array[i] = array[i + g];
                array[i + g] = temp;
                for (int j = 0; j < k; j++)
                    stri += array[j];
                arr[z] = stri;
                System.out.println(arr[z] + "   " + p++);
                z++;
            }
            }
            char temp;
            temp=array[0];
            array[0]=array[y];
            array[y]=temp;
            if (y >= k-1)
                y=y-(k-1);
            else
                y++;
        }
        if (g >= k-1)
            g=1;
        else
            g++;
    }

}

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

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) + "  ");
    }
}

串的排列:

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));
    }   
}
//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--]);
        }
    }
}

这是一个具有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);

}

}