Файл:Probabilities7.svg
Материал из Википедии — свободной энциклопедии
Перейти к навигации
Перейти к поиску
Размер этого PNG-превью для исходного SVG-файла: 360 × 270 пкс. Другие разрешения: 320 × 240 пкс | 640 × 480 пкс | 1024 × 768 пкс | 1280 × 960 пкс | 2560 × 1920 пкс.
Исходный файл (SVG-файл, номинально 360 × 270 пкс, размер файла: 215 Кб)
Этот файл находится на Викискладе. Сведения о нём показаны ниже.
Викисклад — централизованное хранилище для свободных файлов, используемых в проектах Викимедиа.
Сообщить об ошибке с файлом |
Краткое описание
ОписаниеProbabilities7.svg |
English: A probability matrix representing the bias in positions for the "Permute-With-All" algorithm from Introduction to Algorithms (Cormen et al.), also described as an implementation error in the Fisher-Yates shuffle |
Дата | |
Источник | Собственная работа |
Автор | Kostmo |
SVG‑разработка InfoField | Это plot было создано с помощью Matplotlib |
Исходный код InfoField | Python code#!/usr/bin/env python
def swap(a, src, dst):
a[src], a[dst] = a[dst], a[src]
# =============================================================================
def PermuteWithAll(array, randoms_sequence=None):
# take swap target index with equal probability in the range 0..N
a = array[:]
for i in range(len(a)):
dest = randoms_sequence[i] if randoms_sequence else randrange(len(a))
swap(a, i, dest)
return a
# =============================================================================
def flatten(nested):
flat = []
for el in nested:
if type(el) is list:
flat.extend( flatten(el) )
else:
flat.append( el )
return flat
# =============================================================================
# Plots a two-dimensional matrix
def plot_nice_matrix(xy, a, denominator=1):
from matplotlib.backends.backend_gtkcairo import FigureCanvasGTKCairo as FigureCanvas
from matplotlib import mpl
from matplotlib.figure import Figure, SubplotParams
from matplotlib.ticker import FormatStrFormatter, FixedLocator
normalized = [[x/float(denominator) for x in row] for row in a]
z = flatten(normalized)
x = xy*len(xy)
y = flatten([[i]*len(xy) for i in xy])
sizes = [400*q for q in z] # The matplotlib documentation says that the "size" values are in units of points^2
f = Figure(figsize=(4, 3), dpi=100, subplotpars=SubplotParams(bottom=0.2, left=0.15, top=0.85, right=0.8))
main_axis = f.add_subplot(111)
scatter2 = main_axis.scatter(x, y, s=sizes, c=z, cmap=mpl.cm.RdBu)
main_axis.set_xlim(-1, len(xy))
main_axis.set_ylim(-1, len(xy))
main_axis.invert_yaxis()
for i, row in enumerate(a):
for j, col in enumerate(row):
main_axis.text(j, i + 0.5,
"%.1f%%" % (100*row[j]/float(denominator)),
verticalalignment='center',
horizontalalignment='center',
fontsize=4.5)
cb = f.colorbar(scatter2, orientation="vertical")
cb.set_label("Probability")
main_axis.set_xlabel("Randomized Position")
main_axis.set_ylabel("Original Position")
main_axis.grid(True, color='#AAAAAA')
main_axis.xaxis.set_major_formatter( FormatStrFormatter("%d") )
main_axis.xaxis.set_major_locator( FixedLocator(xy) )
main_axis.yaxis.set_major_formatter( FormatStrFormatter("%d") )
main_axis.yaxis.set_major_locator( FixedLocator(xy) )
f.suptitle( '"Permute-With-All" Order Bias' )
chart_title = "probabilities" + str( len(xy) )
FigureCanvas( f ).print_figure(chart_title + ".svg", format="svg", transparent=True)
# =============================================================================
def position_frequency_matrix(a, permutation_bins):
# Initialize a zeroed 2D array
probabilities = [[0 for i in range(len(a))] for j in range(len(a))]
for sequence, count in permutation_bins.items():
for new_position, original_position in enumerate(sequence):
probabilities[original_position][new_position] += count
return probabilities
# =============================================================================
if __name__ == "__main__":
from collections import defaultdict
import itertools
for length in range(2, 8):
A = range(length)
print A
permutation_bins = defaultdict(int)
for random_number_sequence in itertools.product(A, repeat=len(A)):
permutation_bins[tuple(PermuteWithAll(A, random_number_sequence))] += 1
probabilities = position_frequency_matrix(A, permutation_bins)
denominator = len(A)**len(A)
plot_nice_matrix(A, probabilities, denominator)
|
Лицензирование
Я, владелец авторских прав на это произведение, добровольно публикую его на условиях следующих лицензий:
Этот файл доступен по лицензии Creative Commons Attribution-Share Alike 3.0 Unported.
- Вы можете свободно:
- делиться произведением – копировать, распространять и передавать данное произведение
- создавать производные – переделывать данное произведение
- При соблюдении следующих условий:
- атрибуция – Вы должны указать авторство, предоставить ссылку на лицензию и указать, внёс ли автор какие-либо изменения. Это можно сделать любым разумным способом, но не создавая впечатление, что лицензиат поддерживает вас или использование вами данного произведения.
- распространение на тех же условиях – Если вы изменяете, преобразуете или создаёте иное произведение на основе данного, то обязаны использовать лицензию исходного произведения или лицензию, совместимую с исходной.
Разрешается копировать, распространять и/или изменять этот документ в соответствии с условиями GNU Free Documentation License версии 1.2 или более поздней, опубликованной Фондом свободного программного обеспечения, без неизменяемых разделов, без текстов, помещаемых на первой и последней обложке. Копия лицензии включена в раздел, озаглавленный GNU Free Documentation License.http://www.gnu.org/copyleft/fdl.htmlGFDLGNU Free Documentation Licensetruetrue |
Вы можете выбрать любую из этих лицензий.
Элементы, изображённые на этом файле
изображённый объект
У этого свойства есть некоторое значение без элемента в
15 июня 2010
История файла
Нажмите на дату/время, чтобы посмотреть файл, который был загружен в тот момент.
Дата/время | Миниатюра | Размеры | Участник | Примечание | |
---|---|---|---|---|---|
текущий | 15:18, 15 июня 2010 | 360 × 270 (215 Кб) | Kostmo | {{Information |Description={{en|1=A probability matrix representing the bias in positions for the Permute-With-All algorithm from w:Introduction to Algorithms, also described as an implementation error in the [[w:Fisher-Yates s |
Использование файла
Следующая страница использует этот файл:
Глобальное использование файла
Данный файл используется в следующих вики:
- Использование в en.wikipedia.org
- Использование в ja.wikipedia.org