Перемешивание части списка на месте - PullRequest
1 голос
/ 26 апреля 2020

У меня есть list, и я хочу перетасовать его часть на месте .

Мне известно о random.shuffle() и что он работает на месте, но если я нарежу список, он перемешивает нарезанную копию исходного ввода, оставляя оригинал list нетронутым:

import random

l = list(range(20))
print(l)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

random.shuffle(l[:10])  # I wish it was shuffling the first half
print(l)  # but does nothing to `l`
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Какие варианты у меня есть?


РЕДАКТИРОВАТЬ : Это не является действительно дубликатом этого вопроса , поскольку не требовалось, чтобы он был на месте . В конце концов, кажется, что можно было бы перетасовать на месте часть списка только вручную (это именно то, чего я пытался избежать), как предлагает один из опубликованных ответов есть .

Ответы [ 3 ]

3 голосов
/ 26 апреля 2020

Не совсем на месте, но с желаемым результатом:

import random

l = list(range(20))

lpart = l[:10]
random.shuffle(lpart)

l[:10] = lpart

print(l)
2 голосов
/ 26 апреля 2020

Изменение списка n-place не будет работать только с частью списка. Вместо этого вы могли бы использовать random.sample, чтобы брать случайные выборки без замены, и назначать срез обратно:

k = 10
l[:k] = random.sample(l[:k], k=k)

print(l)
# [1, 7, 6, 0, 2, 3, 4, 9, 8, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
0 голосов
/ 28 апреля 2020

Можно использовать Фишера-Йейтса shuffle , чтобы существенно перестроить random.shuffle(), чтобы принять индексы first и last в качестве аргументов, например:

import random


def valid_index(i, n):
    assert(-n <= i < n)
    return i % n


def shuffle(seq, first=0, last=-1, rand_int_gen=None):
    n = len(seq)
    first = valid_index(first, n)
    last = valid_index(last, n)
    # use Fisher-Yates shuffle (Durstenfeld method)
    if callable(rand_int_gen):
        for i in range(first, last):
            j = rand_int_gen(i, last)
            seq[i], seq[j] = seq[j], seq[i]
    else:
        getrandbits = random.getrandbits
        for i in range(first, last + 1):
            size = last - i + 1
            j = getrandbits(size.bit_length()) % size + i
            seq[i], seq[j] = seq[j], seq[i]
    return seq

, который будет использоваться как:

l = list(range(20))
print(l)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

random.seed(0)  # just to show reproducible results
shuffle(l, 0, 9)
print(l)
# [6, 7, 2, 5, 8, 4, 9, 3, 0, 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

С течением времени это даже на несколько процентов быстрее, чем random.shuffle() для перемешивания всей последовательности.

По существу, это быстрее потому что он получает случайные значения непосредственно из random.getrandbits(), который является ближайшим методом, предоставляемым random для генерации случайных целых чисел, остальные, например, randint() и randrange(), в конечном итоге сводятся к этому. Эти последние два в конечном итоге используют внутренне _getrandbelow(), который может вызывать getrandbits() чаще всего необходимое.

for k in range(1, 7): 
    n = 10 ** k 
    print(n) 
    %timeit l = list(range(n)); random.shuffle(l) 
    %timeit l = list(range(n)); shuffle(l) 
    print() 
10
100000 loops, best of 3: 6.16 µs per loop
100000 loops, best of 3: 3.85 µs per loop

100
10000 loops, best of 3: 54.3 µs per loop
10000 loops, best of 3: 28 µs per loop

1000
1000 loops, best of 3: 585 µs per loop
1000 loops, best of 3: 341 µs per loop

10000
100 loops, best of 3: 6.01 ms per loop
100 loops, best of 3: 3.56 ms per loop

100000
10 loops, best of 3: 71.7 ms per loop
10 loops, best of 3: 44.1 ms per loop

1000000
1 loop, best of 3: 815 ms per loop
1 loop, best of 3: 582 ms per loop

Этот подход также был предложен здесь , как указано @ usr2564301. К сожалению, я думаю, что нет лучшего подхода для выполнения этой операции на месте.

...