生成所有排序(permutations),但要檢查生成的permutation是否有連續的重複組合,如有連續的重複組合即為無效的permutatoin,若否則為有效的permutation。如"ABAB"為無效,因連續出現"AB"組合,但"ABCAB"則為有效。輸出指定的第n個有效permutation。
CODE
#include <iostream> using namespace std; #define MAX 80 int n, let, seqn; bool check(char *s, int len); void gen(char *s, int len); void output(char *s, int len); int main(){ char s[MAX]; while( (cin >> n >> let) && (n != 0) ){ seqn = 0; gen(s, 0); }//while return 0; } //return true if string is "hard", false when "easy" bool check(char *s, int len){ int i, j, k; for(i=0; i<len; ++i){ for(j=0; j<i; ++j){ for(k=j; k<i && s[k]==s[i+k-j]; ++k) ;//k if( k == i ) return false; }//j }//i return true; } void gen(char *s, int len){ for(int i=0; i<let && seqn<n; ++i){ s[len] = 'A' + i; s[len+1] = '\0'; if( check(s, len+1) ){ if( ++seqn == n ){ output(s, len+1); return; } if( seqn < n ) gen(s, len+1); } }//i } void output(char *s, int len){ for(int i=0; i<len; ++i){ if( i == 64 ) cout << endl; else if( i>0 && i%4==0 ) cout << ' '; cout << s[i]; }//i cout << endl << len << endl; }
No comments:
Post a Comment