aslf010990's blog

Permutations in java.
By aslf010990, 10 years ago, In English

Hello everyone, I am trying to solve the following problem: link but I'm getting time limit exceeded, I am using the following code.

import java.io.*;
import java.util.*;
public class Main {
    static boolean used[];
    static TreeSet<String>ts;
    public static void main(String[] args) throws IOException {
        BufferedReader cin=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(cin.readLine());
        while(n-->0)
        {
            String s=cin.readLine();
            ts=new TreeSet();
            used=new boolean[s.length()];
            permutations("",s,s.length(),0);
            Iterator it=ts.iterator();
            while(it.hasNext())
                System.out.println(it.next());
        }
    }
    private static void permutations(String per, String s, int t, int l) {
        if(l==t)
            ts.add(per);
        else
        {
            for(int i=0;i<t;i++)
            {
                if(!used[i])
                {
                    used[i]=true;
                    permutations(per+s.charAt(i),s,s.length(),l+1);
                    used[i]=false;
                }
            }
        }
    }
}

the problem is when generating the permutations, I have the following question, what is the fastest way to generate the permutations in java?, hope you can help me, greetings and sorry for my bad English.

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First, you should avoid creating new objects when you don't have to. In case this case instead of allocating a new object to the ts variable you should just call the method clear to remove all the elements. Second, do you really, really need to use TreeSet for this problem? Third, get rid of System.out.println(), use a Writer object, PrintWriter or BufferedWriter, something that does not flush every time you print something. And looking at your code, I think that even if it doesn't get TLE it will get WA: look at the hint section, that is not the default letter ordering used to compare Strings.

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

1) Use PrintWriter rather than System.out.println(). I tried a string "someRandom" on your code with both cases. Syso takes 5316 ms, while PrintWriter takes 2570ms on my system. PrintWriter stores the things you want to be printed on buffer and prints it out when you flush it rather than acquiring IO interrupt every time as is the case with Syso.

2) Rather than computing s.length() everytime, you can use t there. That will bring down run time to 2410.

3) You can use char arrays instead of string. String in java is not mutable, which means every time you do per + s.charAt(i), a new String is created in memory, then it is appended with values per and s.charAt(i). This will bring down run time to 2132ms.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you very much to Junior94, phantom11 and Klein for advice, just one last question is faster to use an array of characteres or StringBuilder ', well I think this is another issue jejej, greetings and thanks

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    An array of chars is faster. (A StringBuilder is basically just an ArrayList of chars. ^^) If you have very long strings you may also consider using an array of bytes, which is the fastest way as it may improve cache performance. :)

    → Reply