Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como embaralhar aleatoriamente as palavras de um arquivo grande com N palavras?

0 votos
3 visitas
perguntada Set 14 em Ciência da Computação por Fabio Fujita (36 pontos)  
editado Set 14 por Fabio Fujita

Sugira uma "boa" forma de resolver o problema, assumindo ter apenas alguns milhares de palavras de memória interna disponível, com algumas dezenas de tape units (memória suficiente para o problema de sorting).

Exercício 13 do Capítulo 5 do livro "The art of computer programming - Volume 3" de Donald E. Knuth, na página 7 da segunda edição.

Compartilhe

1 Resposta

0 votos
respondida Set 15 por Fabio Fujita (36 pontos)  
editado 4 dias atrás por Fabio Fujita

Primeiramente, note que apesar do exercício fazer referência a um arquivo grande, o complemento do enunciado define que a memória disponível é suficiente para resolver o problema de sorting. Dessa forma, precisamos levar em consideração a memória utilizada na solução, mas caso o algoritmo seja adequado, o problema ainda pode ser classificado como um problema de internal sorting (em que os registros podem ser mantidos integralmente na RAM do computador). Caso o arquivo a ser embaralhado fosse grande a ponto da memória disponível não ser suficiente, seria necessário quebrar o problema original em problemas menores.

Há funções e bibliotecas que realizam o processo de shuffle automaticamente em Python, mas para fins de aprendizado dos algoritmos, consideraremos que temos disponível apenas uma função que gere números inteiros aleatórios em determinado intervalo (foi utilizada a função randint, da biblioteca random). Destaca-se que, caso não esteja satisfeito com o algoritmo de geração aleatória de números utilizado, seria possível implementar outro método.

Uma das formas de resolver o problema é atribuir um número aleatório entre 1 e N a cada palavra e posteriormente realizar a ordenação dessas chaves. Outra forma eficiente, que escolhi para implementar em Python, é utilizar o algoritmo de Fischer-Yates.

Pelo algoritmo:

  1. Inserimos as palavras que devem ser embaralhadas em uma lista (o que
    é possível, pois temos memória suficiente para resolver um problema
    de sorting).
  2. Começamos pelo último elemento da lista e o substituímos por um elemento aleatório, que pode ser o próprio elemento.
  3. Reduzimos o tamanho da lista em uma unidade e repetimos o procedimento até chegarmos ao primeiro elemento.

O enunciado não especifica o formato do arquivo de entrada. Para um teste, foi considerado o "arquivo_original.txt", com registros separados por espaços. De forma análoga, a saída dos registros embaralhados é gravada no "arquivo_saida.txt", após convertermos novamente a lista em uma string.

A seguir, apresenta-se a implementação em Python.

import random

if __name__ == '__main__':

    # Leitura do arquivo_original.txt e conversão para uma lista de palavras
    file1 = open("arquivo_original.txt","r")
    string_registros=file1.read()
    file1.close()
    list_registros=list(string_registros.split(" "))
    print("A ordem original das palavras eh: "+str(list_registros))

    # Algoritmo de Fischer-Yates
    for i in range(len(list_registros)-1, 0, -1):

        # Sorteio de um número aleatório entre 0 e i
        j = random.randint(0, i)
           # troca o elemento i pelo elemento aleatório
        list_registros[i], list_registros[j] = list_registros[j], list_registros[i]

    print("A ordem das palavras embaralhadas aleatoriamente eh: "+str(list_registros)  )

    # Gravação da saída no arquivo_saida.txt em formato de string
    file2 = open("arquivo_saida.txt","w+")
    file2.write(" ".join(list_registros))
    file2.close()

As listas são exibidas no console para verificação (os arquivos de entrada e saída estão em formato de string). Um exemplo do resultado é apresentado a seguir:

A ordem original das palavras eh: ['registro1', 'registro2', 
'registro3', 'registro4', 'registro5', 'registro6', 'registro7', 
'registro8', 'registro9']

A ordem das palavras embaralhadas aleatoriamente eh: 
['registro2', 'registro9', 'registro6', 'registro4', 'registro8', 
'registro1', 'registro7', 'registro3', 'registro5']
...