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 = ()