Ctrl →

The gray Cardinal · Дек. 31, 2008 14:36:17

Я использую для перемешивания списка такой метод:

random.shuffle(myList)

Если список содержит не более 48 элементов, получу ли я теоретически все возможные комбинации следования элементов, если число вызовов метода теоретически бесконечно? Иначе говоря, не будет ли здесь некоторых комбинаций следования элементов, которые не могут выпасть никогда в принципе?

ice · Дек. 31, 2008 14:40:57

Иначе говоря, не будет ли здесь некоторых комбинаций следования элементов, которые не могут выпасть никогда в принципе?

нет не будут. Каждая комбинация имеет вероятность быть. (поправьте, если ошибаюсь, но вероятность любой комбинации 48! при 48 элементах)

The gray Cardinal · Дек. 31, 2008 14:46:42

А сказано где-то прямо в доке, что random.shuffle до конца пережёвывает факториал 48? Ведь у этого метода должен быть какой-то теоретический предел, за которым уже не все комбинации будут выпадать?

ice · Дек. 31, 2008 14:54:23

The gray Cardinal
А сказано где-то прямо в доке, что random.shuffle до конца пережёвывает факториал 48? Ведь у этого метода должен быть какой-то теоретический предел, за которым уже не все комбинации будут выпадать?

Вообще шафл устроен примерно так (где-то читал):
Выбирается случайный индекс из листа, и этот элемент удаляется из исходного листа, так строится новый лист. Поэтому как бы без разницы сколько там элементов.
тут тему рядом заводил про случайные числа. там пример есть с choice. Если я “бесконечное” число чойсов сделаю, то все элементы придут примерно одинаковое количество раз. Поэтому любая комбинация шаффла имеет шанс, так сказать.

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

Отредактировано (Дек. 31, 2008 14:56:25)

The gray Cardinal · Дек. 31, 2008 14:58:05

ice
поэтому будь у тебя хоть гугол элементов в листе, любой варинат возможен…

А так ли это? В доке от Active State читаю:

Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.

Отметьте, что даже для довольно маленького len(x), общее количество перестановок x больше, чем период большинства генераторов случайных чисел; это подразумевает, что большинство перестановок длинной последовательности никогда не сможет сгенерироваться.

ice · Дек. 31, 2008 16:28:14

The gray Cardinal
это подразумевает, что большинство перестановок длинной последовательности никогда не сможет сгенерироваться.

По мойму это говорит о том, что если генератор не сможет сгенерить достаточно большое число len(x) > maxrand то какие-то числа из исходной последовательности могут не перемешаться.

вот пример

import random

def shuffle(a):
    out = []
    while len(a) > 0:
        i = random.choice(a)
        a.remove(i)
        out.append(i)
    return out
    
print shuffle([x for x in xrange(100)])

какие ограничения у choice?

The gray Cardinal · Дек. 31, 2008 16:40:40

ice
какие ограничения у choice?

В доке от Active State про ограничения для choice ничего не сказано, вроде.

ZZZ · Дек. 31, 2008 17:01:40

Вот вариант…

# -*- coding: utf-8 -*-

import random

def shuffle(l):
    for i in xrange(len(l)):
        l.insert(random.randint(0, len(l)), l.pop(i))

l = range(100)
shuffle(l)
print l

The gray Cardinal · Янв. 1, 2009 22:18:51

ZZZ
Вот вариант…

Спасибо, понятно. Так ты не рекомендуешь использовать random.shuffle(), считаешь, не надёжно?

Андрей Светлов · Янв. 2, 2009 01:21:05

Надежно. Так же надежно, как и randint. С теми же ограничениями.
Для темы топика - более чем подойдет.

P.S. Опять непонимание матчасти в разделе комбинаторика-теории вероятностей-мат статистика

Python-сообщество

Уведомления

#1 Дек. 31, 2008 14:36:17

Использование метода random.shuffle()

#2 Дек. 31, 2008 14:40:57

Использование метода random.shuffle()

#3 Дек. 31, 2008 14:46:42

Использование метода random.shuffle()

#4 Дек. 31, 2008 14:54:23

Использование метода random.shuffle()

#5 Дек. 31, 2008 14:58:05

Использование метода random.shuffle()

#6 Дек. 31, 2008 16:28:14

Использование метода random.shuffle()

#7 Дек. 31, 2008 16:40:40

Использование метода random.shuffle()

#8 Дек. 31, 2008 17:01:40

Использование метода random.shuffle()

#9 Янв. 1, 2009 22:18:51

Использование метода random.shuffle()

#10 Янв. 2, 2009 01:21:05

Использование метода random.shuffle()

Board footer