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

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