java - 重复排列

Question

在开始之前，我必须为提出另一个重复排列的案例而道歉。我浏览了大部分搜索结果，但无法真正找到我要找的东西。我已阅读有关词典顺序的信息并已实现。对于这个问题，我想实现一个递归方法，打印出所有长度为 n 的字符串，这些字符串仅由字符 a 和 b 组成，并且 a 和 b 的数量相等。字符串必须按词汇顺序一次打印一行。因此，例如，一个电话:

printBalanced(4);

将打印字符串:

aabb
abab
abba
baab
baba
bbaa

这是代码

public static void main(String[] args){
    printBalanced(4);
}


public static void printBalanced(int n){
    String letters = "";

    //string to be duplicates of "ab" depending the number of times the user wants it
    for(int i =0; i<n/2;i++){
        letters += "ab";
    }


    balanced("",letters);

}

private static void balanced(String prefix, String s){

    int len = s.length();

    //base case
    if (len ==0){
        System.out.println(prefix);
    }
    else{
            for(int i = 0; i<len; i++){     

                balanced(prefix + s.charAt(i),s.substring(0,i)+s.substring(i+1,len));


            }

        }
    }

我的打印结果:

abab
abba
aabb
aabb
abba
abab
baab
baba
baab
baba
bbaa
bbaa
aabb
aabb
abab
abba
abab
abba
baba
baab
bbaa
bbaa
baab
baba

如您所见，我得到了很多重复项。这部分是由于要求仅使用字符“a”和“b”。如果它是“abcd”或“0123”，则不会发生重复。我已经阅读了有关使用 arraylist 并存储所有结果然后循环遍历 N 元素以检查重复项然后将其删除的信息。这似乎不是最好的方法。有人可以分享这个问题的其他更好的解决方案吗？ =)

我使用 SortedSet 的解决方案:

import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;

public class BalancedStrings {

public static void main(String[] args){

    printBalanced(4);
}


public static void printBalanced(int n){
    String letters = "";

    for(int i =0; i<n/2;i++){
        letters += "ab";
    }


    SortedSet<String> results = balanced("",letters);
    Iterator<String> it = results.iterator();
    while (it.hasNext()) {

        // Get element and print
        Object element = it.next();
        System.out.println(element);
    }

}


//This method returns a SortedSet with permutation results. SortedSet was chosen for its sorting and not allowing
//duplicates properties.
private static SortedSet<String> balanced(String prefix, String s){

    SortedSet<String> set = new TreeSet<String>();

    int len = s.length();

    //base case
    if (len == 0){

        //return the new SortedSet with just the prefix
        set.add(prefix);
        return set;


    }
    else{

        SortedSet<String> rest = new TreeSet<String>();

        for(int i = 0; i<len; i++){

            //get all permutations and store in a SortedSet, rest
            rest = balanced(prefix + s.charAt(i),s.substring(0,i)+s.substring(i+1,len));

            //put each permutation into the new SortedSet
            set.addAll(rest);
        }

        return set;

        }
    }

Answer 1

此解决方案不需要额外的排序空间

学分:http://k2code.blogspot.in/2011/09/permutation-of-string-in-java-efficient.html

public class Permutation {

    public static void printDuplicates(String str, String prefix) {
        if (str.length() == 0) {
            System.out.println(prefix); 
        }
        else {
            for (int i = 0; i < str.length(); i++) {
                if (i > 0) {
                    if (str.charAt(i) == str.charAt(i - 1)) {
                        continue; 
                    }
                }

                printDuplicates(
                    str.substring(0, i) + str.substring(i + 1, str.length()),
                    prefix + str.charAt(i)
                ); 
            }
        }
    }

    public String sort(string str) {
        // Please Implement the sorting function, I was lazy enough to do so 
    }

    public static void main(String[] args) {
        String test = "asdadsa"; 
        test = sort(test); 
        printDuplicates(test, ""); 
    }
}