Em R, se eu definir.seed () e usar a função de amostra para randomizar uma lista, posso garantir que não gerarei a mesma permutação?
ie ...
set.seed(25)
limit <- 3
myindex <- seq(0,limit)
for (x in seq(1,factorial(limit))) {
permutations <- sample(myindex)
print(permutations)
}
Isso produz
[1] 1 2 0 3
[1] 0 2 1 3
[1] 0 3 2 1
[1] 3 1 2 0
[1] 2 3 0 1
[1] 0 1 3 2
todas as permutações impressas serão permutações únicas? Ou existe alguma chance, com base na maneira como isso é implementado, de obter algumas repetições?
Quero poder fazer isso sem repetições, garantido. Como eu faria isso?
(Também quero evitar ter que usar uma função como permn (), que tem um método muito mecanicista para gerar todas as permutações - não parece aleatório.)
Além disso, nota de rodapé --- parece que esse problema é O ((n!)!), Se não me engano.
r
sampling
combinatorics
resampling
Mittenchops
fonte
fonte
limit
exceder 12, você provavelmente ficará sem memória RAM quando R tentar alocar espaço paraseq(1,factorial(limit))
. (! 12 requer cerca de 2 GB, de modo 13 terá cerca de 25 GB, 14 cerca de 350 GB, etc.!)Respostas:
A questão tem muitas interpretações válidas. Os comentários - especialmente aquele que indica permutações de 15 ou mais elementos são necessários (15! = 1307674368000 está ficando grande) - sugerem que o que se quer é uma amostra aleatória relativamente pequena , sem substituição, de todos os n! = n * (n-1) (n-2) ... * 2 * 1 permutações de 1: n. Se isso for verdade, existem soluções (um tanto) eficientes.
A função a seguir
rperm
, aceita dois argumentosn
(o tamanho das permutações para amostrar) em
(o número de permutações de tamanho n para desenhar). Se m se aproximar ou exceder n !, a função levará muito tempo e retornará muitos valores de NA: ela deve ser usada quando n for relativamente grande (digamos, 8 ou mais) e m for muito menor que n !. Ele funciona armazenando em cache uma representação em cadeia das permutações encontradas até o momento e gerando novas permutações (aleatoriamente) até que uma nova seja encontrada. Ele explora a capacidade de indexação de lista associativa de R para pesquisar rapidamente a lista de permutações encontradas anteriormente.A natureza de
replicate
é retornar as permutações como vetores de coluna ; por exemplo , o seguinte reproduz um exemplo na pergunta original, transposta :Os tempos são excelentes para valores pequenos a moderados de m, até cerca de 10.000, mas degradam-se para problemas maiores. Por exemplo, uma amostra de m = 10.000 permutações de n = 1000 elementos (uma matriz de 10 milhões de valores) foi obtida em 10 segundos; uma amostra de m = 20.000 permutações de n = 20 elementos exigiu 11 segundos, mesmo que a saída (uma matriz de 400.000 entradas) fosse muito menor; e a amostra de computação de m = 100.000 permutações de n = 20 elementos foi abortada após 260 segundos (não tive paciência para aguardar a conclusão). Esse problema de escala parece estar relacionado a ineficiências de escala no endereçamento associativo de R. Pode-se contornar isso gerando amostras em grupos de, digamos, mais ou menos 1000, combinando essas amostras em uma amostra grande e removendo duplicatas.
Editar
Podemos obter um desempenho assintótico quase linear dividindo o cache em uma hierarquia de dois caches, para que R nunca precise pesquisar em uma lista grande. Conceitualmente (embora não seja implementado), crie uma matriz indexada pelos primeiros elementos de uma permutação. As entradas nessa matriz são listas de todas as permutações que compartilham esses primeiros elementos. Para verificar se uma permutação foi vista, use seus primeiros elementos para encontrar sua entrada no cache e, em seguida, procure essa permutação nessa entrada. Podemos escolher para equilibrar os tamanhos esperados de todas as listas. A implementação real não usa umk k k kk k k k k array -fold, que seria difícil de programar em generalidade suficiente, mas usa outra lista.
Aqui estão alguns tempos decorridos em segundos para uma variedade de tamanhos de permutação e número de permutações distintas solicitadas:
(A aceleração aparentemente anômala de size = 10 para size = 15 é porque o primeiro nível do cache é maior para size = 15, reduzindo o número médio de entradas nas listas de segundo nível, acelerando a pesquisa associativa de R. custo em RAM, a execução pode ser feita mais rapidamente aumentando o tamanho do cache de nível superior, aumentando apenas
k.head
1 (o que multiplica o tamanho de nível superior por 10) acelerandorperm(100000, size=10)
de 11,77 segundos para 8,72 segundos, por exemplo. cache 10 vezes maior, mas não obteve ganho apreciável, com clock de 8,51 segundos.)Exceto no caso de 1.000.000 de permutações únicas de 10 elementos (uma parcela substancial de todos os 10! = Cerca de 3,63 milhões de permutações), praticamente nenhuma colisão foi detectada. Nesse caso excepcional, houve 169.301 colisões, mas nenhuma falha completa (um milhão de permutações únicas foram de fato obtidas).
Observe que, com tamanhos de permutação grandes (maiores que 20 ou mais), a chance de obter duas permutações idênticas, mesmo em uma amostra de até 1.000.000.000, é muito pequena. Assim, esta solução é aplicável principalmente em situações em que (a) um grande número de permutações únicas de (b) entre e ou então elementos estão a ser gerada, mas mesmo assim, (c), substancialmente menos do que todos ospermutações são necessárias.n = 15 n !n=5 n=15 n!
Código de trabalho a seguir.
fonte
> rperm(6,3) $failures [1] 9 $sample [,1] [,2] [,3] [1,] 3 1 3 [2,] 2 2 1 [3,] 1 3 2 [4,] 1 2 2 [5,] 3 3 1 [6,] 2 1 3
Usar
unique
da maneira correta deve fazer o truque:fonte
Vou desviar um pouco a sua primeira pergunta e sugerir que, se você está lidando com vetores relativamente curtos, você pode simplesmente gerar todas as permutações usando
permn
e ordená-las aleatoriamente as que usamsample
:fonte
permn(10)
ou o que quer que seja apenas uma vez.set.seed
: descreve como salvar o estado do RNG e restaurá-lo mais tarde.