Geek asks and answers

Duplicate permutations

Before I begin, I have to apologize for creating another case of duplicate permutations. I went through most of the search results and cannot find what I am looking for. I read about the lexicographic order and implemented it. For this question, I suppose to implement a recursion method that prints all lines of length n, consisting only of characters a and b, which have equal numbers a and bs. Lines should be printed one line at a time in lexical order. So, for example, a call:

printBalanced(4);

print lines:

aabb
abab
abba
baab
baba
bbaa

here is the code

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));


            }

        }
    }

My print results:

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;

        }
    }

}

+5
3

Set ( SortedSet), , .

+4

credits - 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,"");
}
}
+6

You can use the most common implementation of permutations (exchange an element with the first and rearrange the rest). First create a line, sort it, then generate all possible permutations. Avoid duplicates.

The implementation may be:

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

Outputs:

aabb
abab
abba
baab
baba
bbaa
+1
source

More articles:


All Articles