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


当前回答

一个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);
        }
    }
}
}

其他回答

在python中

def perms(in_str, prefix=""):
if not len(in_str) :
    print(prefix)
else:        
    for i in range(0, len(in_str)):
        perms(in_str[:i] + in_str[i + 1:], prefix + in_str[i])

perms('ASD')

递归Python解决方案

def permute(input_str):
    _permute("", input_str)

def _permute(prefix, str_to_permute):
    if str_to_permute == '':
        print(prefix)

    else:
        for i in range(len(str_to_permute)): 
            _permute(prefix+str_to_permute[i], str_to_permute[0:i] + str_to_permute[i+1:])

if __name__ == '__main__':
    permute('foobar')

倒计时Quickperm算法的通用实现,表示#1(可伸缩,非递归)。

/**
 * Generate permutations based on the
 * Countdown <a href="http://quickperm.org/">Quickperm algorithm</>.
 */
public static <T> List<List<T>> generatePermutations(List<T> list) {
    List<T> in = new ArrayList<>(list);
    List<List<T>> out = new ArrayList<>(factorial(list.size()));

    int n = list.size();
    int[] p = new int[n +1];
    for (int i = 0; i < p.length; i ++) {
        p[i] = i;
    }
    int i = 0;
    while (i < n) {
        p[i]--;
        int j = 0;
        if (i % 2 != 0) { // odd?
            j = p[i];
        }
        // swap
        T iTmp = in.get(i);
        in.set(i, in.get(j));
        in.set(j, iTmp);

        i = 1;
        while (p[i] == 0){
            p[i] = i;
            i++;
        }
        out.add(new ArrayList<>(in));
    }
    return out;
}

private static int factorial(int num) {
    int count = num;
    while (num != 1) {
        count *= --num;
    }
    return count;
}

它需要list,因为泛型不能很好地使用数组。

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

我们可以用阶乘来计算有多少字符串以某个字母开头。

示例:取输入abcd。(3!) == 6个字符串将以abcd中的每个字母开头。

static public int facts(int x){
    int sum = 1;
    for (int i = 1; i < x; i++) {
        sum *= (i+1);
    }
    return sum;
}

public static void permutation(String str) {
    char[] str2 = str.toCharArray();
    int n = str2.length;
    int permutation = 0;
    if (n == 1) {
        System.out.println(str2[0]);
    } else if (n == 2) {
        System.out.println(str2[0] + "" + str2[1]);
        System.out.println(str2[1] + "" + str2[0]);
    } else {
        for (int i = 0; i < n; i++) {
            if (true) {
                char[] str3 = str.toCharArray();
                char temp = str3[i];
                str3[i] = str3[0];
                str3[0] = temp;
                str2 = str3;
            }

            for (int j = 1, count = 0; count < facts(n-1); j++, count++) {
                if (j != n-1) {
                    char temp1 = str2[j+1];
                    str2[j+1] = str2[j];
                    str2[j] = temp1;
                } else {
                    char temp1 = str2[n-1];
                    str2[n-1] = str2[1];
                    str2[1] = temp1;
                    j = 1;
                } // end of else block
                permutation++;
                System.out.print("permutation " + permutation + " is   -> ");
                for (int k = 0; k < n; k++) {
                    System.out.print(str2[k]);
                } // end of loop k
                System.out.println();
            } // end of loop j
        } // end of loop i
    }
}