Czy w R, jeśli ustawię set.seed (), a następnie użyję przykładowej funkcji do losowej listy, czy mogę zagwarantować, że nie wygeneruję tej samej permutacji?
to znaczy...
set.seed(25)
limit <- 3
myindex <- seq(0,limit)
for (x in seq(1,factorial(limit))) {
permutations <- sample(myindex)
print(permutations)
}
To produkuje
[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
czy wszystkie wydrukowane permutacje będą unikatowymi permutacjami? Czy może jest jakaś szansa, w oparciu o sposób, w jaki jest to realizowane, że mogę dostać kilka powtórzeń?
Gwarantuję, że mogę to zrobić bez powtórzeń. Jak mam to zrobić?
(Chcę również uniknąć konieczności używania funkcji takiej jak permn (), która ma bardzo mechanistyczną metodę generowania wszystkich permutacji --- nie wygląda losowo.)
Ponadto, sidenote --- wygląda na to, że ten problem to O ((n!)!), Jeśli się nie mylę.
r
sampling
combinatorics
resampling
Mittenchops
źródło
źródło
limit
przekroczy 12, prawdopodobnie zabraknie pamięci RAM, gdy R spróbuje przydzielić miejsceseq(1,factorial(limit))
. (12! Wymaga około 2 GB, więc 13! Potrzebuje około 25 GB, 14! Około 350 GB itp.)Odpowiedzi:
Pytanie ma wiele ważnych interpretacji. Komentarze - szczególnie te wskazujące na konieczność permutacji 15 lub więcej elementów (15! = 1307674368000 stają się duże) - sugerują, że to, czego potrzebujemy, to stosunkowo niewielka losowa próbka, bez zamiany, wszystkich n! = n * (n-1) (n-2) ... * 2 * 1 permutacje 1: n. Jeśli to prawda, istnieją (nieco) wydajne rozwiązania.
Poniższa funkcja
rperm
akceptuje dwa argumentyn
(rozmiar permutacji do próbki) im
(liczba permutacji o rozmiarze n do narysowania). Jeśli m zbliży się lub przekroczy n !, funkcja zajmie dużo czasu i zwróci wiele wartości NA: jest przeznaczona do użycia, gdy n jest względnie duże (powiedzmy 8 lub więcej), a m jest znacznie mniejsze niż n !. Działa poprzez buforowanie reprezentacji łańcuchowej znalezionych dotychczas permutacji, a następnie generowanie nowych permutacji (losowo), aż do znalezienia nowej. Wykorzystuje zdolność asocjatywnego indeksowania list R do szybkiego przeszukiwania listy znalezionych wcześniej permutacji.Naturą
replicate
jest zwracanie permutacji jako wektorów kolumnowych ; np . następujący tekst odtwarza przykład z pierwotnego pytania, transponowanego :Czasy są doskonałe dla małych do umiarkowanych wartości m, do około 10 000, ale zmniejszają się w przypadku większych problemów. Na przykład próbkę m = 10 000 permutacji n = 1000 elementów (macierz 10 milionów wartości) uzyskano w 10 sekund; próbka m = 20 000 permutacji n = 20 elementów wymagała 11 sekund, mimo że wynik (macierz 400 000 wpisów) był znacznie mniejszy; a próbka obliczeniowa m = 100 000 permutacji n = 20 elementów została przerwana po 260 sekundach (nie miałem czasu czekać na zakończenie). Ten problem skalowania wydaje się być związany z nieefektywnością skalowania w adresowaniu asocjacyjnym R. Można obejść ten problem, generując próbki w grupach, powiedzmy, około 1000, a następnie łącząc je w dużą próbkę i usuwając duplikaty.
Edytować
Oto kilka upływających czasów w sekundach dla zakresu rozmiarów permutacji i liczby różnych żądanych kombinacji:
(Pozornie nietypowe przyspieszenie od rozmiaru = 10 do rozmiaru = 15 jest spowodowane tym, że pierwszy poziom pamięci podręcznej jest większy dla rozmiaru = 15, co zmniejsza średnią liczbę wpisów na listach drugiego poziomu, przyspieszając w ten sposób wyszukiwanie asocjacyjne R. koszt pamięci RAM, wykonanie można przyspieszyć, zwiększając rozmiar pamięci podręcznej wyższego poziomu. Po prostu zwiększenie
k.head
o 1 (co zwielokrotnia rozmiar górnego poziomu przez 10) przyspieszyło np.rperm(100000, size=10)
z 11,77 sekundy do 8,72 sekundy. pamięć podręczna 10-krotnie większa, ale nie osiągnęła żadnego znaczącego wzmocnienia, taktując 8,51 sekundy.)Z wyjątkiem przypadku 1 000 000 unikalnych permutacji 10 elementów (znaczna część wszystkich 10! = Około 3,63 miliona takich permutacji) praktycznie nigdy nie wykryto kolizji. W tym wyjątkowym przypadku doszło do 169 301 kolizji, ale nie doszło do całkowitej awarii (faktycznie uzyskano milion unikalnych kombinacji).
Następuje kod roboczy.
źródło
> 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
unique
Właściwe użycie powinno załatwić sprawę:źródło
Przejdę trochę do twojego pierwszego pytania i zasugeruję, że jeśli masz do czynienia ze stosunkowo krótkimi wektorami, możesz po prostu wygenerować wszystkie permutacje za pomocą
permn
i losowo uporządkować te za pomocąsample
:źródło
permn(10)
lub cokolwiek innego tylko raz.set.seed
: opisuje, jak zapisać stan RNG i przywrócić go później.