# Caminho aleatório sem repetição

O caminho aleatório sem repetição é um tipo de permutação no campo da análise combinatória. Embora o seu conceito já tenha sido estudado pelo menos desde 1150 por Baskara II, só na década de 1990 começou a ser utilizado recorrentemente no campo da geoestatística com o aumento da capacidade de processamento dos computadores e implementação em métodos de simulação sequencial, como é o caso da simulação sequencial gaussiana. Um caminho aleatório sem repetição é feito a partir de um conjunto de localizações pré-determinadas mas randomizando o caminho feito sobre elas garantindo que nunca voltará ao mesmo local. Isto implica que o único processo aleatório deste procedimento é o do instante em que se irá percorrer uma dada localização e não o da própria localização.

## Definição

Assumindo que temos uma malha com nove localizações possíveis (nós) e tencionamos percorrer todas a cada momento que passa sendo os momentos [1,2,3,4,5,6,7,8,9] então quatro possíveis caminhos aleatórios são:
Malha com 9 locais :
| Malha com 9 locais *** *** *** | $\rightarrow$ | 1º Caminho aleatório 821 965 437 | 2º Caminho aleatório 379 156 824 | 3º Caminho aleatório 597 612 384 | 4º Caminho aleatório 453 927 186 |
Embora seja um método tipicamente utilizado em ciências de modelação o conceito de permutação (de análise combinatória) está na sua génese dado que representa a possibilidade de objectos (neste caso uma lista de localizações) ter vários arranjos diferentes. Importa, no entanto, frisar que se tratam de arranjos em que cada um dos elementos é único e que o processo de arranjo provém de um procedimento baseado em números aleatórios (ou pseudo-aleatórios). Assim, pegando num exemplo semelhante ao anterior, se tivermos uma lista de 9 localizações [1,2,3,4,5,6,7,8,9] cada arranjo dos elementos desta lista seria um caminho aleatório sem repetição num total de:
    $P_{n}=n!\rightarrow P_{9}=9!=362880$

## Algoritmo do caminho aleatório sem repetição (Python)

A implementação bidimensional que se segue é feita na linguagem Python (versão 2.7.2) com recurso à biblioteca NumPy tendo por esse motivo o seguinte cabeçalho de importações:
Em recurso à função shuffle do módulo numpy é possível criar facilmente uma função cujos argumentos são tamanho e semente e resultado um vector com um caminho aleatório:
Dado que o caminho é gerado aleatóriamente é necessário a existência de uma semente que faça com o utilizador possa repetir o mesmo resultado desde que utilizando o mesmo número de semente. Veja-se a experiências seguinte onde foi lançada a função quatro vezes duas das quais (primeira e última) com a mesma semente:
O resultado é este:
De notar que foram gerados quatro vectores nos quais as posições indicam diferentes localizações dadas pelos valores que se encontram em cada vector. As funções utilizadas para conseguir este efeito são:
* np.random.seed - Força a semente dos processos aleatórios que se seguem a serem a de input, implicando um controlo sobre a geração pseudo-aleatório.
* np.arange - Cria um vector crescente de valores igualmente espaçados. Por defeito inteiros com espaçamento de 1 a começar em zero e terminando no argumento inserido.
* np.shuffle - Troca, por meio de processos aleatórios, a posição dos elementos de um vector.

## Discussão

Este tipo de caminho aleatório é muito utilizado em geoestátistica nos algoritmos de simulação sequencial muito embora por vezes haja aplicações no qual ele não é totalmente aleatório dando prioridade a certas localizações.