/** * Author: Ali Taleghani * ali@math.ubc.ca **/ #include <iostream> #include <algorithm> #include <string> #include <map> #include <stdio.h> using namespace std; void readRequirements(map <char, char> &mustSitLeftOf, char & leftEnd, char & rightEnd, int ruleCount); bool evaluateArrangement(map <char, char> &mustSitLeftOf, char & leftEnd, char & rightEnd, char* arrangement, int length); void printAllPossibleArrangements(map <char, char> &mustSitLeftOf, char & leftEnd, char & rightEnd, int n); int main() { int n, m; cin >> n >> m; // number of guests, requirements. while (n != 0) { map <char, char> mustSitLeftOf; char leftEnd = '-', rightEnd = '-'; readRequirements(mustSitLeftOf, leftEnd, rightEnd, m); printAllPossibleArrangements(mustSitLeftOf, leftEnd, rightEnd, n); cout << endl; cin >> n >> m; // number of guests, requirements. } return 0; } void readRequirements(map <char, char> &mustSitLeftOf, char & leftEnd, char & rightEnd, int count) { string str; char guest1, guest2; for (; count > 0; count--) { cin >> str; if (sscanf(str.c_str(), "^%c", &guest1) == 1) leftEnd = guest1; else if (sscanf(str.c_str(), "%c<%c", &guest1, &guest2) == 2) mustSitLeftOf[guest1] = guest2; else if (sscanf(str.c_str(), "%c>%c", &guest1, &guest2) == 2) mustSitLeftOf[guest2] = guest1; else if (sscanf(str.c_str(), "%c$", &guest1) == 1) rightEnd = guest1; } } bool evaluateArrangement(map <char, char> &mustSitLeftOf, char & leftEnd, char & rightEnd, char * arrangement, int length) { // quick check on the two ends: if (leftEnd != '-' && arrangement[0] != leftEnd) return false; if (rightEnd != '-' && arrangement[length - 1] != rightEnd) return false; // by now, we know arrangement[0] is permitted to be // sitting at leftEnd, just check everyone compared to right for (int i = 1; i < length; i++) if (mustSitLeftOf.count(arrangement[i-1]) && mustSitLeftOf[arrangement[i-1]] != arrangement[i]) return false; return true; } void printAllPossibleArrangements(map <char, char> &mustSitLeftOf, char & leftEnd, char & rightEnd, int n) { char * arrangement = new char[n+1]; arrangement[n] = '\0'; for (int i=0; i < n; i++) arrangement[i] = 'A' + i; do { if (evaluateArrangement(mustSitLeftOf, leftEnd, rightEnd, arrangement, n)) cout << arrangement << endl; } while (next_permutation(arrangement, arrangement + n)); }