jeudi 2 juillet 2020

Random combinations without duplicates in Python

Suppose you have an iterable t of size n. You want to draw l random combinations of r elements from t. You require that the l combinations are different. Until now my take is the following (inspired by the iter tools recipes):

def random_combinations(iterable,r,size):
 n=len(tuple(iterable))
 combinations=[None]*size
 
 f=mt.factorial                                            # Factorial function
 nCr=f(n)//(f(r)*f(n-r))                                   # nCr
 iteration_limit=10*nCr                      # Limit of iterations 10 times nCr
 
 repeated_combinations=0                     # Counter of repeated combinations
 i=0                                         # Storage index
 
 combinations[i]=tuple(sorted(rn.sample(xrange(n),r)))      # First combination
 i+=1                                                    # Advance the counting
 
 while i < size:                                  # Loop for subsequent samples
  indices=tuple(sorted(rn.sample(xrange(n),r)))
  test=[ combinations[j] for j in range(i) ]
  test.append(indices)
  test=len(list(set(test)))
  if test == i+1:                                           # Test of duplicity
   repeated_combinations=0
   combinations[i]=indices
   i+=1
  else:
   repeated_combinations+=1
  if repeated_combinations == iteration_limit:       # Test for iteration limit
   break
 return combinations

Is there another way more efficient to do this? I ask this because I will be drawing several combinations from iterables that are huge (over 100 elements).




Aucun commentaire:

Enregistrer un commentaire