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

r""" 

Enumerated set of lists of integers with constraints: front-end 

 

- :class:`IntegerLists`: class which models an enumerated set of lists 

of integers with certain constraints. This is a Python front-end 

where all user-accessible functionality should be implemented. 

""" 

 

#***************************************************************************** 

# Copyright (C) 2015 Bryan Gillespie <Brg008@gmail.com> 

# Nicolas M. Thiery <nthiery at users.sf.net> 

# Anne Schilling <anne@math.ucdavis.edu> 

# Jeroen Demeyer <jdemeyer@cage.ugent.be> 

# 

# This program is free software: you can redistribute it and/or modify 

# it under the terms of the GNU General Public License as published by 

# the Free Software Foundation, either version 2 of the License, or 

# (at your option) any later version. 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

 

 

from inspect import ismethod 

from sage.categories.enumerated_sets import EnumeratedSets 

from sage.structure.list_clone import ClonableArray 

from sage.structure.parent import Parent 

from sage.combinat.integer_lists.base import IntegerListsBackend 

from six import get_method_function 

 

 

class IntegerList(ClonableArray): 

""" 

Element class for :class:`IntegerLists`. 

""" 

def check(self): 

""" 

Check to make sure this is a valid element in its 

:class:`IntegerLists` parent. 

 

EXAMPLES:: 

 

sage: C = IntegerListsLex(4) 

sage: C([4]).check() 

True 

sage: C([5]).check() 

False 

""" 

return self in self.parent() 

 

 

class IntegerLists(Parent): 

""" 

Enumerated set of lists of integers with constraints. 

 

Currently, this is simply an abstract base class which should not 

be used by itself. See :class:`IntegerListsLex` for a class which 

can be used by end users. 

 

``IntegerLists`` is just a Python front-end, acting as a 

:class:`Parent`, supporting element classes and so on. 

The attribute ``.backend`` which is an instance of 

:class:`sage.combinat.integer_lists.base.IntegerListsBackend` is the 

Cython back-end which implements all operations such as iteration. 

 

The front-end (i.e. this class) and the back-end are supposed to be 

orthogonal: there is no imposed correspondence between front-ends 

and back-ends. 

 

For example, the set of partitions of 5 and the set of weakly 

decreasing sequences which sum to 5 might be implemented by the 

same back-end, but they will be presented to the user by a 

different front-end. 

 

EXAMPLES:: 

 

sage: from sage.combinat.integer_lists import IntegerLists 

sage: L = IntegerLists(5) 

sage: L 

Integer lists of sum 5 satisfying certain constraints 

 

sage: IntegerListsLex(2, length=3, name="A given name") 

A given name 

""" 

backend = None 

backend_class = IntegerListsBackend 

 

Element = IntegerList 

 

def __init__(self, *args, **kwds): 

""" 

Initialize ``self``. 

 

TESTS:: 

 

sage: from sage.combinat.integer_lists import IntegerLists 

sage: C = IntegerLists(2, length=3) 

sage: C == loads(dumps(C)) 

True 

""" 

if "name" in kwds: 

self.rename(kwds.pop("name")) 

 

if "element_class" in kwds: 

self.Element = kwds.pop("element_class") 

 

if "element_constructor" in kwds: 

element_constructor = kwds.pop("element_constructor") 

elif issubclass(self.Element, ClonableArray): 

# Not all element classes support check=False, but 

# ClonableArray certainly does. 

element_constructor = self._element_constructor_nocheck 

else: 

element_constructor = self._element_constructor_default 

self._element_constructor_ = element_constructor 

 

category = kwds.pop("category", None) 

if category is None: 

category = EnumeratedSets().Finite() 

 

# Let self.backend be some IntegerListsBackend 

self.backend = self.backend_class(*args, **kwds) 

 

Parent.__init__(self, category=category) 

 

def __eq__(self, other): 

r""" 

Return whether ``self == other``. 

 

EXAMPLES:: 

 

sage: C = IntegerListsLex(2, length=3) 

sage: D = IntegerListsLex(2, length=3); L = D.list(); 

sage: E = IntegerListsLex(2, min_length=3) 

sage: F = IntegerListsLex(2, length=3, element_constructor=list) 

sage: G = IntegerListsLex(4, length=3) 

sage: C == C 

True 

sage: C == D 

True 

sage: C == E 

False 

sage: C == F 

False 

sage: C == None 

False 

sage: C == G 

False 

 

This is a minimal implementation enabling pickling tests. It 

is safe, but one would want the two following objects to be 

detected as equal:: 

 

sage: C = IntegerListsLex(2, ceiling=[1,1,1]) 

sage: D = IntegerListsLex(2, ceiling=[1,1,1]) 

sage: C == D 

False 

 

TESTS: 

 

This used to fail due to poor equality testing. See 

:trac:`17979`, comment 433:: 

 

sage: DisjointUnionEnumeratedSets(Family([2,2], 

....: lambda n: IntegerListsLex(n, length=2))).list() 

[[2, 0], [1, 1], [0, 2], [2, 0], [1, 1], [0, 2]] 

sage: DisjointUnionEnumeratedSets(Family([2,2], 

....: lambda n: IntegerListsLex(n, length=1))).list() 

[[2], [2]] 

""" 

