ACM: 129 – Krypton Factor

生成所有排序(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;
}