Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

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

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

from __future__ import print_function, division 

 

from sympy.core.compatibility import range 

from sympy.combinatorics.util import _distribute_gens_by_base 

from sympy.combinatorics import Permutation 

 

rmul = Permutation.rmul 

 

 

def _cmp_perm_lists(first, second): 

""" 

Compare two lists of permutations as sets. 

 

This is used for testing purposes. Since the array form of a 

permutation is currently a list, Permutation is not hashable 

and cannot be put into a set. 

 

Examples 

======== 

 

>>> from sympy.combinatorics.permutations import Permutation 

>>> from sympy.combinatorics.testutil import _cmp_perm_lists 

>>> a = Permutation([0, 2, 3, 4, 1]) 

>>> b = Permutation([1, 2, 0, 4, 3]) 

>>> c = Permutation([3, 4, 0, 1, 2]) 

>>> ls1 = [a, b, c] 

>>> ls2 = [b, c, a] 

>>> _cmp_perm_lists(ls1, ls2) 

True 

 

""" 

return {tuple(a) for a in first} == \ 

{tuple(a) for a in second} 

 

 

def _naive_list_centralizer(self, other, af=False): 

from sympy.combinatorics.perm_groups import PermutationGroup 

""" 

Return a list of elements for the centralizer of a subgroup/set/element. 

 

This is a brute force implementation that goes over all elements of the 

group and checks for membership in the centralizer. It is used to 

test ``.centralizer()`` from ``sympy.combinatorics.perm_groups``. 

 

Examples 

======== 

 

>>> from sympy.combinatorics.testutil import _naive_list_centralizer 

>>> from sympy.combinatorics.named_groups import DihedralGroup 

>>> D = DihedralGroup(4) 

>>> _naive_list_centralizer(D, D) 

[Permutation([0, 1, 2, 3]), Permutation([2, 3, 0, 1])] 

 

See Also 

======== 

 

sympy.combinatorics.perm_groups.centralizer 

 

""" 

from sympy.combinatorics.permutations import _af_commutes_with 

if hasattr(other, 'generators'): 

elements = list(self.generate_dimino(af=True)) 

gens = [x._array_form for x in other.generators] 

commutes_with_gens = lambda x: all(_af_commutes_with(x, gen) for gen in gens) 

centralizer_list = [] 

if not af: 

for element in elements: 

if commutes_with_gens(element): 

centralizer_list.append(Permutation._af_new(element)) 

else: 

for element in elements: 

if commutes_with_gens(element): 

centralizer_list.append(element) 

return centralizer_list 

elif hasattr(other, 'getitem'): 

return _naive_list_centralizer(self, PermutationGroup(other), af) 

elif hasattr(other, 'array_form'): 

return _naive_list_centralizer(self, PermutationGroup([other]), af) 

 

 

def _verify_bsgs(group, base, gens): 

""" 

Verify the correctness of a base and strong generating set. 

 

This is a naive implementation using the definition of a base and a strong 

generating set relative to it. There are other procedures for 

verifying a base and strong generating set, but this one will 

serve for more robust testing. 

 

Examples 

======== 

 

>>> from sympy.combinatorics.named_groups import AlternatingGroup 

>>> from sympy.combinatorics.testutil import _verify_bsgs 

>>> A = AlternatingGroup(4) 

>>> A.schreier_sims() 

>>> _verify_bsgs(A, A.base, A.strong_gens) 

True 

 

See Also 

======== 

 

sympy.combinatorics.perm_groups.PermutationGroup.schreier_sims 

 

""" 

from sympy.combinatorics.perm_groups import PermutationGroup 

strong_gens_distr = _distribute_gens_by_base(base, gens) 

current_stabilizer = group 

for i in range(len(base)): 

candidate = PermutationGroup(strong_gens_distr[i]) 

if current_stabilizer.order() != candidate.order(): 

return False 

current_stabilizer = current_stabilizer.stabilizer(base[i]) 

if current_stabilizer.order() != 1: 

return False 

return True 

 

 

def _verify_centralizer(group, arg, centr=None): 

