sage-main: a6e4e7605c30 sage/combinat/designs/covering

sage-main

view sage/combinat/designs/covering_design.py @ 11462:a6e4e7605c30

modifications to answer the comments

author	Daniel Gordon <gordon@ccrwest.org>
date	Tue Jan 27 14:57:53 2009 -0800 (19 months ago)
parents	b6e6c7924777
children	da7ed8fbd34e

line source

1 r"""

2 Covering designs: coverings of $t$-element subsets of a $v$-set by $k$-sets

4 A $(v,k,t)$ covering design $C$ is an incidence structure consisting of a

5 set of points $P$ of order $v$, and a set of blocks $B$, where each

6 block contains $k$ points of $P$. Every $t$-element subset of $P$

7 must be contained in at least one block.

9 If every $t$-set is contained in exactly one block of $C$, then we

10 have a block design. Following the block design implementation, the

11 standard representation of a covering design uses $P = [0,1,..., v-1]$.

13 There is an online database of the best known covering designs, the La

14 Jolla Covering Repository (LJCR), at [1]. This is maintained with an SQL

15 database, also in Sage, but since it changes frequently, and is over

16 60MB, that code is not included here. A user may get individual

17 coverings from the LJCR using best_known_covering_design_www.

19 In addition to the parameters and incidence structure for a covering

20 design from this database, we include extra information:

22 \begin{itemize}

23 \item Best known lower bound on the size of a (v,k,t)-covering design

24 \item Name of the person(s) who produced the design

25 \item Method of construction used

26 \item Date when the design was added to the database

27 \end{itemize}

29 REFERENCES

30 [1] La Jolla Covering Repository, http://www.ccrwest.org/cover.html

31 [2] Coverings, by Daniel Gordon and Douglas Stinson,

32 http://www.ccrwest.org/gordon/hcd.pdf, in Handbook of Combinatorial Designs

35 AUTHORS:

36 -- Daniel M. Gordon (2008-12-22): initial version

38 """

40 #*****************************************************************************

42 #

43 # Distributed under the terms of the GNU General Public License (GPL)

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

45 #*****************************************************************************

47 import types

48 import urllib

49 from sage.misc.sage_eval import sage_eval

50 from sage.structure.sage_object import SageObject

51 from sage.rings.integer import Integer

52 from sage.rings.rational import Rational

53 from sage.rings.integer_ring import ZZ

54 from sage.rings.arith import binomial

55 from sage.combinat.combination import Combinations

56 from sage.combinat.designs.incidence_structures import IncidenceStructure

58 ###################### covering design functions ##############################

61 def schonheim(v,k,t):

62 r"""

63 Schonheim lower bound for size of covering design

66 INPUT:

67 v -- integer, size of point set

68 k -- integer, cardinality of each block

69 t -- integer, cardinality of sets being covered

71 OUTPUT:

72 The Schonheim lower bound for such a covering design's size:

73 $C(v,k,t) \leq \lceil(\frac{v}{k} \lceil \frac{v-1}{k-1} \cdots \lceil \frac{v-t+1}{k-t+1} \rceil \cdots \rceil \rceil$

75 EXAMPLES:

76 sage: from sage.combinat.designs.covering_design import schonheim

77 sage: schonheim(10,3,2)

78 17

79 sage: schonheim(32,16,8)

80 930

81 """

82 bound = 1

83 for i in range(t-1,-1,-1):

84 bound = Rational((bound*(v-i),k-i)).ceil()

86 return bound

89 def trivial_covering_design(v,k,t):

90 r"""

91 Construct a trivial covering design.

93 INPUT:

94 v -- integer, size of point set

95 k -- integer, cardinality of each block

96 t -- integer, cardinality of sets being covered

98 OUTPUT:

99 (v,k,t) covering design

100

101 EXAMPLE:

102 sage: C = trivial_covering_design(8,3,1)

103 sage: print C

104 C(8,3,1) = 3

105 Method: Trivial

106 0 1 2

107 0 6 7

108 3 4 5

109 sage: C = trivial_covering_design(5,3,2)

110 sage: print C

111 4 <= C(5,3,2) <= 10

112 Method: Trivial

113 0 1 2

114 0 1 3

115 0 1 4

116 0 2 3

117 0 2 4

118 0 3 4

119 1 2 3

120 1 2 4

121 1 3 4

122 2 3 4

123

124 NOTES:

125 Cases are:

126 \begin{enumerate}

127 \item $t=0$: This could be empty, but it's a useful convention to

128 have one block (which is empty if $k=0$).

129 \item $t=1$: This contains $\lceil v/k \rceil$ blocks:

130 $[0,...,k-1]$,[k,...,2k-1],...$. The last block

131 wraps around if $k$ does not divide $v$.

132 \item anything else: Just use every $k$-subset of $[0,1,...,v-1]$.

133 \end{enumerate}

134

135 """

