import java.util.ArrayList ;
import java.io.* ;
class Lexicography {
static ArrayList< Long> perms = new ArrayList< Long> ( ) ;
long time
= System .
currentTimeMillis ( ) ;
System .
out .
println ( "\n Size:-" + perms.
size ( ) + "\n Time:-" + ( System .
currentTimeMillis ( ) - time
) ) ; //This println is never printed... java aborts before that
}
public static ArrayList< Long> getPermutations( int num) {
int [ ] n = new int [ num+ 1 ] ;
for ( int i= 0 ; i<= num; i++ ) n[ i] = i;
perms.add ( getLong( n) ) ;
for ( int i= num; i>= 0 ; i-- ) permutate( n[ i] ,n) ;
return perms;
}
private static void permutate( int k, int [ ] n) {
if ( k> n.length ) return ;
int p= 0 ;
for ( int i: n) { if ( i== k) break ; p++; }
for ( int i= 0 ; i< n.length ; i++ ) {
if ( i== p || n[ i] < k) continue ;
n= swap( p,i,n) ;
perms.add ( getLong( n) ) ;
//System.out.println("i:"+(i+1)+" k:"+k+" n:"+getLong(n));//this prints all permutations till the last one and then poof!
for ( int j= k- 1 ; j>= 0 ; j-- ) permutate( j,n) ;
n= swap( p,i,n) ;
}
}
private static int [ ] swap( int i, int f, int [ ] a) {
int t= a[ f] ;
a[ f] = a[ i] ; a[ i] = t;
return a;
}
private static long getLong( int [ ] n) {
long ten= 1 , num= 0 ;
for ( int i= n.length - 1 ; i>= 0 ; i-- ) {
num+= n[ i] * ten; ten*= 10 ;
}
return num;
}
}
aW1wb3J0IGphdmEudXRpbC5BcnJheUxpc3Q7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBMZXhpY29ncmFwaHkgewoKICAgIHN0YXRpYyBBcnJheUxpc3Q8TG9uZz4gcGVybXMgPSBuZXcgQXJyYXlMaXN0PExvbmc+KCk7CgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgdGhyb3dzIElPRXhjZXB0aW9uewogICAgICAgIGxvbmcgdGltZSA9IFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpOwogICAgICAgIGdldFBlcm11dGF0aW9ucyhJbnRlZ2VyLnZhbHVlT2YobmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKS5yZWFkTGluZSgpKSk7CgogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiXG5TaXplOi0iK3Blcm1zLnNpemUoKSsiXG5UaW1lOi0iKyhTeXN0ZW0uY3VycmVudFRpbWVNaWxsaXMoKS10aW1lKSk7CiAgICAgICAgLy9UaGlzIHByaW50bG4gaXMgbmV2ZXIgcHJpbnRlZC4uLiBqYXZhIGFib3J0cyBiZWZvcmUgdGhhdAogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgQXJyYXlMaXN0PExvbmc+IGdldFBlcm11dGF0aW9ucyhpbnQgbnVtKXsKICAgICAgICBpbnRbXSBuID0gbmV3IGludFtudW0rMV07CiAgICAgICAgZm9yKGludCBpPTA7IGk8PW51bTsgaSsrKSBuW2ldPWk7CiAgICAgICAgcGVybXMuYWRkKGdldExvbmcobikpOwogICAgICAgIGZvcihpbnQgaT1udW07IGk+PTA7IGktLSkgcGVybXV0YXRlKG5baV0sbik7CiAgICAgICAgcmV0dXJuIHBlcm1zOwogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgcGVybXV0YXRlKGludCBrLCBpbnRbXSBuKXsKICAgICAgICBpZihrPm4ubGVuZ3RoKSByZXR1cm47CiAgICAgICAgaW50IHA9MDsKICAgICAgICBmb3IoaW50IGk6bil7IGlmKGk9PWspIGJyZWFrOyBwKys7fQoKICAgICAgICBmb3IoaW50IGk9MDsgaTxuLmxlbmd0aDsgaSsrKXsKICAgICAgICAgICAgaWYoaT09cCB8fCBuW2ldPGspIGNvbnRpbnVlOwogICAgICAgICAgICBuPXN3YXAocCxpLG4pOwogICAgICAgICAgICBwZXJtcy5hZGQoZ2V0TG9uZyhuKSk7CiAgICAgICAgICAgIC8vU3lzdGVtLm91dC5wcmludGxuKCJpOiIrKGkrMSkrIiBrOiIraysiICAgIG46IitnZXRMb25nKG4pKTsvL3RoaXMgcHJpbnRzIGFsbCBwZXJtdXRhdGlvbnMgdGlsbCB0aGUgbGFzdCBvbmUgYW5kIHRoZW4gcG9vZiEKCiAgICAgICAgICAgIGZvcihpbnQgaj1rLTE7IGo+PTA7IGotLSkgcGVybXV0YXRlKGosbik7CiAgICAgICAgICAgIG49c3dhcChwLGksbik7CiAgICAgICAgfQogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIGludFtdIHN3YXAoaW50IGksIGludCBmLCBpbnRbXSBhKXsKICAgICAgICBpbnQgdD1hW2ZdOwogICAgICAgIGFbZl09YVtpXTsgYVtpXT10OwogICAgICAgIHJldHVybiBhOwogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIGxvbmcgZ2V0TG9uZyhpbnRbXSBuKXsKICAgICAgICBsb25nIHRlbj0xLCBudW09MDsKICAgICAgICBmb3IoaW50IGk9bi5sZW5ndGgtMTsgaT49MDsgaS0tKXsKICAgICAgICAgICAgbnVtKz1uW2ldKnRlbjsgdGVuKj0xMDsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIG51bTsKICAgIH0KCn0=