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


当前回答

使用Set操作建模“依赖于其他选择的选择”更容易理解相关排列 使用依赖排列,可用的选择减少,因为位置被从左到右的选定字符填充。递归调用的终端条件是测试可用选择集是否为空。当满足终端条件时,置换完成,并存储到“结果”列表中。

public static List<String> stringPermutation(String s) {
    List<String> results = new ArrayList<>();
    Set<Character> charSet = s.chars().mapToObj(m -> (char) m).collect(Collectors.toSet());
    stringPermutation(charSet, "", results);
    return results;
}

private static void stringPermutation(Set<Character> charSet, 
        String prefix, List<String> results) {
    if (charSet.isEmpty()) {
        results.add(prefix);
        return;
    }
    for (Character c : charSet) {
        Set<Character> newSet = new HashSet<>(charSet);
        newSet.remove(c);
        stringPermutation(newSet, prefix + c, results);
    }
} 

该代码可以泛化为一组对象查找排列。在本例中,我使用了一组颜色。

public enum Color{
    ORANGE,RED,BULE,GREEN,YELLOW;
}

public static List<List<Color>> colorPermutation(Set<Color> colors) {
    List<List<Color>> results = new ArrayList<>();
    List<Color> prefix = new ArrayList<>();
    permutation(colors, prefix, results);
    return results;
}

private static <T> void permutation(Set<T> set, List<T> prefix, List<List<T>> results) {
    if (set.isEmpty()) {
        results.add(prefix);
        return;
    }
    for (T t : set) {
        Set<T> newSet = new HashSet<>(set);
        List<T> newPrefix = new ArrayList<>(prefix);
        newSet.remove(t);
        newPrefix.add(t);
        permutation(newSet, newPrefix, results);
    }
} 

测试代码。

public static void main(String[] args) {
    List<String> stringPerm = stringPermutation("abcde");
    System.out.println("# of permutations:" + stringPerm.size());
    stringPerm.stream().forEach(e -> System.out.println(e));

    Set<Color> colorSet = Arrays.stream(Color.values()).collect(Collectors.toSet());
    List<List<Color>> colorPerm = colorPermutation(colorSet);
    System.out.println("# of permutations:" + colorPerm.size());
    colorPerm.stream().forEach(e -> System.out.println(e));
}

其他回答

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

基于Mark Byers的回答,我想出了这个解决方案:

JAVA

public class Main {

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

    private static void myPerm(String str, int index)
    {
        if (index == str.length()) System.out.println(str);

        for (int i = index; i < str.length(); i++)
        {
            char prefix = str.charAt(i);
            String suffix = str.substring(0,i) + str.substring(i+1);

            myPerm(prefix + suffix, index + 1);
        }
    }
}

C#

我还使用新的c# 8.0范围操作符在c#中编写了该函数

    class Program
    {
        static void Main(string[] args)
        {
            myPerm("ABCD", 0);
        }

        private static void myPerm(string str, int index)
        {
            if (index == str.Length) Console.WriteLine(str);

            for (int i = index; i < str.Length; i++)
            {
                char prefix = str[i];
                string suffix = str[0..i] + str[(i + 1)..];

                myPerm(prefix + suffix, index + 1);
            }
        }
    

我们只是把每个字母放在开头,然后排列。 第一次迭代是这样的:

/*
myPerm("ABCD",0)  
  prefix = "A"  
  suffix = "BCD"  
  myPerm("ABCD",1)  
    prefix = "B"  
    suffix = "ACD"  
    myPerm("BACD",2)  
      prefix = "C"  
      suffix = "BAD"  
      myPerm("CBAD",3)  
        prefix = "D"  
        suffix = "CBA"  
        myPerm("DCBA",4)  
          Console.WriteLine("DCBA")
*/

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','')

如果有人想要生成排列来做一些事情,而不是通过void方法打印它们:

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;

}

作为Python生成器,带有现代类型提示:

from typing import Iterator


def permutations(string: str, prefix: str = '') -> Iterator[str]:
    if len(string) == 0:
        yield prefix
    for i, character in enumerate(string):
        yield from permutations(string[:i] + string[i + 1:], prefix + character)


for p in permutations('abcd'):
    print(p)