查找给定数字 n - javascript python 的所有偶数因式分解
Finding all even factorizations of a given number n - javascript python
目前我正在实现一种算法,该算法依赖于查找给定数字 n 的所有偶数因式分解,包括 n。
我已经尝试了一些方法,但总的来说我无法很好地处理这个问题。递归处理它也许是个好主意,但我还不太擅长 javascript,尤其是语言的高级方面可能会派上用场。
function evens(n) {
evens = []
for (var i = 2; i < n/2 - 1; i++){
if (i % 2 != 0){
continue;
}
else {
if ((n/i) % 2 == 0) {
evens.push([n/i, i])
}
}
}
return evens
}
这是一些代码,但考虑到所有正确的基本情况,我还不能递归地实现它。
我还认为可以用树状结构来完成,其中路径是偶数因子,但是我的cs知识很差。
也欢迎 Python 中的建议,但 javascript 最好。
只是为了让一切更清楚:例如,136 的所有偶数分解是 [[68, 2], [34, 2, 2], [34, 4], [136]]。
感谢您的帮助:)
在cdlane正确指出我方案的缺陷后,我收回了原方案,将cdlane优雅的python方案移植到javascript。
function even_factorization(n) {
let solutions = [];
function even_divisors(n) {
var divisors = [];
for (let i = 2; i <= n; i += 2) {
if (n % i === 0) divisors.push(i);
}
return divisors;
}
function remove_similarities(combos) {
for (let i = 0; i < combos.length; i++) {
for (let j = i + 1; j < combos.length; j++) {
if (combos[i].sort((a,b) => a - b).join(" ") === combos[j].sort((a,b) => a - b).join(" ")) {
combos.splice(j--,1);
}
}
}
return combos;
}
even_divisors(n).forEach(divisor => {
if (divisor === n)
solutions.push([divisor]);
else {
even_factorization(n / divisor).forEach(solution => {
solutions.push([divisor, ...solution]);
});
}
});
return remove_similarities(solutions);
}
运行 218960 returns...
- [[2,2,2,27370],[2,2,10,5474],[2,2,14,3910],[2,2,34,1610],[2,2 ,46,1190],[2,2,70,782],[2,2,170,322],[2,2,230,238],[2,2,54740],[2,4,27370],[2,10,14,782], [2,10,34,322],[2,10,46,238],[2,10,10948],[2,14,34,230],[2,14,46,170],[2,14,7820],[2 ,20,5474],[2,28,3910],[2,34,46,70],[2,34,3220],[2,46,2380],[2,68,1610],[2 ,70,1564],[2,92,1190],[2,140,782],[2,170,644],[2,230,476],[2,238,460],[2,322,340],[2,109480],[4,10,5474],[4 ,14,3910],[4,34,1610],[4,46,1190],[4,70,782],[4,170,322],[4,230,238],[4,54740],[8,27370],[10 ,14,34,46],[10,14,1564],[10,28,782],[10,34,644],[10,46,476],[10,68,322],[10,92,238],[10,21896 ],[14,20,782],[14,34,460],[14,46,340],[14,68,230],[14,92,170],[14,15640],[20,34,322],[20,46,238], [20,10948],[28,34,230],[28,46,170],[28,7820],[34,46,140],[34,70,92],[34,6440],[40,5474], [46,68,70],[46,4760],[56,3910],[68,3220],[70,3128],[92,2380],[136,1610],[140,1564], [170,1288],[184,1190],[230,952],[238,920],[280,782],[322,680],[340,644],[460,476],[218960]]
...和运行 136 returns...
- [[2,2,34],[2,68],[4,34],[136]]
Maybe its a good idea to handle it recursively
这是我在 Python 中的递归解决方案的尝试:
def even_factorization(n):
solutions = []
def even_divisors(n): # 136 generates [2, 4, 8, 34, 68, 136]
return (d for d in range(2, n + 1, 2) if n % d == 0)
def remove_similarities(array): # [[2, 2, 34], [2, 34, 2], [34, 2, 2]] -> [[2, 2, 34]]
return list(map(list, set(map(lambda a: tuple(sorted(a)), array))))
for divisor in even_divisors(n):
if divisor == n:
solutions.append([divisor])
else:
for solution in even_factorization(n // divisor):
solutions.append([divisor] + solution)
return remove_similarities(solutions) # return 'solutions' to see raw data
对于 136 returns:
[[2, 2, 34], [4, 34], [2, 68], [136]]
218960 returns:
[[184, 1190], [8, 27370], [4, 54740], [2, 70, 1564], [56, 3910], [2, 2, 170, 322],
[280, 782], [70, 3128], [4, 46, 1190], [2, 2, 34, 1610], [2, 14, 34, 230],
[2, 14, 7820], [20, 34, 322], [10, 14, 34, 46], [14, 92, 170], [20, 46, 238],
[218960], [2, 322, 340], [10, 68, 322], [34, 46, 140], [10, 14, 1564],
[2, 10, 10948], [10, 92, 238], [4, 170, 322], [92, 2380], [14, 20, 782],
[10, 21896], [238, 920], [28, 34, 230], [10, 28, 782], [2, 2, 46, 1190],
[2, 28, 3910], [10, 34, 644], [34, 6440], [2, 92, 1190], [46, 4760], [2, 170, 644],
[2, 68, 1610], [4, 70, 782], [340, 644], [2, 34, 46, 70], [2, 20, 5474],
[14, 68, 230], [2, 34, 3220], [4, 34, 1610], [4, 10, 5474], [28, 7820],
[14, 34, 460], [322, 680], [10, 46, 476], [2, 2, 54740], [4, 230, 238],
[2, 2, 2, 27370], [34, 70, 92], [2, 140, 782], [14, 15640], [2, 10, 46, 238],
[2, 10, 14, 782], [2, 14, 46, 170], [2, 238, 460], [136, 1610], [2, 2, 10, 5474],
[20, 10948], [4, 14, 3910], [40, 5474], [2, 2, 70, 782], [2, 2, 230, 238],
[230, 952], [68, 3220], [2, 46, 2380], [2, 230, 476], [2, 10, 34, 322],
[140, 1564], [460, 476], [170, 1288], [2, 4, 27370], [46, 68, 70], [14, 46, 340],
[2, 109480], [28, 46, 170], [2, 2, 14, 3910]]
目前我正在实现一种算法,该算法依赖于查找给定数字 n 的所有偶数因式分解,包括 n。
我已经尝试了一些方法,但总的来说我无法很好地处理这个问题。递归处理它也许是个好主意,但我还不太擅长 javascript,尤其是语言的高级方面可能会派上用场。
function evens(n) {
evens = []
for (var i = 2; i < n/2 - 1; i++){
if (i % 2 != 0){
continue;
}
else {
if ((n/i) % 2 == 0) {
evens.push([n/i, i])
}
}
}
return evens
}
这是一些代码,但考虑到所有正确的基本情况,我还不能递归地实现它。 我还认为可以用树状结构来完成,其中路径是偶数因子,但是我的cs知识很差。
也欢迎 Python 中的建议,但 javascript 最好。
只是为了让一切更清楚:例如,136 的所有偶数分解是 [[68, 2], [34, 2, 2], [34, 4], [136]]。
感谢您的帮助:)
在cdlane正确指出我方案的缺陷后,我收回了原方案,将cdlane优雅的python方案移植到javascript。
function even_factorization(n) {
let solutions = [];
function even_divisors(n) {
var divisors = [];
for (let i = 2; i <= n; i += 2) {
if (n % i === 0) divisors.push(i);
}
return divisors;
}
function remove_similarities(combos) {
for (let i = 0; i < combos.length; i++) {
for (let j = i + 1; j < combos.length; j++) {
if (combos[i].sort((a,b) => a - b).join(" ") === combos[j].sort((a,b) => a - b).join(" ")) {
combos.splice(j--,1);
}
}
}
return combos;
}
even_divisors(n).forEach(divisor => {
if (divisor === n)
solutions.push([divisor]);
else {
even_factorization(n / divisor).forEach(solution => {
solutions.push([divisor, ...solution]);
});
}
});
return remove_similarities(solutions);
}
运行 218960 returns...
- [[2,2,2,27370],[2,2,10,5474],[2,2,14,3910],[2,2,34,1610],[2,2 ,46,1190],[2,2,70,782],[2,2,170,322],[2,2,230,238],[2,2,54740],[2,4,27370],[2,10,14,782], [2,10,34,322],[2,10,46,238],[2,10,10948],[2,14,34,230],[2,14,46,170],[2,14,7820],[2 ,20,5474],[2,28,3910],[2,34,46,70],[2,34,3220],[2,46,2380],[2,68,1610],[2 ,70,1564],[2,92,1190],[2,140,782],[2,170,644],[2,230,476],[2,238,460],[2,322,340],[2,109480],[4,10,5474],[4 ,14,3910],[4,34,1610],[4,46,1190],[4,70,782],[4,170,322],[4,230,238],[4,54740],[8,27370],[10 ,14,34,46],[10,14,1564],[10,28,782],[10,34,644],[10,46,476],[10,68,322],[10,92,238],[10,21896 ],[14,20,782],[14,34,460],[14,46,340],[14,68,230],[14,92,170],[14,15640],[20,34,322],[20,46,238], [20,10948],[28,34,230],[28,46,170],[28,7820],[34,46,140],[34,70,92],[34,6440],[40,5474], [46,68,70],[46,4760],[56,3910],[68,3220],[70,3128],[92,2380],[136,1610],[140,1564], [170,1288],[184,1190],[230,952],[238,920],[280,782],[322,680],[340,644],[460,476],[218960]]
...和运行 136 returns...
- [[2,2,34],[2,68],[4,34],[136]]
Maybe its a good idea to handle it recursively
这是我在 Python 中的递归解决方案的尝试:
def even_factorization(n):
solutions = []
def even_divisors(n): # 136 generates [2, 4, 8, 34, 68, 136]
return (d for d in range(2, n + 1, 2) if n % d == 0)
def remove_similarities(array): # [[2, 2, 34], [2, 34, 2], [34, 2, 2]] -> [[2, 2, 34]]
return list(map(list, set(map(lambda a: tuple(sorted(a)), array))))
for divisor in even_divisors(n):
if divisor == n:
solutions.append([divisor])
else:
for solution in even_factorization(n // divisor):
solutions.append([divisor] + solution)
return remove_similarities(solutions) # return 'solutions' to see raw data
对于 136 returns:
[[2, 2, 34], [4, 34], [2, 68], [136]]
218960 returns:
[[184, 1190], [8, 27370], [4, 54740], [2, 70, 1564], [56, 3910], [2, 2, 170, 322],
[280, 782], [70, 3128], [4, 46, 1190], [2, 2, 34, 1610], [2, 14, 34, 230],
[2, 14, 7820], [20, 34, 322], [10, 14, 34, 46], [14, 92, 170], [20, 46, 238],
[218960], [2, 322, 340], [10, 68, 322], [34, 46, 140], [10, 14, 1564],
[2, 10, 10948], [10, 92, 238], [4, 170, 322], [92, 2380], [14, 20, 782],
[10, 21896], [238, 920], [28, 34, 230], [10, 28, 782], [2, 2, 46, 1190],
[2, 28, 3910], [10, 34, 644], [34, 6440], [2, 92, 1190], [46, 4760], [2, 170, 644],
[2, 68, 1610], [4, 70, 782], [340, 644], [2, 34, 46, 70], [2, 20, 5474],
[14, 68, 230], [2, 34, 3220], [4, 34, 1610], [4, 10, 5474], [28, 7820],
[14, 34, 460], [322, 680], [10, 46, 476], [2, 2, 54740], [4, 230, 238],
[2, 2, 2, 27370], [34, 70, 92], [2, 140, 782], [14, 15640], [2, 10, 46, 238],
[2, 10, 14, 782], [2, 14, 46, 170], [2, 238, 460], [136, 1610], [2, 2, 10, 5474],
[20, 10948], [4, 14, 3910], [40, 5474], [2, 2, 70, 782], [2, 2, 230, 238],
[230, 952], [68, 3220], [2, 46, 2380], [2, 230, 476], [2, 10, 34, 322],
[140, 1564], [460, 476], [170, 1288], [2, 4, 27370], [46, 68, 70], [14, 46, 340],
[2, 109480], [28, 46, 170], [2, 2, 14, 3910]]