Ví dụ, hãy xem xét số 96. Nó có thể được viết bằng những cách sau đây:R Thuật toán để tạo ra tất cả factorizations có thể của một số
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
Tôi biết điều này có liên quan đến phân vùng như bất kỳ số văn bản như sức mạnh , n, của một số nguyên tố, p, chỉ đơn giản là số cách bạn có thể viết n. Ví dụ: để tìm tất cả các thừa số của 2^5, chúng tôi phải tìm tất cả các cách để viết 5. Chúng là:
- 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
Tôi đã tìm thấy một bài viết tuyệt vời của Jerome Kelleher về thuật toán tạo phân vùng here. Tôi đã thích nghi một trong những thuật toán python của mình để R. Đoạn mã dưới:
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
}
Tôi đã cố gắng để mở rộng phương pháp này để số với hơn một hơn một yếu tố quan trọng, nhưng mã của tôi trở nên rất vụng về. Sau khi đấu vật với ý tưởng này một lúc, tôi quyết định thử một con đường khác. Thuật toán mới của tôi không sử dụng phân vùng tạo nào. Nó là một thuật toán "tra cứu" tận dụng lợi thế của các yếu tố đã được tạo ra. Mã bên dưới:
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
}
Hàm đầu tiên trong mã trên chỉ đơn giản là hàm tạo ra tất cả các yếu tố. Đây là mã nếu bạn tò mò:
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
}
thuật toán của tôi chỉ là okay nếu bạn chỉ quan tâm đến số dưới 10.000 (nó tạo ra tất cả factorizations cho mỗi số < = 10.000 trong khoảng 17 giây), nhưng nó chắc chắn không mở rộng tốt. Tôi muốn tìm một thuật toán có cùng một tiền đề tạo ra một danh sách tất cả các thừa số cho mỗi số nhỏ hơn hoặc bằng n vì một số ứng dụng tôi có trong tâm trí sẽ tham chiếu một hệ số đã cho nhiều lần, do đó có nó trong một danh sách nên nhanh hơn tạo ra nó trên bay mọi lúc (tôi biết có một chi phí bộ nhớ ở đây).
Đây không phải là một vấn đề đơn giản (rõ ràng) nhưng trong trường hợp bạn chưa tìm thấy nó, đây là mục có liên quan từ Bách khoa toàn thư trực tuyến của chuỗi số nguyên: https://oeis.org/A001055 –
Đây là rất hữu ích, mặc dù điều này chỉ cho tổng số các thừa số và không phải là các yếu tố thực tế. Ví dụ, đối với n = 96 như trên, nó mang lại cho 19. –