Obtenir un échantillon aléatoire de la liste tout en maintenant la commande des articles?

Question

J'ai une liste triée, disons: (ce ne sont pas vraiment des nombres, c'est une liste d'objets qui sont triés avec un algorithme compliqué et chronophage)

 mylist = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,9  , 10 ]
 

Y a-t-il une fonction python qui me donnera N des articles, mais gardera l'ordre?

Exemple:

 randomList = getRandom(mylist,4)
# randomList = [ 3 , 6 ,7 , 9 ]
randomList = getRandom(mylist,4)
# randomList = [ 1 , 2 , 4 , 8 ]
 

etc...

Answer 1

Le code suivant générera un échantillon aléatoire de taille 4.

 rand_smpl = [ mylist[i] for i in sorted(random.sample(xrange(len(mylist)), 4)) ]
 

Modifier - Explication:

 random.sample(xrange(len(mylist)), sample_size)
 

génère un échantillon aléatoire des indices de la liste d'origine.

Cet échantillon est ensuite trié pour conserver l'ordre des éléments dans la liste d'origine.

Enfin, la compréhension de la liste extrait les éléments de la liste d'origine, compte tenu des indices échantillonnés, et construit l'échantillon final (des éléments réels).

Answer 2

Simple à code O(N + K*log(K)) de manière à

Prendre un échantillon aléatoire sans remplacement de l'indice, trier les indices, et de les prendre à partir de l'original.

indices = random.sample(range(len(myList)), K)
[myList[i] for i in sorted(indices)]

Ou de façon plus concise:

[x[1] for x in sorted(random.sample(enumerate(myList),K))]

---

Optimisé O(N) en temps O(1)-auxiliaire-de l'espace de façon

Alternativement, vous pouvez utiliser un math astuce et de manière itérative passer par myList de gauche à droite, choisir les numéros avec les dynamiques de probabilité (N-numbersPicked)/(total-numbersVisited). L'avantage de cette approche est qu'il est un O(N) de l'algorithme, car il n'implique pas de du tri!

def orderedSampleWithoutReplacement(seq, k):
    if not 0<=k<=len(seq):
        raise ValueError('Required that 0 <= sample_size <= population_size')

    numbersPicked = 0
    for i,number in enumerate(seq):
        prob = (k-numbersPicked)/(len(seq)-i)
        if random.random() < prob:
            yield number
            numbersPicked += 1

La preuve de concept et de tester que les probabilités sont corrects:

Simulé avec 1 billion de pseudo-aléatoires d'échantillons au cours de 5 heures:

>>> Counter(
        tuple(orderedSampleWithoutReplacement([0,1,2,3], 2))
        for _ in range(10**9)
    )
Counter({
    (0, 3): 166680161, 
    (1, 2): 166672608, 
    (0, 2): 166669915, 
    (2, 3): 166667390, 
    (1, 3): 166660630, 
    (0, 1): 166649296
})

Les probabilités de s'écarter de la vraie probabilités au moins un facteur de 1.0001. L'exécution de ce test de nouveau entraîné dans un ordre différent du sens qu'il n'est pas biaisé en faveur d'une commande. Exécution du test avec moins d'échantillons pour l' [0,1,2,3,4], k=3 et [0,1,2,3,4,5], k=4 avaient des résultats similaires.

edit: je ne sais Pas pourquoi les gens sont à droit de vote jusqu'mauvais commentaires ou peur de upvote... NON, il n'y a rien de mal avec cette méthode. =)

Answer 3

Vous pouvez peut-être simplement générer l'échantillon d'indices, puis collecter les éléments de votre liste.

 randIndex = random.sample(range(len(mylist)), sample_size)
randIndex.sort()
rand = [mylist[i] for i in randIndex]
 

Answer 4

Apparemment, random.sample été introduit dans python 2.3

donc pour la version en dessous, on peut utiliser shuffle (exemple pour 4 items):

 myRange =  range(0,len(mylist)) 
shuffle(myRange)
coupons = [ bestCoupons[i] for i in sorted(myRange[:4]) ]