Jos*_*ood 8 algorithm r factorization
例如,考虑数字96.可以用以下方式编写:
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
我知道这与分区有关,因为任何数字写为单个素数p的幂n,只是你可以编写n的方式.例如,要找到2 ^ 5的所有因子分解,我们必须找到所有写入5的方法.它们是:
我发现杰罗姆·凯莱赫约分区生成算法精彩的文章在这里.我已经将他的一个python算法改编为R.代码如下:
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
}
我试图将这种方法扩展到具有一个以上素数因子的数字,但我的代码变得非常笨重.在与这个想法挣扎了一段时间后,我决定尝试不同的路线.我的新算法不使用任何生成分区.它更像是一种"回顾"算法,它利用了已经生成的因子分解.代码如下:
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
}
上面代码中的第一个函数只是一个生成所有因子的函数.如果你很好奇,这是代码:
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
}
如果你只关心小于10,000的数字,我的算法就可以了(它会在大约17秒内为每个数字<= 10,000生成所有因子分解),但它肯定不能很好地扩展.我想找到一个算法,它具有相同的前提,即为每个小于或等于n的数字生成所有因子分解的列表,因为我想到的一些应用程序将多次引用给定的分解,因此将其放入list应该比每次动态生成它更快(我知道这里有内存成本).
你的函数EfficientFactorList可以很好地有效地抓取从1到n的每个数字的所有因子的集合,所以剩下的就是得到所有因子的集合.正如您所建议的那样,使用较小值的因子来计算较大值的因子分解似乎可能是有效的.
考虑数k,其中因子为k_1,k_2,...,k_n.一种简单的方法是组合k/k_1,k/k_2,...,k/k_n的因子分解,将k_i附加到k/k_i的每个因子分解以产生k的因子分解.作为一个有效的例子,考虑计算16的因子(具有非平凡因子2,4和8).2具有因式分解{2},4具有分解{4,2*2},并且8具有分解{8,4*2,2*2*2},因此我们将通过首先计算{2来计算全部分解因子*8,4*4,2*2*4,8*2,4*2*2,2*2*2*2}然后采用独特的因子分解,{8*2,4*4,4*2*2,2*2*2*2}.添加16会产生最终答案.
更有效的方法是注意到我们不需要将k_i附加到k/k_i的所有因子分解.例如,我们不需要从4的因子分解中添加2*2*4,因为这已经从8的因子分解中包括在内.同样,我们不需要从2的因式分解中添加2*8,因为这从8的因子分解中已经包括了.通常,如果因子分解中的所有值都是k_i或更大,我们只需要包括k/k_i的因子分解.
在代码中:
library(gmp)
all.fact <- function(n) {
facts <- EfficientFactorList(n)
facts[[1]] <- list(1)
for (x in 2:n) {
if (length(facts[[x]]) == 2) {
facts[[x]] <- list(x) # Prime number
} else {
x.facts <- facts[[x]][facts[[x]] != 1 & facts[[x]] <= (x^0.5+0.001)]
allSmaller <- lapply(x.facts, function(pf) lapply(facts[[x/pf]], function(y) {
if (all(y >= pf)) {
return(c(pf, y))
} else {
return(NULL)
}
}))
allSmaller <- do.call(c, allSmaller)
facts[[x]] <- c(x, allSmaller[!sapply(allSmaller, function(y) is.null(y))])
}
}
return(facts)
}
这比发布的代码更快:
system.time(f1 <- FactorRepresentations(10000))
# user system elapsed
# 13.470 0.159 13.765
system.time(f2 <- all.fact(10000))
# user system elapsed
# 1.602 0.028 1.641
作为完整性检查,它还为每个数字返回相同数量的因子分解:
lf1 <- sapply(f1, length)
lf2 <- sapply(f2, length)
all.equal(lf1, lf2)
# [1] TRUE