Список целочисленной факторизации на N условия


Я хочу, самый быстрый способ в Mathematica 7 для формирования списка факторов (не простые множители) целых чисел на заданное количество терминов, причем каждый фактор больше единицы.

Например, 240 в три срока:

{{2,2,60}, {2,3,40}, {2,4,30}, {2,5,24}, {2,6,20}, {2,8,15}, {2,10,12},
 {3,4,20}, {3,5,16}, {3,8,10}, {4,4,15}, {4,5,12}, {4,6,10}, {5,6,8}}

Мой начальный код на основе рекурсивного метода источник которого я забыл, но, наверное, кто-то на projecteuler.net:

f[n_, 1, ___] := {{n}}

f[n_, k_, x_: 2] :=
 Join @@ Table[
   If[q < x, {}, {q, ##} & @@@ f[n/q, k - 1, q]],
   {q, # ~Take~ ⌈Length@#/k⌉ & @ Divisors @ n}
 ]

f[240, 3]

Мемоизация может быть применен в нескольких местах. В случае больших чисел это гораздо быстрее, за счет памяти конечно. Здесь, с мемоизацией в трех точках:

Clear[f, div]

div@n_ := div@n = Divisors@n

div[n_, k_] := div[n, k] = # ~Take~ ⌈Length@#/k⌉ & @ div @ n

f[n_, 1, ___] := {{n}}

f[n_, k_, x_: 2] := f[n, k, x] =
 Join @@ Table[
   If[q < x, {}, {q, ##} & @@@ f[n/q, k - 1, q]],
   {q, n~div~k}
  ]

По сравнению с Код Саши на большое составное число:

f[10080^2, 5] // Length // Timing
 {0.891, 103245}
FactorIntoFixedTerms[10080^2, 5] // Length // Timing
 {25.594, 103245}

Это может быть улучшено?



Комментарии
1 ответ

Так как делитель является довольно эффективным в своей работе, единственная оптимизация, я вижу, чтобы избежать ненужных вызовов, с помощью мемоизации техника:

FactorIntoFixedTerms[in_Integer, terms_Integer] := Block[{f, div},
div[n_] := (div[n] = Divisors[n]);
f[n_, 1] := {{n}};
f[n_, k_] :=
Join @@ Table[{q, ##} & @@@
Select[f[n/q,
k - 1], #[[1]] >=
q &], {q, #[[2 ;; \[LeftCeiling]Length@#/
k\[RightCeiling]]] &@div@n}];
f[in, terms]
]

Это может привести к существенному сокращению сроков:

In[683]:= FactorIntoFixedTerms[1453522322112240, 6] // Length // Timing

Out[683]= {0.047, 47}

In[685]:= foriginal[1453522322112240, 6] // Length // Timing

Out[685]= {0.39, 47}

6
ответ дан 6 мая 2011 в 06:05 Источник Поделиться