Dla przykładu rozważmy liczbę 96. To może być napisany w następujący sposób:R Algorytm generowania wszystkich możliwych factorizations z szeregu
1. 96
2. 48 * 2
3. 24 * 2 * 2
4. 12 * 2 * 2 * 2
5. 6 * 2 * 2 * 2 * 2
6. 3 * 2 * 2 * 2 * 2 * 2
7. 4 * 3 * 2 * 2 * 2
8. 8 * 3 * 2 * 2
9. 6 * 4 * 2 * 2
10. 16 * 3 * 2
11. 4 * 4 * 3 * 2
12. 12 * 4 * 2
13. 8 * 6 * 2
14. 32 * 3
15. 8 * 4 * 3
16. 24 * 4
17. 6 * 4 * 4
18. 16 * 6
19. 12 * 8
wiem, że to jest związane z partycjami za każdym numerem wpisanym jako moc , n, pojedyncza liczba podstawowa, p, to po prostu liczba sposobów na zapisanie n. Na przykład, aby znaleźć wszystkie faktoryzacje 2^5, musimy znaleźć wszystkie sposoby na napisanie 5. Są to:
- 1 + 1 + 1 + 1 + 1 == >> 2^1 * 2^1 * 2^1 * 2^1 * 2^1
- 1 + 1 + 1 + 2 == >> 2^1 * 2^1 * 2^1 * 2^2
- 1 + 1 + 3 == >> 2^1 * 2^1 * 2^3
- 1 + 2 + 2 == >> 2^1 * 2^2 * 2^2
- 1 + 4 == >> 2^1 * 2^4
- 2 + 3 == >> 2^2 * 2^3
- 5 == >> 2^5
Znalazłem wspaniały artykuł autorstwa Jerome'a Kellehera na temat algorytmów generowania partycji here. Mam dostosowany jedną ze swoich algorytmów Python R. Kod jest poniżej:
library(partitions) ## using P(n) to determine number of partitions of an integer
IntegerPartitions <- function(n) {
a <- 0L:n
k <- 2L
a[2L] <- n
MyParts <- vector("list", length=P(n))
count <- 0L
while (!(k==1L)) {
x <- a[k-1L]+1L
y <- a[k]-1L
k <- k-1L
while (x<=y) {a[k] <- x; y <- y-x; k <- k+1L}
a[k] <- x+y
count <- count+1L
MyParts[[count]] <- a[1L:k]
}
MyParts
}
próbowałem przedłużyć tę metodę do numerów z więcej niż jednego czynnika jedna premiera, ale mój kod dostał bardzo niezgrabne. Po walce z tym pomysłem przez chwilę postanowiłem spróbować innej trasy. Mój nowy algorytm nie ma zastosowania do generowania partycji. Jest to bardziej "lookback" algorytm, który korzysta z faktoryzacji, które zostały już wygenerowane. Kod znajduje się poniżej:
FactorRepresentations <- function(n) {
MyFacts <- EfficientFactorList(n)
MyReps <- lapply(1:n, function(x) x)
for (k in 4:n) {
if (isprime(k)) {next}
myset <- MyFacts[[k]]
mylist <- vector("list")
mylist[[1]] <- k
count <- 1L
for (j in 2:ceiling(length(myset)/2)) {
count <- count+1L
temp <- as.integer(k/myset[j])
myvec <- sort(c(myset[j], temp), decreasing=TRUE)
mylist[[count]] <- myvec
MyTempRep <- MyReps[[temp]]
if (isprime(temp) || temp==k) {next}
if (length(MyTempRep)>1) {
for (i in 1:length(MyTempRep)) {
count <- count+1L
myvec <- sort(c(myset[j], MyTempRep[[i]]), decreasing=TRUE)
mylist[[count]] <- myvec
}
}
}
MyReps[[k]] <- unique(mylist)
}
MyReps
}
Pierwsza funkcja w powyższym kodzie jest po prostu funkcją, która generuje wszystkie czynniki. Oto kod, jeśli jesteś ciekaw:
EfficientFactorList <- function(n) {
MyFactsList <- lapply(1:n, function(x) 1)
for (j in 2:n) {
for (r in seq.int(j, n, j)) {MyFactsList[[r]] <- c(MyFactsList[[r]], j)}
}
MyFactsList
}
Mój algorytm jest po prostu w porządku jeśli chodzi tylko o numerach mniej niż 10.000 (generuje wszystkie factorizations dla każdej liczby < = 10000 w ciągu około 17 sekund), ale zdecydowanie nie skaluje się dobrze. Chciałbym znaleźć algorytm, który ma tę samą przesłankę generowania listy wszystkich faktoryzacji dla każdej liczby mniejszej lub równej n, ponieważ niektóre z aplikacji, które mam na myśli, będą odwoływać się do danej faktoryzacji wiele razy, a więc mieć ją na liście powinna być szybsza niż generowanie jej w locie za każdym razem (wiem, że jest tu koszt pamięci).
To nie jest prosty problem (oczywiście), ale w przypadku, gdy jeszcze go nie znalazłeś, oto odpowiedni wpis z internetowej encyklopedii ciągów liczb całkowitych: https://oeis.org/A001055 –
To jest bardzo pomocne, choć daje to całkowitą liczbę faktoryzacji, a nie faktyczne same faktoryzacje. Na przykład, dla n = 96 jak wyżej, daje 19. –