if self.__class__ != other.__class__: 

return False 

if self.backend != other.backend: 

return False 

a = self._element_constructor_ 

b = other._element_constructor_ 

if ismethod(a): 

a = get_method_function(a) 

if ismethod(b): 

b = get_method_function(b) 

return a == b 

 

def __ne__(self, other): 

r""" 

Return whether ``self != other``. 

 

EXAMPLES:: 

 

sage: C = IntegerListsLex(2, length=3) 

sage: D = IntegerListsLex(2, length=3); L = D.list(); 

sage: E = IntegerListsLex(2, max_length=3) 

sage: C != D 

False 

sage: C != E 

True 

""" 

return not self == other 

 

def __iter__(self): 

""" 

Return an iterator for the elements of ``self``. 

 

EXAMPLES:: 

 

sage: C = IntegerListsLex(2, length=3) 

sage: list(C) # indirect doctest 

[[2, 0, 0], [1, 1, 0], [1, 0, 1], [0, 2, 0], [0, 1, 1], [0, 0, 2]] 

""" 

return self._element_iter(self.backend._iter(), self._element_constructor_) 

 

@staticmethod 

def _element_iter(itr, constructor): 

""" 

Given an iterator ``itr`` and an element constructor 

``constructor``, iterate over ``constructor(v)`` where `v` 

are the values of ``itr``. 

 

EXAMPLES:: 

 

sage: C = IntegerListsLex(2, length=3) 

sage: list(C._element_iter(C._iter(), tuple)) 

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

""" 

for v in itr: 

yield constructor(v) 

 

def __getattr__(self, name): 

""" 

Get an attribute of the implementation backend. 

 

Ideally, this would be done using multiple inheritance, but 

Python doesn't support that for built-in types. 

 

EXAMPLES:: 

 

sage: C = IntegerListsLex(2, length=3) 

sage: C.min_length 

3 

 

TESTS: 

 

Check that uninitialized instances do not lead to infinite 

recursion because there is no ``backend`` attribute:: 

 

sage: from sage.combinat.integer_lists import IntegerLists 

sage: L = IntegerLists.__new__(IntegerLists) 

sage: L.foo 

Traceback (most recent call last): 

... 

AttributeError: 'NoneType' object has no attribute 'foo' 

""" 

return getattr(self.backend, name) 

 

def __contains__(self, item): 

""" 

Return ``True`` if ``item`` meets the constraints imposed by 

the arguments. 

 

EXAMPLES:: 

 

sage: C = IntegerListsLex(n=2, max_length=3, min_slope=0) 

sage: all(l in C for l in C) 

True 

""" 

return self.backend._contains(item) 

 

def _element_constructor_default(self, l): 

""" 

Default element constructor 

 

EXAMPLES:: 

 

sage: L = IntegerListsLex(4) 

sage: L._element_constructor_default([1,2,3]) 

[1, 2, 3] 

 

We construct a variant of :class:`IntegerLists` with a custom 

element class:: 

 

sage: class MyElt(list): 

....: def __init__(self, parent, x): 

....: list.__init__(self, x) 

sage: from sage.combinat.integer_lists import IntegerLists 

sage: class MyIntegersLists(IntegerLists): 

....: Element = MyElt 

sage: L = MyIntegersLists(5) 

sage: L._element_constructor_ 

<bound method MyIntegersLists._element_constructor_default of Integer lists of sum 5 satisfying certain constraints> 

""" 

return self.element_class(self, l) 

 

def _element_constructor_nocheck(self, l): 

r""" 

A variant of the standard element constructor that passes 

``check=False`` to the element class. 

 

EXAMPLES:: 

 

sage: L = IntegerListsLex(4, max_slope=0) 

sage: L._element_constructor_nocheck([1,2,3]) 

[1, 2, 3] 

 

When relevant, this is assigned to 

``self._element_constructor_`` by :meth:`__init__`, to avoid 

overhead when constructing elements from trusted data in the 

iterator:: 

 

sage: L._element_constructor_ 

<bound method IntegerListsLex._element_constructor_nocheck of ...> 

sage: L._element_constructor_([1,2,3]) 

[1, 2, 3] 

""" 

return self.element_class(self, l, check=False)