С.И.Хашин
Мы рассматриваем подстановки на множестве из n элементов, а именно
на множестве целых чисел от 0 до n-1.
Так как 21! > 264, то мы в основном будем рассматривать небольшие
подстановки, но многие функции будут работать и при n вплоть до 256.
Подстановка из n элементов представляет собой байтовый массив из целых чисел от 0 до n-1, которые все различны. Поэтому базовым классом для подстановок является байтовый массив:
class barray{ // байтовый массив
protected:
int n; // number of elements
BYTE *a; // elements
public:
...
void setN(int n_); // setSize
int getN() { return n;}
BYTE &operator[] (int i); // обращение к элементу массива (с проверкой индексов)
void setA(BYTE *a1); // copy from array
void copyFrom(barray &s); // this := copyFrom(s)
void set(BYTE v0, BYTE v1);
void set(BYTE v0, BYTE v1, BYTE v2);
void set(BYTE v0, BYTE v1, BYTE v2, BYTE v3);
void set(BYTE v0, BYTE v1, BYTE v2, BYTE v3, BYTE v4);
void set(BYTE v0, BYTE v1, BYTE v2, BYTE v3, BYTE v4, BYTE v5);
void set(BYTE v0, BYTE v1, BYTE v2, BYTE v3, BYTE v4, BYTE v5, BYTE v6);
void set(BYTE v0, BYTE v1, BYTE v2, BYTE v3, BYTE v4, BYTE v5, BYTE v6, BYTE v7);
void set(BYTE v0, BYTE v1, BYTE v2, BYTE v3, BYTE v4, BYTE v5, BYTE v6, BYTE v7, BYTE v8);
void set(BYTE v0, BYTE v1, BYTE v2, BYTE v3, BYTE v4, BYTE v5, BYTE v6, BYTE v7, BYTE v8, BYTE v9);
char *toString();
bool isEqual(barray &s); // this == s?
bool operator==(barray &s);
bool isSubs(); // all elements are different
void sort(); // (22031) -> (32210)
};
Примеры работы:
barray ba;
ba.set(2, 2, 0, 3, 1);
printf(" ini: %s\n", ba.toString());
ba.sort();
printf(" srt: %s\n", ba.toString());
Результат:
ini: 22031 srt: 32210
Класс подстановок является наследником байтового массива:
class subs: public barray{
public:
// constructors/destructor
subs(int n_ = 0);
char *toStringS(); // разложение на циклы
void setId(); // Единичная подстановка
void mult(subs &s1, subs &s2); // Умножение подстановок
void div(subs &s1, subs &s2); // this := s1/s2
void revers(subs &s); // Обратная подстановка
bool isCommut(subs &s); // Будет ли s*this == this*s ?
bool isH(); // Подстановка без неподвижных точек?
unsigned index(); // index of substitution
// можно применять только при n<=12 (13!>2^32)
unsigned long long index64(); // index of substitution
// можно применять только при n<=20 (21!>2^64)
void setByIndex(unsigned ind); // this := substitution number ind, n<=12
void setByIndex64(unsigned long long ind); // this := substitution number ind, n<=20
bool isE(); // Будет ли подстановка единичной
bool isSim(subs &s); // this/s без неподвижных точек?
int fixCount(); // количество неподвижных точек
void stype(barray &ba); // ba:=тип разложения на циклы подстановки this,
// например при this=(01)(2)(3456)(78)(9),
// получим ba=(422110000)
int nKind(); // количество типов подстановок данного размера
int itype(); // номер типа подстановки
void set_min(int k); // минимальная подстановка типа k
void conj(subs &r, subs &t); // this := r*t/r
bool Find_conj(subs &r, subs &t); // this := s such, that: t = s*r/s,
};
Опишем некоторые методы более подробно.
Все подстановки пронумерованы от 0 до n!-1. Узнать номер (индекс) подстановки
позволяет функции index() и index64().
Замечание. Индексы подстановок упорядочены лексикографически.
То есть, если индекс s1 меньше индекса s2, то s1 лексикографически меньше s2.
Обратную операцию – построить подстановку с данным номером (индексом) выполняют фунцкии setByIndex() и setByIndex64().
subs s(18);
unsigned long long ind, in2;
ind = 3591172723459074ULL;
s.setByIndex64(ind);
in2 = s.index64();
printf("%20llu %20llu %s\n", ind, in2, s.toStringS());
Получаем:
3591172723459074 3591172723459074 (hbdf50a)(34862c)(9g)
Ещё пример:
int N = 3;
subs s(N);
for (unsigned i = 0; i < factorial(N); i++) {
s.setByIndex(i);
printf("%2d: {%s} = ", i, s.toString());
printf("%s\n", s.toStringS());
}
Получаем:
0: {012} = Id
1: {021} = (12)
2: {102} = (01)
3: {120} = (012)
4: {201} = (021)
5: {210} = (02)
Напомним, что числа – элементы подстановки, большие 9 отображаются маленькими латинскими буквами: a,b,c,... и циклы длины 1, в данном случае (1) и (e) не показываются.
Умножение и деление.
t3.div(t1,t2);
t4.mult(t3,t2);
В результате получаем t4==t1.
В моих вычислениях мне часто требовалось проверить для двух подстановок σ и τ будет ли подстановка σ τ-1 иметь неподвижные точки? Это можно выяснить с помощью функции
bool isSim(subs &s); // this/s без неподвижных точек?
Типом разложения на циклы подстановки будем называть список с количеством циклов каждой длины.
subs s;
...
barray ba;
s.stype(ba);
Различных типов подстановов без неподвижных точек при данной длине немного:
N : 2,3,4,5,6,7,8,9,10, ...
количество типов подстановок: 1,1,2,2,4,4,7,8,12, ...
Количество типов подстановок без неподвижных точек возвращается функцией
int nKind(); // количество типов подстановок данного размера
Перенумеруем все возможные типы подстановок (без неподвижных точек). Номер типа данной подстановки можно узнать функцией
int itype(); // номер типа подстановки
Среди всех подстановок данного типа выделим одну – минимальную в лексикографическом порядке.
Её можно получить функцией
void set_min(int k); // минимальная подстановка типа k
Следующие функции связаны с сопряженными подстановками:
void conj(subs &r, subs &t); // this := r*t/r
bool Find_conj(subs &r, subs &t); // this := s such, that: t = s*r/s,
Функция conj просто строит сопряжённую подстановку, а
функция Find_conj для данной пары подстановок r и t ищет сопрягающую
подстановку. Если такой не существует, то есть подстановки не сопряжены, возвращается false.
Пример использования:
const int N = 5;
subs s(N);
s.setByIndex(7);
printf("s =<%s> = ", s.toString());
printf("%s\n", s.toStringS());
subs r(N), t(N), tr(N), g(N);
r.setByIndex(16);
if (t.Find_conj(s, r)) {
printf("r =<%s> = ", r.toString());
printf("%s\n", r.toStringS());
printf("t =<%s> = ", t.toString());
printf("%s\n", t.toStringS());
tr.revers(t); // tr = 1/t
g.mult(s, tr); // g = s/t
g.mult(t, g); // g = t*s/t
if (g.isEqual(r)) printf("Ok 1!\n");
// проверка с помощью функции conj:
g.conj(t, s); // g = t*s/t
if (g.isEqual(r)) printf("Ok 2!\n");
}
Получаем:
s =<02143> = (12)(34) r =<03412> = (13)(24) t =<01324> = (23) Ok 1! Ok 2!