136 if t==0: #single block [0,...,k-1]

137 blk=[]

138 for i in range(k):

139 blk.append(i)

140 return CoveringDesign(v,k,t,1,range(v),[blk],1,"Trivial")

141

142 if t==1: #blocks [0,...,k-1],[k,...,2k-1],...

143 size = Rational((v,k)).ceil()

144 blocks=[]

145 for i in range(size-1):

146 blk=[]

147 for j in range(i*k,(i+1)*k):

148 blk.append(j)

149 blocks.append(blk)

150

151 blk=[] # last block: if k does not divide v, wrap around

152 for j in range((size-1)*k,v):

153 blk.append(j)

154 for j in range(k-len(blk)):

155 blk.append(j)

156 blk.sort()

157 blocks.append(blk)

158 return CoveringDesign(v,k,t,size,range(v),blocks,size,"Trivial")

159

160 # default case, all k-subsets

161 return CoveringDesign(v,k,t,binomial(v,k),range(v),Combinations(range(v),k),schonheim(v,k,t),"Trivial")

162

163

164 class CoveringDesign(SageObject):

165 """

166 Covering design.

167

168 INPUT:

169 data -- parameters (v,k,t)

170 size

171 incidence structure (points and blocks) -- default points are $[0,...v-1]$

172 lower bound for such a design

173 database information: creator, method, timestamp

174 """

175

176 def __init__(self, v=0, k=0, t=0, size=0, points=[], blocks=[], low_bd=0, method='', creator ='',timestamp=''):

177 """

178 EXAMPLES:

179 sage: C=CoveringDesign(5,4,3,4,range(5),[[0,1,2,3],[0,1,2,4],[0,1,3,4],[0,2,3,4]],4, 'Lexicographic Covering')

180 sage: print C

181 C(5,4,3) = 4

182 Method: Lexicographic Covering

183 0 1 2 3

184 0 1 2 4

185 0 1 3 4

186 0 2 3 4

187 """

188 self.__v = v

189 self.__k = k

190 self.__t = t

191 self.__size = size

192 if low_bd > 0:

193 self.__low_bd = low_bd

194 else:

195 self.__low_bd = schonheim(v,k,t)

196 self.__method = method

197 self.__creator = creator

198 self.__timestamp = timestamp

199 self.__incidence_structure = IncidenceStructure(points, blocks)

200

201

202 def __repr__(self):

203 """

204 A print method, giving the parameters and any other information about the covering (but not the blocks).

205

206 EXAMPLES:

207 sage: C=CoveringDesign(7,3,2,7,range(7),[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]],0, 'Projective Plane')

208 sage: C

209 (7,3,2)-covering design of size 7

210 Lower bound: 7

211 Method: Projective Plane

212 """

213 repr = '(%d,%d,%d)-covering design of size %d\n'%(self.__v,self.__k,self.__t,self.__size)

214 repr += 'Lower bound: %d\n'%(self.__low_bd)

215 if self.__creator != '':

216 repr += 'Created by: %s\n'%(self.__creator)

217 if self.__method != '':

218 repr += 'Method: %s\n'%(self.__method)

219 if self.__timestamp != '':

220 repr += 'Submitted on: %s\n'%(self.__timestamp)

221

222 return repr

223

224

225 def __str__(self):

226 """

227 A print method, displaying a covering design's parameters and blocks.

228

229 OUTPUT:

230 covering design parameters and blocks, in a readable form

231

232 EXAMPLES:

233 sage: C=CoveringDesign(7,3,2,7,range(7),[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]],0, 'Projective Plane')

234 sage: print C

235 C(7,3,2) = 7

236 Method: Projective Plane

237 0 1 2

238 0 3 4

239 0 5 6

240 1 3 5

241 1 4 6

242 2 3 6

243 2 4 5

244 """

245 if self.__size == self.__low_bd: # check if the covering is known to be optimal

246 repr = 'C(%d,%d,%d) = %d\n'%(self.__v,self.__k,self.__t,self.__size)

247 else:

248 repr = '%d <= C(%d,%d,%d) <= %d\n'%(self.__low_bd,self.__v,self.__k,self.__t,self.__size);

249 if self.__creator != '':

250 repr += 'Created by: %s\n'%(self.__creator)

251 if self.__method != '':

252 repr += 'Method: %s\n'%(self.__method)

253 if self.__timestamp != '':

254 repr += 'Submitted on: %s\n'%(self.__timestamp)

255 for i in range(self.__size):

256 for j in range(self.__k):

257 repr = repr + str(self.__incidence_structure.blocks()[i][j]) + ' '

258 repr += '\n'

259

260 return repr

261

262

263 def is_covering(self):

