for starters you can make N x nested for loops like this
You can handle your problem as a 9 digit number generation
As your digits are not repeating you can discard many iterations. If encoded in the above manner (like nested for) you will came up with something like this:
Generalized Permutation (without repetitions) in C++:
//---------------------------------------------------------------------------
//--- permutation class ver 0.00 --------------------------------------------
//---------------------------------------------------------------------------
#ifndef _permutation_h
#define _permutation_h
/*---------------------------------------------------------------------------
// usage:
permutation per;
per.alloc(N);
per.first();
for (;;)
{
... here per.i[0..N-1] contains actual permutation
... N! permutations
if (!per.next()) break;
}
//-------------------------------------------------------------------------*/
class permutation
{
public:
int *i; // i[N] permutation
BYTE *a; // a[N] item not used yet ?
int N; // items
int ix; // actual permutation layer
permutation() { N=0; i=NULL; a=NULL; ix=0; }
permutation(permutation& b) { *this=b; }
~permutation() { free(); }
permutation* operator = (const permutation *b) { *this=*b; return this; }
permutation* operator = (const permutation &b) { alloc(b.N); for (int j=0;j<N;j++) { i[j]=b.i[j]; a[j]=b.a[j]; } ix=b.ix; return this; }
void alloc(int _N)
{
free();
i=new int[_N];
if (i==NULL) return;
a=new BYTE[_N];
if (a==NULL) { free(); return; }
N=_N;
}
void free ()
{
N=0; ix=0;
if (i!=NULL) delete i; i=NULL;
if (a!=NULL) delete a; a=NULL;
}
void first() // init permutation
{
for (ix=0;ix<N;ix++)
{
i[ix]=ix;
a[ix]=0;
} ix--;
}
bool next() // next permutation return if it is not last
{
int *ii=&i[ix];
for (;;)
{
if (*ii>=0) a[*ii]=1;
for ((*ii)++;*ii<N;(*ii)++) if (a[*ii]) { a[*ii]=0; break; }
if (*ii>=N)
{
if (ix== 0) return false;
*ii=-1; ix--; ii=&i[ix];
}
else{
if (ix==N-1) return true;
ix++; ii=&i[ix];
}
}
}
};
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
The important stuff is in first() and next() members, each permutation is stored in the i[] array as index so set N=9 and your output numbers will be (per.i[0]+1),(per.i[1]+1),...,(per.i[9]+1)
it works in following manner:
first() initialize permutation to state i[9]=(0,1,2,...8) and a[9]=(0,0,0,...0)
I will write this for simplicity like this: i=012345678,a=000000000 where
ix points to last digiti is the actual permutationa flags if digit is unused(1) or used(0) (to avoid O(N^N) operation)
next() increment to next valid permutation
Increase the last digit to next unused value. If no unused value set it as unused and increment previous digit. The same goes for overflow. The first iteration will be like this:
i=012345678,a=000000000 // starting iteration
i=01234567? a=000000001 // unset (no unused values)
i=01234568? a=000000010 // increment 8th digit
i=012345687 a=000000000 // set the last digit result
next iteration:
i=012345687 a=000000000 // starting iteration
i=01234568? a=000000010 // unset (no unused values)
i=0123456?? a=000000011 // unset (8->9 overflow)
i=0123457?? a=000000101 // increment 7th digit
i=01234576? a=000000001 // after overflow digit set to lowest free value
i=012345768 a=000000000 // after overflow digit set to lowest free value
I hope it is clear enough.
Of coarse if you use recursion instead of iteration the code will look much nicer but in most languages will run also slower due to stack/heap trashing
As @NikolaDimitroff pointed out this is in C++ instead of javascript so:
- ignore
new,delete and class members other then first(),next()
- set
N=9; and arrays i,a can be static like: int i[9]; BYTE a[9];
Here the solution O(N!) for the task in C++:
int a,b,c,d,e,f,g,h,i;
permutation per;
per.alloc(9);
per.first();
for (;;)
{
if ((per.i[0]+1)
+(13*(per.i[1]+1)/(per.i[2]+1))+(per.i[3]+1)
+(12*(per.i[4]+1))
-(per.i[5]+1)-11
+((per.i[6]+1)*(per.i[7]+1)/(per.i[8]+1))-10
==66)
{
a=per.i[0]+'1';
b=per.i[1]+'1';
c=per.i[2]+'1';
d=per.i[3]+'1';
e=per.i[4]+'1';
f=per.i[5]+'1';
g=per.i[6]+'1';
h=per.i[7]+'1';
i=per.i[8]+'1';
// here a,b,c,d,e,f,g,h,i holds the solution
break;
}
if (!per.next()) break;
}
与恶龙缠斗过久,自身亦成为恶龙；凝视深渊过久,深渊将回以凝视…
