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