使用Es6的字符串排列

使用reduce()方法

Const排列= STR => { If (str.length <= 2) 返回str.length === 2 ?[str, str[1] + str[0]]: [str]; 返回str .split (") .reduce ( (acc, letter, index) => acc.concat(排列(str。Slice (0, index) + str.slice(index + 1))。Map (val =>字母+ val))， ［］ ）; }; console.log(排列(STR));

为排列和组合添加更详细的NcK/NcR

public static void combinationNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
    if (chooseCount == 0)
        resultList.add(prefix);
    else {
        for (int i = 0; i < inputList.size(); i++)
            combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);

        // Finally print once all combinations are done
        if (prefix.equalsIgnoreCase("")) {
            resultList.stream().map(str -> str.substring(1)).forEach(System.out::println);
        }
    }
}

public static void permNcK(List<String> inputList, int chooseCount, List<String> resultList) {
    for (int count = 0; count < inputList.size(); count++) {
        permNcK(inputList, "", chooseCount, resultList);
        resultList = new ArrayList<String>();
        Collections.rotate(inputList, 1);
        System.out.println("-------------------------");
    }

}

public static void permNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
    if (chooseCount == 0)
        resultList.add(prefix);
    else {
        for (int i = 0; i < inputList.size(); i++)
            combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);

        // Finally print once all combinations are done
        if (prefix.equalsIgnoreCase("")) {
            resultList.stream().map(str -> str.substring(1)).forEach(System.out::println);
        }
    }
}

public static void main(String[] args) {
    List<String> positions = Arrays.asList(new String[] { "1", "2", "3", "4", "5", "6", "7", "8" });
    List<String> resultList = new ArrayList<String>();
    //combinationNcK(positions, "", 3, resultList);

    permNcK(positions, 3, resultList);

}

使用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));
}

以下是我在《破解编程面试》(P54)一书中提出的解决方案:

/**
 * List permutations of a string.
 * 
 * @param s the input string
 * @return  the list of permutations
 */
public static ArrayList<String> permutation(String s) {
    // The result
    ArrayList<String> res = new ArrayList<String>();
    // If input string's length is 1, return {s}
    if (s.length() == 1) {
        res.add(s);
    } else if (s.length() > 1) {
        int lastIndex = s.length() - 1;
        // Find out the last character
        String last = s.substring(lastIndex);
        // Rest of the string
        String rest = s.substring(0, lastIndex);
        // Perform permutation on the rest string and
        // merge with the last character
        res = merge(permutation(rest), last);
    }
    return res;
}

/**
 * @param list a result of permutation, e.g. {"ab", "ba"}
 * @param c    the last character
 * @return     a merged new list, e.g. {"cab", "acb" ... }
 */
public static ArrayList<String> merge(ArrayList<String> list, String c) {
    ArrayList<String> res = new ArrayList<>();
    // Loop through all the string in the list
    for (String s : list) {
        // For each string, insert the last character to all possible positions
        // and add them to the new list
        for (int i = 0; i <= s.length(); ++i) {
            String ps = new StringBuffer(s).insert(i, c).toString();
            res.add(ps);
        }
    }
    return res;
}

字符串"abcd"的运行输出:

第一步:合并[a]和b: [ba, ab] 步骤2:Merge [ba, ab]和c: [cba, bca, bac, cab, acb, abc] 第三步:Merge [cba, bca, bac, cab, acb, abc]和d: [dcba, cdba, cbad, cbca, bdcad

/*
     * eg: abc =>{a,bc},{b,ac},{c,ab}
     * =>{ca,b},{cb,a}
     * =>cba,cab
     * =>{ba,c},{bc,a}
     * =>bca,bac
     * =>{ab,c},{ac,b}
     * =>acb,abc
     */
    public void nonRecpermute(String prefix, String word)
    {
        String[] currentstr ={prefix,word};
        Stack<String[]> stack = new Stack<String[]>();
        stack.add(currentstr);
        while(!stack.isEmpty())
        {
            currentstr = stack.pop();
            String currentPrefix = currentstr[0];
            String currentWord = currentstr[1];
            if(currentWord.equals(""))
            {
                System.out.println("Word ="+currentPrefix);
            }
            for(int i=0;i<currentWord.length();i++)
            {
                String[] newstr = new String[2];
                newstr[0]=currentPrefix + String.valueOf(currentWord.charAt(i));
                newstr[1] = currentWord.substring(0, i);
                if(i<currentWord.length()-1)
                {
                    newstr[1] = newstr[1]+currentWord.substring(i+1);
                }
                stack.push(newstr);
            }

        }

    }

public class Permutation 
{ 
public static void main(String[] args) 
{ 
    String str = "ABC"; 
    int n = str.length(); 
    Permutation permutation = new Permutation(); 
    permutation.permute(str, 0, n-1); 
} 

/** 
* permutation function 
* @param str string to calculate permutation for 
* @param l starting index 
* @param r end index 
*/
private void permute(String str, int l, int r) 
{ 
    if (l == r) 
        System.out.println(str); 
    else
    { 
        for (int i = l; i <= r; i++) 
        { 
            str = swap(str,l,i); 
            permute(str, l+1, r); 
            str = swap(str,l,i); 
        } 
    } 
} 

/** 
* Swap Characters at position 
* @param a string value 
* @param i position 1 
* @param j position 2 
* @return swapped string 
*/
public String swap(String a, int i, int j) 
{ 
    char temp; 
    char[] charArray = a.toCharArray(); 
    temp = charArray[i] ; 
    charArray[i] = charArray[j]; 
    charArray[j] = temp; 
    return String.valueOf(charArray); 
} 

}