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         for i in range(0,k):
 174                 nsi = ns[i]
 175                 #print("ns = "+str(ns))
 176                 #print("rank += %i * nAk(%i,%i)" % (nsi - 1, n - (i+1), k - (i+1)))
 177                 rank += (nsi - 1) * nAk(n - (i+1), k - (i+1))
 178                 for j in range(i+1,k):
 179                         if nsi < ns[j]:
 180                                 ns[j] -= 1
 181         return str(rank)
 182 def bitSize(n):
 183         """
 184         bitSize(n) retourne le nombre de bits servant à encoder n.
 185         """
 186         try:
 187                 n = int(n)
 188         except ValueError:
 189                 return None
 190         if n<0:
 191                 return None
 192         r = 0
 193         while n > 0:
 194                 r += 1
 195                 n //= 2
 196         return r
 197 def equiprobableBits(n):
 198         """
 199         equiprobableBits(n) retourne le nombre maximal de bits de i
 200         équiprobables quand i parcourt [0 .. n-1].
 201
 202         Ce nombre est le plus grand 'b' dans [0 .. ] tel que 2**b-1 <= n.
 203
 204         map(equiprobableBits, range(0, 17+1)) == [0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4]
 205         """
 206         b = bitSize(n)
 207         return (b if n == 2**b-1 else b-1)
 208 def bitsOfInteger(m, n):
 209         """
 210         bitsOfInteger(m, n) retourne les m premiers bits de poids faible
 211         encodant le nombre n.
 212         """
 213         m = int(m)
 214         n = int(n)
 215         if not(0<=m and 0<=n):
 216                 return None
 217         bs = ""
 218         while m > 0:
 219                 (q,r) = (n//2, n%2)
 220                 bs = ("1" if r else "0") + bs
 221                 m -= 1
 222                 n = q
 223         return bs
 224 def interleave(cols):
 225         """
 226         interleave(cols) return a string interleaving the characters
 227         of the strings within cols.
 228         """
 229         m = 0
 230         for rows in cols:
 231                 for cell in rows:
 232                         try:
 233                                 m = max(m, len(cell))
 234                         except TypeError:
 235                                 return None
 236         s = ""
 237         for idx in range(0, m):
 238                 for rows in cols:
 239                         for cell in rows:
 240                                 try:
 241                                         s+=cell[idx]
 242                                 except IndexError:
 243                                         continue
 244         return s
 245 def inBase(base, digits):
 246         acc = 0
 247         for digit in digits:
 248                 acc = int(digit) + (base * acc)
 249         return acc
 250 def randomIntegerOfBits(n, bs):
 251         """
 252         randomIntegerOfBits(n, bs) retourne le premier entier i formé par les bits bs
 253         qui a le potentiel d’atteindre un entier dans [0 .. n-1],
 254         ou recommence en ignorant le premier bit si n <= i.
 255         """
 256         n = int(n)
 257         if bs == None:
 258                 return None
 259         #print("randomIntegerOfBits: "+str((n, bs)))
 260         enough = bitSize(str(n - 1))
 261         #print("randomIntegerOfBits: enough="+str(enough))
 262         while True:
 263                 bits  = bs[0:enough]
 264                 given = len(bits)
 265                 bs_   = bs[enough:]
 266                 i     = inBase(2, bits)
 267                 if given < enough:
 268                         return None
 269                 if n <= i:
 270                         bs = bits[1:] + bs_
 271                 else:
 272                         return str(i)
 273
 274 g_exportedScripts = ()