PKU Judge Online 1731 Orders

■1731 Orders

□Problem
文字列sが与えられる．sの順列を辞書式順で生成せよ．但し，重複する文字列は省く．

□Solution
順列生成は再帰で．
重複を省くためには，以下．
まず，
s=c₀c₁…c_n-1
に，
v_k=kと数字を割り当てる．
再帰で順列を生成し，
s'=c_a0c_a1…c_an-1
となったとする．
c_ai=c_aj (i<j)
となるi,jがあった時，
v_i<v_j
であれば，その順列を出力し，そうでない場合は出力しない．
実際には，この判定を再帰の途中で行い，枝刈りをしている．

出力が遅かったため(TLEした)，
System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
として，最後にまとめてストリームをフラッシュ．

□Code

view plainprint?

1. package p1731;  
2.   
3. import java.util.*;  
4. import java.io.BufferedOutputStream;  
5. import java.io.PrintStream;  
6. import java.lang.*;  
7. import java.math.*;  
8.   
9. // AC  
10. public class Main{  
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  char[] cs;  
14.  int[] order;  
15.  int n;  
16.   
17.  void recursive(int j){  
18.   if(j==n){  
19.    println(new String(cs));  
20.    return;  
21.   }  
22.   for(int i=j; i<n; i++){  
23.    // right rotate [j,i]  
24.    char c=cs[i];  
25.    int t=order[i];  
26.    for(int k=i; k>j; k--){  
27.     cs[k]=cs[k-1];  
28.     order[k]=order[k-1];  
29.    }  
30.    cs[j]=c;  
31.    order[j]=t;  
32.    boolean f=true;  
33.    for(int k=j; k<=i; k++){  
34.     if(cs[j]==cs[k]&&order[j]>order[k]){  
35.      f=false;  
36.      break;  
37.     }  
38.    }  
39.    if(f)  
40.     recursive(j+1);  
41.    // left rotate [j,i]  
42.    for(int k=j; k<i; k++){  
43.     cs[k]=cs[k+1];  
44.     order[k]=order[k+1];  
45.    }  
46.    cs[i]=c;  
47.    order[i]=t;  
48.   }  
49.  }  
50.   
51.  void run(){  
52.   cs=sc.next().toCharArray();  
53.   n=cs.length;  
54.   order=new int[n];  
55.   for(int i=0; i<n; i++)  
56.    order[i]=i;  
57.   Arrays.sort(cs);  
58.   recursive(0);  
59.   System.out.flush();  
60.  }  
61.   
62.  void println(String s){  
63.   System.out.println(s);  
64.  }  
65.   
66.  void print(String s){  
67.   System.out.print(s);  
68.  }  
69.   
70.  public static void main(String[] args){  
71.   System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
72.   new Main().run();  
73.  }  
74. }  

package p1731;

import java.util.*;
import java.io.BufferedOutputStream;
import java.io.PrintStream;
import java.lang.*;
import java.math.*;

// AC
public class Main{
 Scanner sc=new Scanner(System.in);

 char[] cs;
 int[] order;
 int n;

 void recursive(int j){
  if(j==n){
   println(new String(cs));
   return;
  }
  for(int i=j; i<n; i++){
   // right rotate [j,i]
   char c=cs[i];
   int t=order[i];
   for(int k=i; k>j; k--){
    cs[k]=cs[k-1];
    order[k]=order[k-1];
   }
   cs[j]=c;
   order[j]=t;
   boolean f=true;
   for(int k=j; k<=i; k++){
    if(cs[j]==cs[k]&&order[j]>order[k]){
     f=false;
     break;
    }
   }
   if(f)
    recursive(j+1);
   // left rotate [j,i]
   for(int k=j; k<i; k++){
    cs[k]=cs[k+1];
    order[k]=order[k+1];
   }
   cs[i]=c;
   order[i]=t;
  }
 }

 void run(){
  cs=sc.next().toCharArray();
  n=cs.length;
  order=new int[n];
  for(int i=0; i<n; i++)
   order[i]=i;
  Arrays.sort(cs);
  recursive(0);
  System.out.flush();
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 public static void main(String[] args){
  System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}