Нахождение всех четных факторизаций заданного числа n - javascript python - PullRequest
Новая
       36

Нахождение всех четных факторизаций заданного числа n - javascript python

2 голосов
/ 11 мая 2019

В настоящее время я реализую алгоритм, который основан на нахождении всех четных факторизаций заданного числа 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]].

Спасибо за любую помощь:)

Ответы [ 2 ]

2 голосов
/ 12 мая 2019

Может быть, это хорошая идея рекурсивно обрабатывать

Вот моя попытка рекурсивного решения в 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 возвратов: 

[[2, 2, 34], [4, 34], [2, 68], [136]]

для 218960 возвратов: 

[[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]]
2 голосов
/ 12 мая 2019

После того, как cdlane правильно указал на недостаток в моем решении, я отозвал свое оригинальное решение и перенес элегантное Python-решение cdlane на 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 возвращает ...

  • [[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], [2140782], [2170644], [2230476], [2238460], [2322340], [2,109480], [4,10,5474], [4, 14,3910], [4,34,1610], [4,46,1190], [4,70,782], [4170322], [4230238], [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], [230952], [238920], [280782], [322680], [340644], [460476], [218960]]

... и работает с 136 возвратами ...

  • [[2,2,34], [2,68], [4,34], [136]]
...