]> Git — Sourcephile - reloto-libreoffice.git/blob - tirages.py
Optimise un peu rankOfSequence.
[reloto-libreoffice.git] / tirages.py
1 # -*- coding: utf-8 -*-
2 # Author: Julien Moutinho <julm@autogeree.net>
3 # License: GNU GPLv3 (or later, at your choice)
4
5 from __future__ import unicode_literals
6
7 if 'XSCRIPTCONTEXT' in globals():
8 def getModel():
9 return (XSCRIPTCONTEXT.getDocument(), XSCRIPTCONTEXT.getComponentContext())
10 def debug(msg):
11 return
12 else:
13 from connect_to_libre_office import getModel
14 def debug(msg):
15 print(msg)
16
17 def nAk(n,k):
18 """
19 nAk(n,k) retourne le nombre d’arrangements
20 de longueur k d’un ensemble de longueur n.
21 """
22 if n<0 or k<0 or n<k:
23 return None
24 r = 1
25 for i in range(n-k+1, n+1):
26 r *= i
27 #print("nAk%s = %i" % (str((n,k)), r))
28 return r
29 def nAkLO(n,k):
30 return str(nAk(int(n), int(k)))
31 def nCk(n,k):
32 """
33 nCk(n,k) retourne le nombre de combinaisons
34 de longueur k d’un ensemble de longueur n.
35 """
36 if n<0 or k<0 or n<k:
37 return None
38 if k > n // 2:
39 k = n - k # more efficient and safe with smaller numbers
40 r = 1
41 for i in range(1, k+1):
42 r = r * (n-i+1) // i
43 #print("nCk%s = %i" % (str((n,k)), r))
44 return r
45 def nCkLO(n,k):
46 return str(nCk(int(n), int(k)))
47 def combinOfRank(n,k,rank):
48 """
49 combinOfRank(n, k, r) retourne les indices de permutation
50 de la combinaison de k entiers parmi [1..n]
51 au rang lexicographique r dans [0 .. nCk(n,k)-1].
52
53 Construit chaque choix de la combinaison en prenant le prochain plus grand
54 dont le successeur engendre un nombre de combinaisons
55 qui dépasse le rang restant à atteindre.
56
57 DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, p.26
58 """
59 #print("combinOfRank: "+str((n,k,rank)))
60 if rank<0 or nCk(n,k)<rank:
61 return None
62 i = 1
63 j = 1
64 c = []
65 while True: # for1K
66 if i < k:
67 while True: # uptoRank
68 nbCombins = nCk(n-j, k-i)
69 #print("i=%i j=%i rank=%i nCk(%i-%i,%i-%i)=%i" % (i,j,rank, n,j,k,i,nbCombins))
70 if nbCombins <= rank:
71 j += 1
72 rank -= nbCombins
73 #print("rank -= %i" % nbCombins)
74 else:
75 c.append(j)
76 #print("c = "+str(c))
77 i += 1
78 j += 1
79 break
80 elif i == k:
81 c.append(j+rank) # because when i == k, nbCombins is always 1
82 break
83 else:
84 break
85 return c
86 def sequenceOfRank(n, k, rank):
87 """
88 sequenceOfRank(n, k, r) retourne les indices de permutation
89 de la combinaison de k entiers parmi [1..n]
90 au rang lexicographique r dans [0 .. nAk(n,k)-1].
91
92 rankOfSequence(n, sequenceOfRank(n, k, r)) == r
93 sequenceOfRank(n, len(ns), rankOfSequence(n, ns)) == ns
94
95 DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, p.75-77
96 Computed from left to right to work on k-sequence of permutations
97 instead of only full permutations.
98 """
99 try:
100 rank = int(rank)
101 except ValueError:
102 return None
103 p = []
104 a = nAk(n,k)
105 for i in range(1,k+1): # first pass from left to right
106 a //= n-(i-1) # optimized a = nAk(n-i, k-i)
107 d = rank // a # greatest multiple of a, lower or equal to r
108 rank = rank % a
109 p.append(d+1)
110 for i in range(k-1,-1,-1): # important: from right to left
111 for j in range(i+1,k):
112 if p[j] >= p[i]:
113 p[j] += 1 # promote the positions in the good interval
114 return p
115 def checkSequence(n,ns):
116 """
117 checkSequence(n,ns) returns the range ns flattened
118 if each element is with 1 and n, without repetition.
119 """
120 p = []
121 for row in ns: # flatten range given by LO
122 for col in row:
123 i = int(col)
124 if not(1<=i and i<=n):
125 return None
126 if i in p: # duplicate
127 return None
128 p.append(i)
129 return p
130
131 def rankOfCombin(n,ns):
132 """
133 rankOfCombin(n, ns) retourne le rang lexicographique dans [0 .. nCk(n, length ns)-1]
134 de la combinaison ns d’entiers parmi [1..n].
135
136 WARNING: ns doit être triée de manière ascendante.
137
138 Compte le nombre de combinaisons précédant celle de rang r.
139
140 DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, pp.24-25
141
142 rankOfCombin(n, combinOfRank(n, k, r)) == r
143 combinOfRank(n, len(ns), rankOfCombin(n, ns)) == ns
144 """
145 ns = checkSequence(n, ns)
146 if ns == None:
147 return None
148 ns.sort()
149 k = len(ns)
150 i = 1
151 rank = 0
152 x1 = 0
153 for x in ns:
154 for j in range(x1+1,x-1 +1):
155 rank += nCk(n-j, k-i)
156 i += 1
157 x1 = x
158 return str(rank)
159 def rankOfSequence(n, ns):
160 """
161 rankOfSequence(n, ns) retourne le rang lexicographique dans [0 .. nAk(n, len(ns))-1]
162 de la combinaison ns d’entiers parmi [1..n].
163
164 Compte le nombre d’arrangements précédant celui de rang r.
165
166 DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, pp.74
167 """
168 rank = 0
169 ns = checkSequence(n, ns)
170 if ns == None:
171 return None
172 k = len(ns)
173 a = nAk(n,k)
174 for i in range(1,k+1):
175 a //= n-(i-1) # optimized a = nAk(n-i, k-i)
176 nsi = ns[i-1]
177 #print("ns = "+str(ns))
178 #print("rank += %i * nAk(%i,%i)" % (nsi - 1, n - (i+1), k - (i+1)))
179 rank += (nsi - 1) * nAk(n-i, k-i)
180 for j in range(i,k):
181 if nsi < ns[j]:
182 ns[j] -= 1
183 return str(rank)
184 def bitSize(n):
185 """
186 bitSize(n) retourne le nombre de bits servant à encoder n.
187 """
188 try:
189 n = int(n)
190 except ValueError:
191 return None
192 if n<0:
193 return None
194 r = 0
195 while n > 0:
196 r += 1
197 n //= 2
198 return r
199 def equiprobableBits(n):
200 """
201 equiprobableBits(n) retourne le nombre maximal de bits de i
202 équiprobables quand i parcourt [0 .. n-1].
203
204 Ce nombre est le plus grand 'b' dans [0 .. ] tel que 2**b-1 <= n.
205
206 map(equiprobableBits, range(0, 17+1)) == [0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4]
207 """
208 b = bitSize(n)
209 return (b if n == 2**b-1 else b-1)
210 def bitsOfInteger(m, n):
211 """
212 bitsOfInteger(m, n) retourne les m premiers bits de poids faible
213 encodant le nombre n.
214 """
215 m = int(m)
216 n = int(n)
217 if not(0<=m and 0<=n):
218 return None
219 bs = ""
220 while m > 0:
221 (q,r) = (n//2, n%2)
222 bs = ("1" if r else "0") + bs
223 m -= 1
224 n = q
225 return bs
226 def interleave(cols):
227 """
228 interleave(cols) return a string interleaving the characters
229 of the strings within cols.
230 """
231 m = 0
232 for rows in cols:
233 for cell in rows:
234 try:
235 m = max(m, len(cell))
236 except TypeError:
237 return None
238 s = ""
239 for idx in range(0, m):
240 for rows in cols:
241 for cell in rows:
242 try:
243 s+=cell[idx]
244 except IndexError:
245 continue
246 return s
247 def inBase(base, digits):
248 acc = 0
249 for digit in digits:
250 acc = int(digit) + (base * acc)
251 return acc
252 def randomIntegerOfBits(n, bs):
253 """
254 randomIntegerOfBits(n, bs) retourne le premier entier i formé par les bits bs
255 qui a le potentiel d’atteindre un entier dans [0 .. n-1],
256 ou recommence en ignorant le premier bit si n <= i.
257 """
258 n = int(n)
259 if bs == None:
260 return None
261 #print("randomIntegerOfBits: "+str((n, bs)))
262 enough = bitSize(str(n - 1))
263 #print("randomIntegerOfBits: enough="+str(enough))
264 while True:
265 bits = bs[0:enough]
266 given = len(bits)
267 bs_ = bs[enough:]
268 i = inBase(2, bits)
269 if given < enough:
270 return None
271 if n <= i:
272 bs = bits[1:] + bs_
273 else:
274 return str(i)
275
276 g_exportedScripts = ()