6

始める前に、重複した順列の別のケースを提起したことをお詫びする必要があります。ほとんどの検索結果を確認しましたが、探しているものが本当に見つかりません。辞書式順序について読み、実装しました。この質問では、aとbの数が等しい文字aとbだけで構成される長さnのすべての文字列を出力する再帰メソッドを実装することを想定しています。文字列は、辞書式順序で一度に1行ずつ印刷する必要があります。したがって、たとえば、次のように呼び出します。

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」の場合、重複は発生しません。配列リストの使用について読み、すべての結果を保存してから、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;

        }
    }

}

4

4 に答える 4

6

このソリューションでは、並べ替えのために余分なスペースは必要ありません

クレジット： 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, ""); 
    }
}
于 2014-02-20T05:34:58.060 に答える
5

セットを使用して結果をそのセット（できればSortedSet ）に保存できます。これにより、重複が排除され、トラバーサル中にソートされた順序も維持されます。

于 2012-10-01T04:34:25.047 に答える
3

順列の最も一般的な実装を使用できます（要素を最初の要素と交換し、残りの要素を並べ替えます）。最初に文字列を作成し、並べ替えてから、可能なすべての順列を生成します。重複を許可しないでください。

実装は次のようになります。

static String swap(String s, int i, int j) {
    char [] c = s.toCharArray();
    char tmp = c[i];
    c[i] = c[j];
    c[j] = tmp;
    return String.copyValueOf(c);
}

static void permute(String s, int start) {
    int end = s.length();

    if(start == end) {
        System.out.println(s);
        return;
    }

    permute(s, start + 1);

    for(int i = start + 1; i < end; i++) {
        if(s.charAt(start) == s.charAt(i)) continue;
        s = swap(s, start, i);
        permute(s, start + 1);
    }
}

public static void main(String [] args) {
    String s = "aabb";
    permute(s, 0);
}

出力を生成します：

aabb
abab
abba
baab
baba
bbaa
于 2012-10-01T04:41:31.643 に答える
0

@ 0605002のコードに基づいて、少し変更しました。permuteのforループでは、permuteメソッドの呼び出し後に再度スワップする必要があります。それはバックトラックのようなものです。次の反復のためにそれを元に戻す必要があります。

static void permute(String s, int start) {
    int end = s.length();

    if(start == end) {
        System.out.println(s);
        return;
    }

    permute(s, start + 1);

    for(int i = start + 1; i < end; i++) {
        if(s.charAt(start) == s.charAt(i)) continue;
        s = swap(s, start, i);
        permute(s, start + 1);
        s = swap(s, start, i);
    }
}
于 2019-02-21T15:40:29.757 に答える