#include #include #include const char* copy(const char* s) { if (s == 0) return 0; char* r = new char[strlen(s)+1]; strcpy(r, s); return r; } const char* copy(const char* s, const char* e) { int len = e - s; char* r = new char[len + 1]; strncpy(r, s, len); r[len] = '\0'; return r; } int compare(const char* a, const char* b) { int len_a = strlen(a); int len_b = strlen(b); if (len_a < len_b) return -1; if (len_a > len_b) return 1; return strcmp(a, b); } const char* name(const char* s) { return *s == '\0' ? "I" : s; } class Reduction { public: Reduction(char l, const char* f, const char* t, Reduction* n) : letter(l), from(copy(f)), to(copy(t)), partialOfI(false), next_sibling(n), children(0) {} Reduction(char l, const char* f, const char* fe, const char* t, Reduction* n) : letter(l), from(copy(f, fe)), to(copy(t)), partialOfI(false), next_sibling(n), children(0) {} ~Reduction() { delete from; delete to; delete next_sibling; delete children; } char letter; const char* from; const char* to; bool partialOfI; // partial sequence of a sequence that reduces to I Reduction* next_sibling; Reduction* children; void print(int depth) { printf("%d '%s'", depth, from); if (to != 0) printf(" -> %s", to); printf("\n"); if (children != 0) children->print(depth+1); if (next_sibling != 0) next_sibling->print(depth); } }; Reduction *reductions = 0; bool addReduction(Reduction** ref_red, const char* at, const char* from, const char* to, bool &error) { bool result = true; while (*ref_red != 0 && (*ref_red)->letter < *at) ref_red = &(*ref_red)->next_sibling; if (at[1] == '\0') { if (*ref_red != 0 && (*ref_red)->letter == *at) { if (to != 0) { if ((*ref_red)->partialOfI && *to == '\0') error = true; // found a partial sequence of a sequence that reduces to I if ((*ref_red)->to != 0) { int comp = compare(to, (*ref_red)->to); if (comp >= 0) return false; // found a longer or equal reduction for 'from'; nothing added else error = true; // found a shorter reduction: should maybe not occur } (*ref_red)->to = copy(to); } } else (*ref_red) = new Reduction(at[0], from, to, *ref_red); } else { if (*ref_red == 0 || (*ref_red)->letter != *at) (*ref_red) = new Reduction(at[0], from, at+1, 0, *ref_red); else result = false; if (to != 0 && *to == '\0') (*ref_red)->partialOfI = true; if (addReduction(&(*ref_red)->children, at+1, from, to, error)) result = true; } return result; } void normalize(char *seq) { for (char *s = seq; *s != '\0';) { char *r = s; Reduction* red = 0; Reduction* child = reductions; for (;*r != '\0';r++) { for (; child != 0; child = child->next_sibling) { if (child->letter == *r) break; } if (child == 0) { red = 0; break; } red = child; if (red->to != 0) break; child = red->children; } if (red != 0 && red->to != 0) { char *t = s; for (const char *k = red->to; *k != '\0'; k++) *t++ = *k; strcpy(t, r+1); s = seq; } else s++; } } bool addReduction(const char* from, const char* to, bool &error) { if (to != 0 && *to != '\0') addReduction(&reductions, to, to, 0, error); return addReduction(&reductions, from, from, to, error); } Reduction* find(const char* seq) { for (Reduction *reduction = reductions; ; reduction = reduction->children) { while (reduction != 0 && reduction->letter < *seq) reduction = reduction->next_sibling; if (reduction == 0 || reduction->letter != *seq) break; if (*(++seq) == '\0') return reduction; } return 0; } class DepthFirstAllIterator { public: DepthFirstAllIterator(Reduction *root) : _root(root), _depth(0) { _path[0] = _root; } void reset() { _depth = 0; _path[0] = _root; } bool more() { return _path[0] != 0; } void next() { if (_path[_depth]->children != 0 && _depth < 100) { _path[_depth+1] = _path[_depth]->children; _depth++; return; } while(_depth >= 0) { if (_path[_depth]->next_sibling != 0) { _path[_depth] = _path[_depth]->next_sibling; return; } _path[_depth] = 0; _depth--; } } int from_len() { return _depth+1; } const char* from() { return _path[_depth]->from; } const char* to() { return _path[_depth]->to; } private: Reduction* _root; Reduction* _path[100]; int _depth; }; class DepthFirstIterator : public DepthFirstAllIterator { public: DepthFirstIterator(Reduction *root) : DepthFirstAllIterator(root) { while (more() && to() == 0) DepthFirstAllIterator::next(); } void next() { do DepthFirstAllIterator::next(); while (more() && to() == 0); } }; class Iterator { public: Iterator(Reduction* root, int depth = 0) : _it(root), _more(true), _depth(depth) { for (int i = 1; i < 101; i++) _available_length[i] = false; _max_length = 0; for (; _it.more(); _it.next()) { _available_length[_it.from_len()] = true; if (_it.from_len() > _max_length) _max_length = _it.from_len(); } if (_max_length == 0) { _more = false; return; } _cur_length = 1 + depth; if (_cur_length > _max_length) { _more = false; return; } while (!_available_length[_cur_length]) _cur_length++; _it.reset(); while (_it.from_len() != _cur_length) _it.next(); } bool more() { return _more; } void next() { for (;;) { _it.next(); if (!_it.more()) break; if (_it.from_len() == _cur_length) return; } if (++_cur_length > _max_length) { _more = false; return; } while (!_available_length[_cur_length]) _cur_length++; _it.reset(); while (_it.from_len() != _cur_length) _it.next(); } const char *from() { return _it.from(); } const char *to() { return _it.to(); } private: DepthFirstIterator _it; int _depth; bool _available_length[101]; int _max_length; int _cur_length; bool _more; }; void findElements(char *seq, char *at, int &c, FILE* fout) { for (Reduction* r = reductions; r != 0; r = r->next_sibling) { *at = r->letter; at[1] = '\0'; Reduction *red = find(seq); if (red == 0 || red->to == 0) { char buffer[200]; strcpy(buffer, seq); normalize(buffer); if (strcmp(buffer, seq) == 0) { if (fout != 0) fprintf(fout, "= %s\n", seq); c++; findElements(seq, at + 1, c, fout); } else if (fout != 0) fprintf(fout, " %s -> %s\n", seq, buffer); } else if (fout != 0) fprintf(fout, " %s = %s\n", seq, red->to); } } void derive(bool &error) { bool go = true; for (int pass = 0; pass < 10 && go && !error; pass++) { go = false; for (Iterator first_it(reductions); first_it.more(); first_it.next()) { for (const char* common = first_it.from() + 1; *common != '\0'; common++) { Reduction* second = find(common); if (second != 0 && second->children) { for (Iterator second_it(second->children, strlen(common)); second_it.more(); second_it.next()) { char left[200]; sprintf(left, "%.*s%s", common - first_it.from(), first_it.from(), second_it.to() == 0 ? "" : second_it.to()); char right[200]; sprintf(right, "%s%s", first_it.to() == 0 ? "" : first_it.to(), second_it.from() + strlen(common)); normalize(left); normalize(right); if (strcmp(left, right) != 0) { if (compare(left, right) < 0) { if (addReduction(right, left, error)) go = true; } else { if (addReduction(left, right, error)) go = true; } } } } } } } if (go && !error) { printf("== still go after 10 passes\n"); error = true; } } void testCaseCountElements(const char *rule, int size) { delete reductions; reductions = 0; bool error = false; for (const char *s = rule; *s != '\0';) { char buffer[50]; char *t = buffer; while (*s != '\0' && *s != ' ') *t++ = *s++; *t = '\0'; addReduction(buffer, "", error); if (*s == ' ') s++; } derive(error); if (error) { printf("Error: Error during reduction of rule %s\n"); return; } int c = 1; for (DepthFirstAllIterator it(reductions); it.more(); it.next()) if (it.to() == 0) { char buffer[200]; strcpy(buffer, it.from()); normalize(buffer); if (strcmp(buffer, it.from()) == 0) c++; } if (c != size) { c = 1; char seq[200]; findElements(seq, seq, c, 0); } if (c != size) { printf("Error: Counted size %d, instead of expected %d for rule %s\n", c, size, rule); printf("I +\n"); char seq[200]; for (DepthFirstAllIterator it(reductions); it.more(); it.next()) { printf("%s", it.from()); if (it.to() != 0) printf(" -> %s", it.to()); else { char buffer[200]; strcpy(buffer, it.from()); normalize(buffer); if (strcmp(buffer, it.from()) == 0) printf(" +"); else printf(" (-> %s)", buffer); } printf("\n"); } printf("\n"); c = 1; findElements(seq, seq, c, stdout); printf("%d\n", c); return; } printf("Info: Passed rule %s\n", rule); } int main(int argc, char* argv[]) { testCaseCountElements("aa bb abab", 4); // Klein group K4 testCaseCountElements("aaa bb abaab", 6); // group C3xC2 testCaseCountElements("aaa bb abab", 6); // symmetric group S3,dihedral Dih6 (triangle) testCaseCountElements("aaa bb ababab", 12); // alternating group A4 (tetrahedron) testCaseCountElements("aaa bb abaababaab", 24); // group A4xC2 testCaseCountElements("aaa bb ababababab", 60); // alternating group A5 (icosahedron) testCaseCountElements("aaa bbb abab", 12); // alternating group A4 (tetrahedron) testCaseCountElements("aaaa bb abaaab", 8); // group C4xC2 testCaseCountElements("aaaa bb abab", 8); // dihedral group Dih8 (square) testCaseCountElements("aaaa bb abababab aabaab", 16); // group K8:C2 testCaseCountElements("aaaa bbb abaaabb", 12); // group C4xC3 testCaseCountElements("aaaa bbbb ababbb aabb", 8); // dicyclic group Dic8, quaternion Q8 testCaseCountElements("aaaa bbbb abaaabbb", 16); // group C4xC4 testCaseCountElements("aaaa bbbb ababbb", 16); // group C4:C4 testCaseCountElements("aaaaa bbbb abababab aabaaaabbb", 20); // Frobenius group F20 testCaseCountElements("aaaaaa bb abaaaaab", 12); // group C6xC2 testCaseCountElements("aaaaaa bb abab", 12); // dihedral group Dih12 testCaseCountElements("aaaaaa bbbb ababbb aaabb", 12); // dicyclic group Dic12 testCaseCountElements("aaaaaaaa bb abaaaaaaab", 16); // group C8xC2 return 0; }