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


当前回答

python实现

def getPermutation(s, prefix=''):
        if len(s) == 0:
                print prefix
        for i in range(len(s)):
                getPermutation(s[0:i]+s[i+1:len(s)],prefix+s[i] )



getPermutation('abcd','')

其他回答

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

(通过Java编程入门)

//循环'整个字符数组,并保持'i'作为你的排列的基础,并像你交换[ab, ba]一样继续寻找组合

public class Permutation {
    //Act as a queue
    private List<Character> list;
    //To remove the duplicates
    private Set<String> set = new HashSet<String>();

    public Permutation(String s) {
        list = new LinkedList<Character>();
        int len = s.length();
        for(int i = 0; i < len; i++) {
            list.add(s.charAt(i));
        }
    }

    public List<String> getStack(Character c, List<Character> list) {
        LinkedList<String> stack = new LinkedList<String>();
        stack.add(""+c);
        for(Character ch: list) {
            stack.add(""+ch);
        }

        return stack;
    }

    public String printCombination(String s1, String s2) {
        //S1 will be a single character
        StringBuilder sb = new StringBuilder();
        String[] strArr = s2.split(",");
        for(String s: strArr) {
            sb.append(s).append(s1);
            sb.append(",");
        }       
        for(String s: strArr) {
            sb.append(s1).append(s);
            sb.append(",");
        }

        return sb.toString();
    }

    public void printPerumtation() {
        int cnt = list.size();

        for(int i = 0; i < cnt; i++) {
            Character c = list.get(0);
            list.remove(0);
            List<String> stack = getStack(c, list);

            while(stack.size() > 1) {
                //Remove the top two elements
                String s2 = stack.remove(stack.size() - 1);
                String s1 = stack.remove(stack.size() - 1);
                String comS = printCombination(s1, s2);
                stack.add(comS);
            }

            String[] perms = (stack.remove(0)).split(",");
            for(String perm: perms) {
                set.add(perm);
            }

            list.add(c);
        }

        for(String s: set) {
            System.out.println(s);
        }
    }
}

倒计时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,因为泛型不能很好地使用数组。

另一种简单的方法是遍历字符串,选择尚未使用的字符并将其放入缓冲区,继续循环,直到缓冲区大小等于字符串长度。我更喜欢这个回溯跟踪解决方案,因为:

容易理解 容易避免重复 输出是排序的

下面是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;
    }
  }
}

str输入:1231

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

注意,输出是排序的,没有重复的结果。

基于Mark Byers的回答,我的python实现:

def permutations(string):
    if len(string) == 1:
        return [string]
    permutations=[]
    for i in range(len(string)):
        for perm in permutations(string[:i]+string[i+1:]):
            permutations.append(string[i] + perm)
    return permutations