1################################################################################
2##  This program is free software: you can redistribute it and/or modify
3##  it under the terms of the GNU General Public License as published by
4##  the Free Software Foundation, either version 2 of the License, or
5##  (at your option) any later version.
6##
7##  This program is distributed in the hope that it will be useful,
8##  but WITHOUT ANY WARRANTY; without even the implied warranty of
9##  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10##  GNU General Public License for more details.
11##
12#W  inversion.gi						Ruth Hoffmann
13##
14##
15#Y  Copyright (C) 2004-2015 School of Computer Science,
16#Y                          University of St. Andrews, North Haugh,
17#Y                          St. Andrews, Fife KY16 9SS, Scotland
18##
19
20################################################################################
21##
22#F InversionAut(k)
23##
24## InversionAut builds the automaton that accepts all permutations under the
25## rank encoding with exactly k inversions.
26##
27##
28InstallGlobalFunction(InversionAut,function(k)
29local siz,alph,strt,acc,trans,temp,i,aut;
30
31siz:=k+3;
32alph:=k+1;
33strt:=[1];
34acc:=[k+2];
35
36trans:=[];
37temp:=[1..k];
38Append(temp,ListWithIdenticalEntries(2,k+2));
39Add(temp,siz);
40Add(trans,temp);
41for i in [2..alph] do
42    temp:=[i..k+1];
43    Append(temp,ListWithIdenticalEntries(i+1,siz));
44    Add(trans,temp);
45od;
46
47aut:=Automaton("det",siz,alph,trans,strt,acc);
48
49return MinimalAutomaton(IntersectionAutomaton(aut,BoundedClassAutomaton(k+1)));
50
51end );
52
53################################################################################
54##
55#F InversionAutOfClass(aut,inv)
56##
57## InvserionAutOfClass returns the automaton that accepts all permutations under
58## the rank encoding, lying in the regular class aut, that have exactly inv
59## inversions.
60##
61InstallGlobalFunction(InversionAutOfClass,function(a,inv)
62local iaut,aaut;
63
64iaut:=InversionAut(inv);
65
66if AlphabetOfAutomaton(a) < AlphabetOfAutomaton(iaut) then
67    aaut:=ExpandAlphabet(a,AlphabetOfAutomaton(iaut));
68elif AlphabetOfAutomaton(a) > AlphabetOfAutomaton(iaut) then
69    iaut:=ExpandAlphabet(iaut,AlphabetOfAutomaton(a));
70else
71    aaut:=a;
72fi;
73
74return IntersectionAutomaton(iaut,aaut);
75
76end );
77
78################################################################################
79##
80#F LoopFreeAut(aut)
81##
82## LoopFreeAut returns the subautomaton of aut that contains no loops of the
83## form (i,i,x) where i is a state and x is any letter in the alphabet.
84##
85InstallGlobalFunction(LoopFreeAut,function(a)
86local trans,j,i;
87
88trans:=List(a!.transitions, ShallowCopy);
89
90for j in [1..Length(trans[1])] do
91    for i in [1..Length(trans)] do
92        Add(trans[i],a!.states+1);
93        if trans[i][j]=j then
94            trans[i][j]:=a!.states+1;
95        fi;
96    od;
97od;
98
99
100return Automaton("det",a!.states+1,a!.alphabet,trans,a!.initial,a!.accepting);
101
102end );
103
104################################################################################
105##
106#F LoopVertexFreeAut(aut)
107##
108## LoopVertexFreeAut builds the subautomaton of aut that does not contain the
109## vertices and their transitions in aut that loop to themselves.
110##
111InstallGlobalFunction(LoopVertexFreeAut,function(a)
112local acc,ll,trans,i,j,x,sink;
113
114acc:=FinalStatesOfAutomaton(a);
115ll:=[];
116trans:=List(a!.transitions, ShallowCopy);
117sink:=a!.states+1;
118
119for i in [1..Length(trans)] do
120    for j in [1..Length(trans[i])] do
121        if trans[i][j]=j then
122            Add(ll,j);
123        fi;
124        Add(trans[i],sink);
125    od;
126od;
127
128for x in [1..a!.states] do
129    if x in ll then
130        for i in [1..Length(trans)] do
131       	    Unbind(trans[i][x]);
132        od;
133    else
134        for i in [1..Length(trans)] do
135            if trans[i][x] in ll then
136                trans[i][x]:=sink;
137            fi;
138        od;
139    fi;
140od;
141
142return MinimalAutomaton(Automaton("nondet",a!.states+1,a!.alphabet,trans,a!.initial,a!.accepting));
143
144end );
145