#include <cstdlib>
#include <iostream>
#include <windows.h>
#include <cmath>
#include "gmp.h"
using namespace std;
const int L=22;
mpz_t Hash[10][L];
mpz_t dif[10][10][L];
mpz_t POW10[L];
char str[L<<1];
void Init( ){
unsigned i, j;
for( i=0; i<10; ++i ){
for( j=0; j<L; ++j )
mpz_init( Hash[i][j] );
}
mpz_set_ui( Hash[0][0], 0 );
mpz_init_set_ui( POW10[0], 1 );
for( i=1; i<10; ++i )
mpz_set_ui( Hash[i][0], 1 );
for( j=1; j<L; ++j ){
mpz_init( POW10[j] );
mpz_mul_ui( POW10[j], POW10[j-1], 10 );
}
for( i=0; i<10; ++i ){
for( j=1; j<L; ++j ){
mpz_mul_ui( Hash[i][j], Hash[i][j-1], i );
}
}
for( int k=0; k<L; ++k ){
for( i=0; i<10; ++i ){
for( j=0; j<10; ++j ){
mpz_init( dif[i][j][k] );
mpz_sub( dif[i][j][k], Hash[i][k], Hash[j][k] );
}
}
}
}
void Clean( ){
unsigned i, j;
for( i=0; i<10; ++i )
for( j=0; j<L; ++j ){
mpz_clear( Hash[i][j] );
}
for( j=0; j<L; ++j )
mpz_clear( POW10[j] );
for( int k=0; k<L; ++k ){
for( i=0; i<10; ++i ){
for( j=0; j<10; ++j ){
mpz_clear( dif[i][j][k] );
}
}
}
}
bool check( mpz_t &n, int *c ){
int i, d[10]={0};
mpz_get_str( str, 10, n );
for( i=0; str[i]!='\0'; ++i ){
d[str[i]-'0']++;
if( d[str[i]-'0']>c[str[i]-'0'] ) return false;
}
return true;
}
void combination( unsigned n, unsigned m ){
int *c=new int[m+2], j, *num=new int[m+2];
int dig[10]={0};
dig[0]=m;
for( j=1; j<=m; ++j ) c[j]=j-1, num[j]=c[j]-j+1;
c[m+1]=n;
mpz_t number;
mpz_init_set_ui( number, 0 );
R2:
if( mpz_cmp( number, POW10[m-1] )>0 && mpz_cmp( number, POW10[m] )<0 && check( number, dig ) ){
mpz_out_str( stdout, 10, number );
printf("\n");
}
if( m&1 )
if( c[1]+1<c[2] ){
--dig[num[1]];
mpz_add( number, number, dif[num[1]+1][num[1]][m] );
++c[1], ++num[1];
++dig[num[1]];
goto R2;
}
else{
j=2; goto R4;
}
else
if( c[1]>0 ){
--dig[num[1]];
mpz_sub( number, number, dif[num[1]][num[1]-1][m] );
--c[1], --num[1];
++dig[num[1]];
goto R2;
}
else{
j=2; goto R5;
};
R4: if( c[j]>=j ){
if( j<=m ){
--dig[num[j]];
mpz_sub( number, number, dif[num[j]][c[j-1]-j+1][m] );
}
if( j-1<=m ){
--dig[num[j-1]];
mpz_sub( number, number, dif[num[j-1]][0][m] );
}
c[j]=c[j-1], num[j]=c[j]-j+1; c[j-1]=j-2, num[j-1]=c[j-1]-(j-1)+1;
if( j<=m )
++dig[num[j]];
if( j-1<=m )
++dig[num[j-1]];
goto R2;
}
else
++j;
R5: if( c[j]+1<c[j+1] ){
if( j<=m ){
--dig[num[j]];
mpz_sub( number, number, dif[num[j]][c[j]+1-j+1][m] );
}
if( j-1<=m ){
--dig[num[j-1]];
mpz_sub( number, number, dif[num[j-1]][c[j]-j+2][m] );
}
c[j-1]=c[j], num[j-1]=c[j-1]-(j-1)+1; c[j]=c[j]+1, num[j]=c[j]-j+1;
if( j<=m )
++dig[num[j]];
if( j-1<=m )
++dig[num[j-1]];
goto R2;
}
else{
++j;
if( j<=m ) goto R4;
}
delete []c;
delete []num;
mpz_clear( number );
}
int main(int argc, char *argv[])
{
int time=GetTickCount();
Init();
for( unsigned i=21; i<L; ++i ){
cout<<i<<" digits search start!\n";
combination( i+9, i );
}
Clean( );
cout<<"time : "<<GetTickCount()-time<<" ms\n";
cout<<"press any key to continue...\n";
cin.get();
return EXIT_SUCCESS;
}
