BogoSort

Descrição

Esconder código-fonte

#!/usr/bin/python2.7
# -*- coding: utf-8 -*-

# (cc) Copyleft 2011 Renan Birck
# renan.ee.ufsm @ (serviço de e-mail do google)

from random import shuffle, sample
from sys import argv, exit
from matplotlib import pyplot as plt
from matplotlib import rc
from scipy import mean, std 
from operator import mul

qualities = []
i = 0;

def measureSolutionQuality(seq):
    """ Mede a qualidade da solução se comparada com o vetor original. """
    score = 0
    for z in enumerate(seq):
   score += reduce(mul,z)
    return score

def bogosort(seq):
    """ BogoSort em si """
    global i
    while not all(x <= y for x, y in zip(seq, seq[1:])):
        shuffle(seq)
   #print "Iteration %d, quality is %d. " % (i,measureSolutionQuality(seq)), seq
   qualities.append(measureSolutionQuality(seq))
   i += 1
    return seq

if len(argv) == 1:
    n = 10
else:
    n = int(argv[1]) 

if n>1000:
    exit("Tu tá tirando uma com a minha cara, né?")

data = sample(range(1000),n)


goodSol = measureSolutionQuality(sorted(data))
print "A qualidade da melhor solução é %d." % goodSol
sorted = bogosort(data)

print "Precisei de %d iterações para fazer o BogoSort dela." % i
print "Qualidade min/max/média/desvpad: %f, %f, %f, %f" % (min(qualities),max(qualities),mean(qualities),std(qualities)) 

# Plotar o diagrama
plt.plot(range(len(qualities)),qualities,'ro')
rc('text', usetex=True) # Para usar acentos com a matplotlib
plt.xlabel('Itera\c c\~ao')
plt.ylabel('Qualidade')
plt.title("BogoSort: itera\c c\~ao x qualidade")
plt.show()