1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
// Copyright (C) 1995 The New York Group Theory Cooperative
// See magnus/doc/COPYRIGHT for the full notice.
// Contents: Definition and implementation of utility class
// EnumeratorOfWordTuples.
//
// Principal Authors: Eugeny Paderin, Dmitry Pechkin
//
// Status: in progress
//
// Revision History:
//
// Special remarks:
//
// * Class EnumeratorOfWordTuple is implemented for to allow enumerating
// of tuple of word which may contain different number of generators.
//
// It implicitly uses techniques of meta-enumerator:
// enumerator of enumerators. Low level enumerators should supply only
// two operations: reset(restart) and get a next element.
// @dp do we want meta-enumerator at all?
//
// * Efficiency of the class depends on ability of Word::nextFreelyReduced()
// to effectively produce next freely reduced word.
//
// * Usage:
//
// Semantics of using of class EnumeratorOfWordTuple is like iterator.
//
// Example of use:
//
// FreeGroup F2(2);
// FreeGroup F3(3);
// EnumeratorOfWordTuple tuple(3, 2);
//
// // Enumerating of maps F3 to F2:
// while( 1 ) {
// VectorOf<Word> images = tuple.value();
// Map M(F3, F2, images);
// cout << M << endl;
// ewt.next();
// }
//
// More complex example:
// Enumerating of maps from F3 into F2 and from F2 into F3 simultaneously.
//
// VectorOf<int> gens(5);
// gens[0]=gens[1]=gens[2]= 2; // 3 gens in the domain, 2 gens in the range
// gens[3]=gens[4]= 3; // 2 gens in the domain, 3 gens in the range
// EnumeratorOfWordTuples tuples(gens);
// for(i = 0; i<100; i++) {
// VectorOf<Word> images = tuples.value();
// Map M32(F3,F2);
// for(int j = 0; j<3; j++)
// M32.setGeneratingImages(j, images[j]);
// cout << "F3->F2: " << M32 << "; ";
// Map M23(F2, F3);
// for(j = 0; j<2; j++)
// M23.setGeneratingImages(j, images[j+3]);
// cout << "F2->F3: " << M23 << endl;
// tuples.next();
// }
//
//
#ifndef _TUPLE_ENUMERATOR_H_
#define _TUPLE_ENUMERATOR_H_
#include "Vector.h"
#include "Word.h"
class EnumeratorOfWordTuples
{
public:
///////////////////////////////////////////////////////////////////
// //
// Constructors //
// //
///////////////////////////////////////////////////////////////////
// no default constructor
EnumeratorOfWordTuples(VectorOf<int> numOfGens) :
tupleSize(numOfGens.length()), tuple(numOfGens.length()),
maxWord(numOfGens.length()), numberOfGens(numOfGens),
fixedWord(0) {}
EnumeratorOfWordTuples(int size, int numOfGens) :
tupleSize(size), tuple(size), maxWord(size),
numberOfGens(size), fixedWord(0)
{
for(int i=0; i<size; i++)
numberOfGens[i] = numOfGens;
}
// copy constructor, operator=, and destructor provided by compiler.
///////////////////////////////////////////////////////////////////
// //
// Methods //
// //
///////////////////////////////////////////////////////////////////
void reset() {
for(int i=0; i<tupleSize; i++)
tuple[i] = maxWord[i] = Word();
fixedWord = tupleSize;
}
// Resets this enumerator to the state it was in after construction.
void next();
// Advances this enumerator.
VectorOf<Word> value() const { return tuple; }
// Returns the current value.
private:
// Data members:
int tupleSize;
VectorOf<Word> tuple;
VectorOf<Word> maxWord;
VectorOf<int> numberOfGens;
int fixedWord;
};
class CantorEnumeration {
public:
static Integer encodePair( const Integer& x, const Integer& y);
static void decodePair( const Integer& n, Integer& x, Integer& y );
static Integer encodeTuple( const VectorOf<Integer>& tuple );
static VectorOf<Integer> decodeTuple( const Integer& number );
};
#endif
|
