]> Git — Sourcephile - reloto-libreoffice.git/blob - tirages.py
Polissage documents Jugement Majoritaire.
[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 j in range(1, k+1):
42 r = r * (n-j+1) // j
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 Improved to work on k-sequence of permutations instead of only full permutations.
97 """
98 try:
99 rank = int(rank)
100 except ValueError:
101 return None
102 p = []
103 a = nAk(n,k)
104 for i in range(1,k+1):
105 a //= n-(i-1) # optimized a = nAk(n-i, k-i)
106 d = rank // a # greatest multiple of a, lower or equal to r
107 rank = rank % a
108 p.append(d+1)
109 for i in range(k-1,-1,-1): # important: from right to left
110 for j in range(i+1,k):
111 if p[j] >= p[i]:
112 p[j] += 1 # promote the positions in the good interval
113 return p
114 def checkSequence(n,ns):
115 """
116 checkSequence(n,ns) returns the range ns flattened
117 if each element is with 1 and n, without repetition.
118 """
119 p = []
120 for row in ns: # flatten range given by LO
121 for col in row:
122 i = int(col)
123 if not(1<=i and i<=n):
124 return None
125 if i in p: # duplicate
126 return None
127 p.append(i)
128 return p
129
130 def rankOfCombin(n,ns):
131 """
132 rankOfCombin(n, ns) retourne le rang lexicographique dans [0 .. nCk(n, length ns)-1]
133 de la combinaison ns d’entiers parmi [1..n].
134
135 WARNING: ns doit être triée de manière ascendante.
136
137 Compte le nombre de combinaisons précédant celle de rang r.
138
139 DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, pp.24-25
140
141 rankOfCombin(n, combinOfRank(n, k, r)) == r
142 combinOfRank(n, len(ns), rankOfCombin(n, ns)) == ns
143 """
144 ns = checkSequence(n, ns)
145 if ns == None:
146 return None
147 ns.sort()
148 k = len(ns)
149 i = 1
150 rank = 0
151 x1 = 0
152 for x in ns:
153 for j in range(x1+1,x-1 +1):
154 rank += nCk(n-j, k-i)
155 i += 1
156 x1 = x
157 return str(rank)
158 def rankOfSequence(n, ns):
159 """
160 rankOfSequence(n, ns) retourne le rang lexicographique dans [0 .. nAk(n, len(ns))-1]
161 de la combinaison ns d’entiers parmi [1..n].
162
163 Compte le nombre d’arrangements précédant celui de rang r.
164
165 DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, pp.74
166 """
167 rank = 0
168 ns = checkSequence(n, ns)
169 if ns == None:
170 return None
171 k = len(ns)
172 for i in range(0,k):
173 nsi = ns[i]
174 #print("ns = "+str(ns))
175 #print("rank += %i * nAk(%i,%i)" % (nsi - 1, n - (i+1), k - (i+1)))
176 rank += (nsi - 1) * nAk(n - (i+1), k - (i+1))
177 for j in range(i+1,k):
178 if nsi < ns[j]:
179 ns[j] -= 1
180 return str(rank)
181 def bitSize(n):
182 """
183 bitSize(n) retourne le nombre de bits servant à encoder n.
184 """
185 try:
186 n = int(n)
187 except ValueError:
188 return None
189 if n<0:
190 return None
191 r = 0
192 while n > 0:
193 r += 1
194 n //= 2
195 return r
196 def equiprobableBits(n):
197 """
198 equiprobableBits(n) retourne le nombre maximal de bits de i
199 équiprobables quand i parcourt [0 .. n-1].
200
201 Ce nombre est le plus grand 'b' dans [0 .. ] tel que 2**b-1 <= n.
202
203 map(equiprobableBits, range(0, 17+1)) == [0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4]
204 """
205 b = bitSize(n)
206 return (b if n == 2**b-1 else b-1)
207 def bitsOfInteger(m, n):
208 """
209 bitsOfInteger(m, n) retourne les m premiers bits de poids faible
210 encodant le nombre n.
211 """
212 m = int(m)
213 n = int(n)
214 if not(0<=m and 0<=n):
215 return None
216 bs = ""
217 while m > 0:
218 (q,r) = (n//2, n%2)
219 bs = ("1" if r else "0") + bs
220 m -= 1
221 n = q
222 return bs
223 def interleave(cols):
224 """
225 interleave(cols) return a string interleaving the characters
226 of the strings within cols.
227 """
228 m = 0
229 for rows in cols:
230 for cell in rows:
231 try:
232 m = max(m, len(cell))
233 except TypeError:
234 return None
235 s = ""
236 for idx in range(0, m):
237 for rows in cols:
238 for cell in rows:
239 try:
240 s+=cell[idx]
241 except IndexError:
242 continue
243 return s
244 def inBase(base, digits):
245 acc = 0
246 for digit in digits:
247 acc = int(digit) + (base * acc)
248 return acc
249 def randomIntegerOfBits(n, bs):
250 """
251 randomIntegerOfBits(n, bs) retourne le premier entier i formé par les bits bs
252 qui a le potentiel d’atteindre un entier dans [0 .. n-1],
253 ou recommence en ignorant le premier bit si n <= i.
254 """
255 n = int(n)
256 if bs == None:
257 return None
258 #print("randomIntegerOfBits: "+str((n, bs)))
259 enough = bitSize(str(n - 1))
260 #print("randomIntegerOfBits: enough="+str(enough))
261 while True:
262 bits = bs[0:enough]
263 given = len(bits)
264 bs_ = bs[enough:]
265 i = inBase(2, bits)
266 if given < enough:
267 return None
268 if n <= i:
269 bs = bits[1:] + bs_
270 else:
271 return str(i)
272
273 g_exportedScripts = ()