Próbuję pokazać mojemu synowi, w jaki sposób kodowania można użyć do rozwiązania problemu związanego z grą, a także zobaczyć, jak R obsługuje duże zbiory danych. Ta gra nazywa się „Lucky 26”. W tej grze numery (1-12 bez duplikatów) są umieszczane na 12 punktach na gwiazdce Davida (6 wierzchołków, 6 skrzyżowań), a 6 linii po 4 liczby muszą się sumować do 26. Z około 479 milionów możliwości (12P12 ) najwyraźniej istnieją 144 rozwiązania. Próbowałem to zakodować w R w następujący sposób, ale wydaje się, że problem z pamięcią. Byłbym bardzo wdzięczny za każdą poradę, aby udzielić odpowiedzi, jeśli członkowie mają czas. Z góry dziękując członkom.
library(gtools)
x=c()
elements <- 12
for (i in 1:elements)
{
x[i]<-i
}
soln=c()
y<-permutations(n=elements,r=elements,v=x)
j<-nrow(y)
for (i in 1:j)
{
L1 <- y[i,1] + y[i,3] + y[i,6] + y[i,8]
L2 <- y[i,1] + y[i,4] + y[i,7] + y[i,11]
L3 <- y[i,8] + y[i,9] + y[i,10] + y[i,11]
L4 <- y[i,2] + y[i,3] + y[i,4] + y[i,5]
L5 <- y[i,2] + y[i,6] + y[i,9] + y[i,12]
L6 <- y[i,5] + y[i,7] + y[i,10] + y[i,12]
soln[i] <- (L1 == 26)&(L2 == 26)&(L3 == 26)&(L4 == 26)&(L5 == 26)&(L6 == 26)
}
z<-which(soln)
z
r
bigdata
permutation
DesertProject
źródło
źródło
x<- 1:elements
i co ważniejszeL1 <- y[,1] + y[,3] + y[,6] + y[,8]
. To naprawdę nie pomogłoby w problemie z pamięcią, więc zawsze możesz zajrzeć do rcpprm(list=ls())
swojego MRE. Jeśli ktoś skopiuje i wklei do aktywnej sesji, może utracić własne dane.Odpowiedzi:
Oto inne podejście. Opiera się na postu na blogu MathWorks autorstwa Cleve Moler , autora pierwszego MATLAB-a.
W poście na blogu, aby zaoszczędzić pamięć, autor dopuszcza tylko 10 elementów, zachowując pierwszy element jako element wierzchołkowy, a 7 jako element podstawowy. Dlatego
10! == 3628800
należy przetestować tylko permutacje.W poniższym kodzie
1
do10
. Jest ich w sumie10! == 3628800
.11
jako element wierzchołka i utrzymuj go w stałym położeniu. Naprawdę nie ma znaczenia, gdzie zaczynają się zadania, pozostałe elementy będą w odpowiednich pozycjach względnych .for
pętli.Powinno to wytworzyć większość rozwiązań, dać lub obrócić i odbić. Ale to nie gwarantuje, że rozwiązania są wyjątkowe. Jest także dość szybki.
źródło
W rzeczywistości istnieje 960 rozwiązań. Poniżej używamy
Rcpp
,RcppAlgos
* iparallel
pakietu, aby uzyskać rozwiązanie nieco ponad6 seconds
4 rdzeni. Nawet jeśli zdecydujesz się zastosować podejście jednowątkowe z podstawami Rlapply
, rozwiązanie jest zwracane w około 25 sekund.Najpierw piszemy prosty algorytm,
C++
który sprawdza konkretną permutację. Zauważysz, że używamy jednej tablicy do przechowywania wszystkich sześciu linii. Ma to na celu zwiększenie wydajności, ponieważ efektywniej wykorzystujemy pamięć podręczną niż 6 pojedynczych tablic. Musisz także pamiętać, żeC++
używa indeksowania zerowego.Teraz, korzystając z argumentów
lower
i , możemy wygenerować fragmenty permutacji i przetestować je indywidualnie, aby utrzymać pamięć pod kontrolą. Poniżej postanowiłem przetestować około 4,7 miliona permutacji na raz. Dane wyjściowe dają indeksy leksykograficzne permutacji 12! tak, że warunek Lucky 26 jest spełniony.upper
permuteGeneral
Teraz weryfikujemy użycie
permuteSample
i argument,sampleVec
który pozwala wygenerować określone permutacje (np. Jeśli przejdziesz 1, da ci to pierwszą permutację (tj.1:12
)).Na koniec weryfikujemy nasze rozwiązanie z bazą R
rowSums
:* Jestem autorem
RcppAlgos
źródło
Do permutacji rcppalgos jest świetny. Niestety istnieje 479 milionów możliwości z 12 polami, co oznacza, że zabiera zbyt dużo pamięci dla większości ludzi:
Istnieje kilka alternatyw.
Pobierz próbkę permutacji. To znaczy, zrób tylko 1 milion zamiast 479 milionów. Aby to zrobić, możesz użyć
permuteSample(12, 12, n = 1e6)
. Zobacz odpowiedź @ JosephWood na nieco podobne podejście, z wyjątkiem tego, że pobiera próbki do 479 milionów permutacji;)Zbuduj pętlę w rcpp, aby ocenić permutację podczas tworzenia. Oszczędza to pamięć, ponieważ w rezultacie budowałbyś funkcję zwracającą tylko prawidłowe wyniki.
Podejdź do problemu za pomocą innego algorytmu. Skoncentruję się na tej opcji.
Nowy algorytm z ograniczeniami
Segmenty powinny mieć 26
Wiemy, że każdy segment linii w gwiazdce powyżej musi dodać do 26. Możemy dodać to ograniczenie do generowania naszych permutacji - daj nam tylko kombinacje, które sumują się do 26:
Grupy ABCD i EFGH
W gwiazdce powyżej kolorowałem trzy grupy inaczej: ABCD , EFGH i IJLK . Dwie pierwsze grupy również nie mają wspólnych punktów i znajdują się również w interesujących segmentach linii. Dlatego możemy dodać kolejne ograniczenie: w przypadku kombinacji, które sumują się do 26, musimy upewnić się, że ABCD i EFGH nie nakładają się na siebie liczb. IJLK zostaną przypisane pozostałe 4 numery.
Permute poprzez grupy
Musimy znaleźć wszystkie permutacje każdej grupy. Oznacza to, że mamy tylko kombinacje, które sumują się do 26. Na przykład musimy wziąć
1, 2, 11, 12
i wykonać1, 2, 12, 11; 1, 12, 2, 11; ...
.Ostateczne obliczenia
Ostatnim krokiem jest zrobienie matematyki. Używam
lapply()
iReduce()
tutaj, aby robić bardziej funkcjonalne programowanie - w przeciwnym razie wiele kodu zostanie wpisanych sześć razy. Zobacz oryginalne rozwiązanie, aby uzyskać dokładniejsze objaśnienie kodu matematycznego.Zamiana ABCD i EFGH
Na końcu powyższego kodu skorzystałem z możliwości wymiany
ABCD
iEFGH
uzyskania pozostałych permutacji. Oto kod potwierdzający, że tak, możemy zamienić dwie grupy i być poprawnym:Wydajność
Ostatecznie oceniliśmy tylko 1,3 miliona spośród 479 permutacji i tylko przetasowaliśmy tylko przez 550 MB pamięci RAM. Uruchomienie zajmuje około 0,7 sekundy
źródło
Oto rozwiązanie dla małego gościa:
źródło