没有递归的Java实现

public Set<String> permutate(String s){
    Queue<String> permutations = new LinkedList<String>();
    Set<String> v = new HashSet<String>();
    permutations.add(s);

    while(permutations.size()!=0){
        String str = permutations.poll();
        if(!v.contains(str)){
            v.add(str);
            for(int i = 0;i<str.length();i++){
                String c = String.valueOf(str.charAt(i));
                permutations.add(str.substring(i+1) + c +  str.substring(0,i));
            }
        }
    }
    return v;
}

Java中一个非常基本的解决方案是使用递归+设置(以避免重复)，如果你想存储和返回解决方案字符串:

public static Set<String> generatePerm(String input)
{
    Set<String> set = new HashSet<String>();
    if (input == "")
        return set;

    Character a = input.charAt(0);

    if (input.length() > 1)
    {
        input = input.substring(1);

        Set<String> permSet = generatePerm(input);

        for (String x : permSet)
        {
            for (int i = 0; i <= x.length(); i++)
            {
                set.add(x.substring(0, i) + a + x.substring(i));
            }
        }
    }
    else
    {
        set.add(a + "");
    }
    return set;
}

这个没有递归

public static void permute(String s) {
    if(null==s || s.isEmpty()) {
        return;
    }

    // List containing words formed in each iteration 
    List<String> strings = new LinkedList<String>();
    strings.add(String.valueOf(s.charAt(0))); // add the first element to the list

     // Temp list that holds the set of strings for 
     //  appending the current character to all position in each word in the original list
    List<String> tempList = new LinkedList<String>(); 

    for(int i=1; i< s.length(); i++) {

        for(int j=0; j<strings.size(); j++) {
            tempList.addAll(merge(s.charAt(i), strings.get(j)));
                        }
        strings.removeAll(strings);
        strings.addAll(tempList);

        tempList.removeAll(tempList);

    }

    for(int i=0; i<strings.size(); i++) {
        System.out.println(strings.get(i));
    }
}

/**
 * helper method that appends the given character at each position in the given string 
 * and returns a set of such modified strings 
 * - set removes duplicates if any(in case a character is repeated)
 */
private static Set<String> merge(Character c,  String s) {
    if(s==null || s.isEmpty()) {
        return null;
    }

    int len = s.length();
    StringBuilder sb = new StringBuilder();
    Set<String> list = new HashSet<String>();

    for(int i=0; i<= len; i++) {
        sb = new StringBuilder();
        sb.append(s.substring(0, i) + c + s.substring(i, len));
        list.add(sb.toString());
    }

    return list;
}

改进的代码相同

    static String permutationStr[];
    static int indexStr = 0;

    static int factorial (int i) {
        if (i == 1)
            return 1;
        else
            return i * factorial(i-1);
    }

    public static void permutation(String str) {
        char strArr[] = str.toLowerCase().toCharArray();
        java.util.Arrays.sort(strArr);

        int count = 1, dr = 1;
        for (int i = 0; i < strArr.length-1; i++){
            if ( strArr[i] == strArr[i+1]) {
                count++;
            } else {
                dr *= factorial(count);
                count = 1;
            }       
        }
        dr *= factorial(count);

        count = factorial(strArr.length) / dr;

        permutationStr = new String[count];

        permutation("", str);

        for (String oneStr : permutationStr){
            System.out.println(oneStr);
        }
    }

    private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0) {
            for (int i = 0; i < indexStr; i++){
                if(permutationStr[i].equals(prefix))
                    return;
            }        
            permutationStr[indexStr++] = prefix;
        } else {
            for (int i = 0; i < n; i++) {
                permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
            }
        }
    }

递归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')

为排列和组合添加更详细的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);

}