264 """

265 Checks that all t-sets are in fact covered.

266

267 INPUT:

268 putative covering design

269

270 OUTPUT:

271 True if all t-sets are in at least one block

272

273

274 NOTES:

275 This is very slow and wasteful of memory. A faster cython

276 version will be added soon.

277

278 EXAMPLES:

279 sage: C=CoveringDesign(7,3,2,7,range(7),[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]],0, 'Projective Plane')

280 sage: C.is_covering()

281 True

282 sage: C=CoveringDesign(7,3,2,7,range(7),[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 6]],0, 'not a covering') # last block altered

283 sage: C.is_covering()

284 False

285 """

286 v = self.__v

287 k = self.__k

288 t = self.__t

289 Svt = Combinations(range(v),t)

290 Skt = Combinations(range(k),t)

291 tset = {} # tables of t-sets: False = uncovered, True = covered

292 for i in Svt:

293 tset[tuple(i)] = False

294

295 # mark all t-sets covered by each block

296 for a in self.__incidence_structure.blocks():

297 for z in Skt:

298 y = [a[x] for x in z]

299 tset[tuple(y)] = True

300

301 for i in Svt:

302 if tset[tuple(i)] == False: # uncovered

303 return False

304

305 return True # everything was covered

306

307

308 def v(self):

309 """

310 Return v, the number of points in the covering design

311

312 EXAMPLES:

313 sage: from sage.combinat.designs.covering_design import CoveringDesign

314 sage: C=CoveringDesign(7,3,2,7,range(7),[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]],0, 'Projective Plane')

315 sage: C.v()

316 7

317 """

318 return self.__v

319

320

321 def k(self):

322 """

323 Return k, the size of blocks of the covering design

324

325 EXAMPLES:

326 sage: from sage.combinat.designs.covering_design import CoveringDesign

327 sage: C=CoveringDesign(7,3,2,7,range(7),[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]],0, 'Projective Plane')

328 sage: C.k()

329 3

330 """

331 return self.__k

332

333

334 def t(self):

335 """

336 Return t, the size of sets which must be covered by the blocks of the covering design

337

338 EXAMPLES:

339 sage: from sage.combinat.designs.covering_design import CoveringDesign

340 sage: C=CoveringDesign(7,3,2,7,range(7),[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]],0, 'Projective Plane')

341 sage: C.t()

342 2

343 """

344 return self.__t

345

346 def size(self):

347 """

348 Return the number of blocks in the covering design

349

350 EXAMPLES:

351 sage: from sage.combinat.designs.covering_design import CoveringDesign

352 sage: C=CoveringDesign(7,3,2,7,range(7),[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]],0, 'Projective Plane')

353 sage: C.size()

354 7

355 """

356 return self.__size

357

358

359 def low_bd(self):

360 """

361 Return a lower bound for the number of blocks a covering design with these parameters could have.

362 Typically this is the Schonheim bound, but for some parameters better bounds have been shown.

363

364 EXAMPLES:

365 sage: from sage.combinat.designs.covering_design import CoveringDesign

366 sage: C=CoveringDesign(7,3,2,7,range(7),[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]],0, 'Projective Plane')

367 sage: C.low_bd()

368 7

369 """

370 return self.__low_bd

371

372

373 def method(self):

374 """

375 Return the method used to create the covering design

376 This field is optional, and is used in a database to give information about how coverings were constructed

377

378 EXAMPLES:

379 sage: from sage.combinat.designs.covering_design import CoveringDesign

380 sage: C=CoveringDesign(7,3,2,7,range(7),[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]],0, 'Projective Plane')

381 sage: C.method()

382 'Projective Plane'

383 """

384 return self.__method

385

386

387 def creator(self):

388 """

389 Return the creator of the covering design

390 This field is optional, and is used in a database to give attribution for the covering design

391 It can refer to the person who submitted it, or who originally gave a construction

392

393 EXAMPLES:

394 sage: from sage.combinat.designs.covering_design import CoveringDesign

395 sage: C=CoveringDesign(7,3,2,7,range(7),[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]],0, 'Projective Plane','Gino Fano')

396 sage: C.creator()

397 'Gino Fano'

398 """

399 return self.__creator

400

401

402 def timestamp(self):

403 """

404 Return the time that the covering was submitted to the database

405

406 EXAMPLES:

407 sage: from sage.combinat.designs.covering_design import CoveringDesign

408 sage: C=CoveringDesign(7,3,2,7,range(7),[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]],0, 'Projective Plane','Gino Fano','1892-01-01 00:00:00')

409 sage: C.timestamp() #Fano had an article in 1892, I don't know the date it appeared

410 '1892-01-01 00:00:00'

411 """

412 return self.__timestamp

413

414

415 def incidence_structure(self):

416 """

417 Return the incidence structure of a covering design, without all the extra parameters.

418

419 EXAMPLES:

420 sage: from sage.combinat.designs.covering_design import CoveringDesign