""" 

Verify the centralizer of a group/set/element inside another group. 

 

This is used for testing ``.centralizer()`` from 

``sympy.combinatorics.perm_groups`` 

 

Examples 

======== 

 

>>> from sympy.combinatorics.named_groups import (SymmetricGroup, 

... AlternatingGroup) 

>>> from sympy.combinatorics.perm_groups import PermutationGroup 

>>> from sympy.combinatorics.permutations import Permutation 

>>> from sympy.combinatorics.testutil import _verify_centralizer 

>>> S = SymmetricGroup(5) 

>>> A = AlternatingGroup(5) 

>>> centr = PermutationGroup([Permutation([0, 1, 2, 3, 4])]) 

>>> _verify_centralizer(S, A, centr) 

True 

 

See Also 

======== 

 

_naive_list_centralizer, 

sympy.combinatorics.perm_groups.PermutationGroup.centralizer, 

_cmp_perm_lists 

 

""" 

if centr is None: 

centr = group.centralizer(arg) 

centr_list = list(centr.generate_dimino(af=True)) 

centr_list_naive = _naive_list_centralizer(group, arg, af=True) 

return _cmp_perm_lists(centr_list, centr_list_naive) 

 

 

def _verify_normal_closure(group, arg, closure=None): 

from sympy.combinatorics.perm_groups import PermutationGroup 

""" 

Verify the normal closure of a subgroup/subset/element in a group. 

 

This is used to test 

sympy.combinatorics.perm_groups.PermutationGroup.normal_closure 

 

Examples 

======== 

 

>>> from sympy.combinatorics.named_groups import (SymmetricGroup, 

... AlternatingGroup) 

>>> from sympy.combinatorics.testutil import _verify_normal_closure 

>>> S = SymmetricGroup(3) 

>>> A = AlternatingGroup(3) 

>>> _verify_normal_closure(S, A, closure=A) 

True 

 

See Also 

======== 

 

sympy.combinatorics.perm_groups.PermutationGroup.normal_closure 

 

""" 

if closure is None: 

closure = group.normal_closure(arg) 

conjugates = set() 

if hasattr(arg, 'generators'): 

subgr_gens = arg.generators 

elif hasattr(arg, '__getitem__'): 

subgr_gens = arg 

elif hasattr(arg, 'array_form'): 

subgr_gens = [arg] 

for el in group.generate_dimino(): 

for gen in subgr_gens: 

conjugates.add(gen ^ el) 

naive_closure = PermutationGroup(list(conjugates)) 

return closure.is_subgroup(naive_closure) 

 

 

def canonicalize_naive(g, dummies, sym, *v): 

""" 

Canonicalize tensor formed by tensors of the different types 

 

g permutation representing the tensor 

dummies list of dummy indices 

msym symmetry of the metric 

 

v is a list of (base_i, gens_i, n_i, sym_i) for tensors of type `i` 

base_i, gens_i BSGS for tensors of this type 

n_i number ot tensors of type `i` 

 

sym_i symmetry under exchange of two component tensors of type `i` 

None no symmetry 

0 commuting 

1 anticommuting 

 

Return 0 if the tensor is zero, else return the array form of 

the permutation representing the canonical form of the tensor. 

 

Examples 

======== 

 

>>> from sympy.combinatorics.testutil import canonicalize_naive 

>>> from sympy.combinatorics.tensor_can import get_symmetric_group_sgs 

>>> from sympy.combinatorics import Permutation, PermutationGroup 

>>> g = Permutation([1, 3, 2, 0, 4, 5]) 

>>> base2, gens2 = get_symmetric_group_sgs(2) 

>>> canonicalize_naive(g, [2, 3], 0, (base2, gens2, 2, 0)) 

[0, 2, 1, 3, 4, 5] 

""" 

from sympy.combinatorics.perm_groups import PermutationGroup 

from sympy.combinatorics.tensor_can import gens_products, dummy_sgs 

from sympy.combinatorics.permutations import Permutation, _af_rmul 

v1 = [] 

for i in range(len(v)): 

base_i, gens_i, n_i, sym_i = v[i] 

v1.append((base_i, gens_i, [[]]*n_i, sym_i)) 

size, sbase, sgens = gens_products(*v1) 

dgens = dummy_sgs(dummies, sym, size-2) 

if isinstance(sym, int): 

num_types = 1 

dummies = [dummies] 

sym = [sym] 

else: 

num_types = len(sym) 

dgens = [] 

for i in range(num_types): 

dgens.extend(dummy_sgs(dummies[i], sym[i], size - 2)) 

S = PermutationGroup(sgens) 

D = PermutationGroup([Permutation(x) for x in dgens]) 

dlist = list(D.generate(af=True)) 

g = g.array_form 

st = set() 

for s in S.generate(af=True): 

h = _af_rmul(g, s) 

for d in dlist: 

q = tuple(_af_rmul(d, h)) 

st.add(q) 

a = list(st) 

a.sort() 

prev = (0,)*size 

for h in a: 

if h[:-2] == prev[:-2]: 

if h[-1] != prev[-1]: 

return 0 

prev = h 

return list(a[0]) 

 

 

def graph_certificate(gr): 

""" 

Return a certificate for the graph 

 

gr adjacency list 

 

The graph is assumed to be unoriented and without 

external lines. 

 

Associate to each vertex of the graph a symmetric tensor with 

number of indices equal to the degree of the vertex; indices 

are contracted when they correspond to the same line of the graph. 

The canonical form of the tensor gives a certificate for the graph. 

 

This is not an efficient algorithm to get the certificate of a graph. 

 

Examples 

======== 

 

>>> from sympy.combinatorics.testutil import graph_certificate 

>>> gr1 = {0:[1, 2, 3, 5], 1:[0, 2, 4], 2:[0, 1, 3, 4], 3:[0, 2, 4], 4:[1, 2, 3, 5], 5:[0, 4]} 

>>> gr2 = {0:[1, 5], 1:[0, 2, 3, 4], 2:[1, 3, 5], 3:[1, 2, 4, 5], 4:[1, 3, 5], 5:[0, 2, 3, 4]} 

>>> c1 = graph_certificate(gr1) 

>>> c2 = graph_certificate(gr2) 

>>> c1 

[0, 2, 4, 6, 1, 8, 10, 12, 3, 14, 16, 18, 5, 9, 15, 7, 11, 17, 13, 19, 20, 21] 

>>> c1 == c2 

True 

""" 

from sympy.combinatorics.permutations import _af_invert 

from sympy.combinatorics.tensor_can import get_symmetric_group_sgs, canonicalize 

items = list(gr.items()) 

items.sort(key=lambda x: len(x[1]), reverse=True) 

pvert = [x[0] for x in items] 

pvert = _af_invert(pvert) 

 

# the indices of the tensor are twice the number of lines of the graph 

num_indices = 0 

for v, neigh in items: 

num_indices += len(neigh) 

# associate to each vertex its indices; for each line 

# between two vertices assign the 

# even index to the vertex which comes first in items, 

# the odd index to the other vertex 

vertices = [[] for i in items] 

i = 0 

for v, neigh in items: 

for v2 in neigh: 

if pvert[v] < pvert[v2]: 

vertices[pvert[v]].append(i) 

vertices[pvert[v2]].append(i+1) 

i += 2 

g = [] 

for v in vertices: 

g.extend(v) 

assert len(g) == num_indices 

g += [num_indices, num_indices + 1] 

size = num_indices + 2 

assert sorted(g) == list(range(size)) 

g = Permutation(g) 

vlen = [0]*(len(vertices[0])+1) 

for neigh in vertices: 

vlen[len(neigh)] += 1 

v = [] 

for i in range(len(vlen)): 

n = vlen[i] 

if n: 

base, gens = get_symmetric_group_sgs(i) 

v.append((base, gens, n, 0)) 

v.reverse() 

dummies = list(range(num_indices)) 

can = canonicalize(g, dummies, 0, *v) 

return can