По запросу "oracle factorial" с ходу нагугливаются два подхода к вычислению факториала в СУБД Oracle:
-
самоочевидный: в цикле получить произведение натуральных чисел от 1 до n
create or replace function fac1(n pls_integer) return number is f number := 1; begin if n in (0, 1) then return 1; end if; for i in 2..n loop f := f * i; end loop; return f; end fac1; / -
забавный: вместо произведения натуральных чисел от 1 до n найти сумму их логарифмов, а затем возвести основание логарифма в найденную степень
create or replace function fac2(n pls_integer) return number is f number; begin select round(exp(sum(ln(level)))) into f from dual connect by level <= n; return f; end fac2; /
Обе функции дают одинаковые результаты, пока значение аргумента невелико:
SQL> select level-1, fac1(level-1), fac2(level-1) from dual connect by level <= 11;
LEVEL-1 FAC1(LEVEL-1) FAC2(LEVEL-1)
---------- ------------- -------------
0 1 1
1 1 1
2 2 2
3 6 6
4 24 24
5 120 120
6 720 720
7 5040 5040
8 40320 40320
9 362880 362880
10 3628800 3628800
11 rows selected
Начиная с n = 33 возникают расхождения (из-за ограниченной точности нецелочисленных вычислений):
SQL> column fac2 format 999999999999999999999999999999999999999999999
SQL> column fac1 format 999999999999999999999999999999999999999999999
SQL> select lvl, fac1(lvl) fac1, fac2(lvl) fac2
2 from (select level-1 lvl from dual connect by level <= 36)
3 where fac1(lvl) != fac2(lvl);
LVL FAC1 FAC2
---------- ---------------------------------------------- ----------------------------------------------
33 8683317618811886495518194401280000000 8683317618811886495518194401280000001
34 295232799039604140847618609643520000000 295232799039604140847618609643520000022
35 10333147966386144929666651337523200000000 10333147966386144929666651337523200000800
Далее, обе функции перестают возвращать результат на 9-том десятке:
SQL> select level+80, fac1(level+80) fac from dual connect by level <= 10;
LEVEL+80 FAC
---------- ----------
81 5.797E+120
82 4.754E+122
83 3.946E+124
84 ~
85 ~
86 ~
87 ~
88 ~
89 ~
90 ~
10 rows selected.
SQL> select level+80, fac2(level+80) fac from dual connect by level <= 10;
ORA-01426: numeric overflow
ORA-06512: at "AY.FAC2", line 6
Как известно, значение типа number в Oracle не может быть больше 10126. А значение 84! оказывается больше этого числа.
Принимая во внимание этот факт, предлагаю третий подход к получению факториала.
Пока мы работаем в СУБД Oracle c типом данных number, нас не интересуют факториалы чисел больше 83. Поэтому, сохраним однажды вычисленные факториалы чисел от 0 до 83 в таблице PL/SQL и будем получать значение факториала n из нее по индексу n+1:
create or replace type number_nt as table of number;
/
create or replace
function fac3(n pls_integer) return number
is
c_fac number_nt := number_nt(
1, --0
1, --1
2, --2
6, --3
24, --4
120, --5
720, --6
5040, --7
40320, --8
362880, --9
3628800, --10
39916800, --11
479001600, --12
6227020800, --13
87178291200, --14
1307674368000, --15
20922789888000, --16
355687428096000, --17
6402373705728000, --18
121645100408832000, --19
2432902008176640000, --20
51090942171709440000, --21
1124000727777607680000, --22
25852016738884976640000, --23
620448401733239439360000, --24
15511210043330985984000000, --25
403291461126605635584000000, --26
10888869450418352160768000000, --27
304888344611713860501504000000, --28
8841761993739701954543616000000, --29
265252859812191058636308480000000, --30
8222838654177922817725562880000000, --31
263130836933693530167218012160000000, --32
8683317618811886495518194401280000000, --33
295232799039604140847618609643520000000, --34
10333147966386144929666651337523200000000, --35
371993326789901217467999448150835200000000, --36
13763753091226345046315979581580902400000000, --37
523022617466601111760007224100074291200000000, --38
20397882081197443358640281739902897356800000000, --39
815915283247897734345611269596115894272000000000, --40
33452526613163807108170062053440751665150000000000, --41
1405006117752879898543142606244511569936000000000000, --42
60415263063373835637355132068513997507200000000000000, --43
2658271574788448768043625811014615890320000000000000000, --44
119622220865480194561963161495657715064000000000000000000, --45
5502622159812088949850305428800254892944000000000000000000, --46
258623241511168180642964355153611979968400000000000000000000, --47
12413915592536072670862289047373375038480000000000000000000000, --48
608281864034267560872252163321295376886000000000000000000000000, --49
30414093201713378043612608166064768844300000000000000000000000000, --50
1551118753287382280224243016469303211060000000000000000000000000000, --51
80658175170943878571660636856403766975120000000000000000000000000000, --52
4274883284060025564298013753389399649681000000000000000000000000000000, --53
230843697339241380472092742683027581082800000000000000000000000000000000, --54
12696403353658275925965100847566516959550000000000000000000000000000000000, --55
710998587804863451854045647463724949735000000000000000000000000000000000000, --56
40526919504877216755680601905432322134900000000000000000000000000000000000000, --57
2350561331282878571829474910515074683820000000000000000000000000000000000000000, --58
138683118545689835737939019720389406345000000000000000000000000000000000000000000, --59
8320987112741390144276341183223364380700000000000000000000000000000000000000000000, --60
507580213877224798800856812176625227222700000000000000000000000000000000000000000000, --61
31469973260387937525653122354950764087810000000000000000000000000000000000000000000000, --62
1982608315404440064116146708361898137532000000000000000000000000000000000000000000000000, --63
126886932185884164103433389335161480802000000000000000000000000000000000000000000000000000, --64
8247650592082470666723170306785496252130000000000000000000000000000000000000000000000000000, --65
544344939077443064003729240247842752641000000000000000000000000000000000000000000000000000000, --66
36471110918188685288249859096605464426900000000000000000000000000000000000000000000000000000000, --67
2480035542436830599600990418569171581030000000000000000000000000000000000000000000000000000000000, --68
171122452428141311372468338881272839091000000000000000000000000000000000000000000000000000000000000, --69
1.197857166996989179607278372168909873640000000000000000000000000000000000000000000000000000000E+100, --70
8.504785885678623175211676442399260102844000000000000000000000000000000000000000000000000000000E+101, --71
6.123445837688608686152407038527467274048000000000000000000000000000000000000000000000000000000E+103, --72
4.470115461512684340891257138125051110055000000000000000000000000000000000000000000000000000000E+105, --73
3.307885441519386412259530282212537821441000000000000000000000000000000000000000000000000000000E+107, --74
2.480914081139539809194647711659403366081000000000000000000000000000000000000000000000000000000E+109, --75
1.885494701666050254987932260861146558222000000000000000000000000000000000000000000000000000000E+111, --76
1.451830920282858696340707840863082849831000000000000000000000000000000000000000000000000000000E+113, --77
1.132428117820629783145752115873204622868000000000000000000000000000000000000000000000000000000E+115, --78
8.946182130782975286851441715398316520660000000000000000000000000000000000000000000000000000000E+116, --79
7.156945704626380229481153372318653216530000000000000000000000000000000000000000000000000000000E+118, --80
5.797126020747367985879734231578109105390000000000000000000000000000000000000000000000000000000E+120, --81
4.753643337012841748421382069894049466420000000000000000000000000000000000000000000000000000000E+122, --82
3.945523969720658651189747118012061057130000000000000000000000000000000000000000000000000000000E+124 --83
);
begin
return c_fac(n+1);
end fac;
/
Проверим работу новой функции:
SQL> select level-1, fac1(level-1), fac2(level-1), fac3(level-1) from dual connect by level <= 21;
LEVEL-1 FAC1(LEVEL-1) FAC2(LEVEL-1) FAC3(LEVEL-1)
---------- ------------- ------------- -------------
0 1 1 1
1 1 1 1
2 2 2 2
3 6 6 6
4 24 24 24
5 120 120 120
6 720 720 720
7 5040 5040 5040
8 40320 40320 40320
9 362880 362880 362880
10 3628800 3628800 3628800
11 rows selected
SQL> select lvl
2 from (select level-1 lvl from dual connect by level <= 84)
3 where fac3(lvl) != fac1(lvl)
4 ;
LVL
----------
Последний запрос показывает, что на диапазоне входных значений от 0 до 83 результаты функций fac1 и fac3 совпадают.
Ниже привожу текст PL/SQL пакета, реализующего основные функции комбинаторики с использованием таблицы факториалов. Пакет предоставляет следующие функции, возвращающие результат типа number:
| Функция | Описание |
|---|---|
fac(n pls_integer) | факториал n |
permutations(n pls_integer) | число перестановок n элементов |
permutations_with_rep(n pls_integer, k number_nt) | число перестановок n элементов c повторениями, где таблица k задает кол-во повторений |
allocations(n pls_integer, k pls_integer) | число размещений k элементов из n |
allocations_with_rep(n pls_integer, k pls_integer) | число размещений с повторениями k элементов из n |
combinations(n pls_integer, k pls_integer) | число сочетаний k элементов из n |
combinations_with_rep(n pls_integer, k pls_integer) | число сочетаний с повторениями k элементов из n |
n_choose_k(n pls_integer, k pls_integer) | то же, что combinations |
create or replace package comics is
/*******************************************************************************
Common com(binator)ics functions.
Changelog
2017-05-12 Andrei Trofimov Create package.
********************************************************************************
Copyright (C) 2017 by Andrei Trofimov
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
********************************************************************************
*/
-- n!
function fac(n pls_integer) return number;
-- n!
function permutations(n pls_integer) return number;
-- n! / (k1!*k2!*...*km!), where sum(k) <= n
function permutations_with_rep(n pls_integer, k number_nt) return number;
-- n! / (n-k)!
function allocations(n pls_integer, k pls_integer) return number;
-- n to the k'th power
function allocations_with_rep(n pls_integer, k pls_integer) return number;
-- n! / ((n-k)! * k!)
function combinations(n pls_integer, k pls_integer) return number;
-- (k+n-1)! / ((n-1)! * k!)
function combinations_with_rep(n pls_integer, k pls_integer) return number;
-- another name for combinations
function n_choose_k(n pls_integer, k pls_integer) return number;
end comics;
/
create or replace package body comics is
/*
-- make list of factorials 0 through 83
declare
r number := 1;
begin
evu.p(r||', --0');
for i in 1..83 loop
r := r * i;
evu.p(r||', --'||i);
end loop;
end;
*/
c_fac number_nt := number_nt(
1, --0
1, --1
2, --2
6, --3
24, --4
120, --5
720, --6
5040, --7
40320, --8
362880, --9
3628800, --10
39916800, --11
479001600, --12
6227020800, --13
87178291200, --14
1307674368000, --15
20922789888000, --16
355687428096000, --17
6402373705728000, --18
121645100408832000, --19
2432902008176640000, --20
51090942171709440000, --21
1124000727777607680000, --22
25852016738884976640000, --23
620448401733239439360000, --24
15511210043330985984000000, --25
403291461126605635584000000, --26
10888869450418352160768000000, --27
304888344611713860501504000000, --28
8841761993739701954543616000000, --29
265252859812191058636308480000000, --30
8222838654177922817725562880000000, --31
263130836933693530167218012160000000, --32
8683317618811886495518194401280000000, --33
295232799039604140847618609643520000000, --34
10333147966386144929666651337523200000000, --35
371993326789901217467999448150835200000000, --36
13763753091226345046315979581580902400000000, --37
523022617466601111760007224100074291200000000, --38
20397882081197443358640281739902897356800000000, --39
815915283247897734345611269596115894272000000000, --40
33452526613163807108170062053440751665150000000000, --41
1405006117752879898543142606244511569936000000000000, --42
60415263063373835637355132068513997507200000000000000, --43
2658271574788448768043625811014615890320000000000000000, --44
119622220865480194561963161495657715064000000000000000000, --45
5502622159812088949850305428800254892944000000000000000000, --46
258623241511168180642964355153611979968400000000000000000000, --47
12413915592536072670862289047373375038480000000000000000000000, --48
608281864034267560872252163321295376886000000000000000000000000, --49
30414093201713378043612608166064768844300000000000000000000000000, --50
1551118753287382280224243016469303211060000000000000000000000000000, --51
80658175170943878571660636856403766975120000000000000000000000000000, --52
4274883284060025564298013753389399649681000000000000000000000000000000, --53
230843697339241380472092742683027581082800000000000000000000000000000000, --54
12696403353658275925965100847566516959550000000000000000000000000000000000, --55
710998587804863451854045647463724949735000000000000000000000000000000000000, --56
40526919504877216755680601905432322134900000000000000000000000000000000000000, --57
2350561331282878571829474910515074683820000000000000000000000000000000000000000, --58
138683118545689835737939019720389406345000000000000000000000000000000000000000000, --59
8320987112741390144276341183223364380700000000000000000000000000000000000000000000, --60
507580213877224798800856812176625227222700000000000000000000000000000000000000000000, --61
31469973260387937525653122354950764087810000000000000000000000000000000000000000000000, --62
1982608315404440064116146708361898137532000000000000000000000000000000000000000000000000, --63
126886932185884164103433389335161480802000000000000000000000000000000000000000000000000000, --64
8247650592082470666723170306785496252130000000000000000000000000000000000000000000000000000, --65
544344939077443064003729240247842752641000000000000000000000000000000000000000000000000000000, --66
36471110918188685288249859096605464426900000000000000000000000000000000000000000000000000000000, --67
2480035542436830599600990418569171581030000000000000000000000000000000000000000000000000000000000, --68
171122452428141311372468338881272839091000000000000000000000000000000000000000000000000000000000000, --69
1.197857166996989179607278372168909873640000000000000000000000000000000000000000000000000000000E+100, --70
8.504785885678623175211676442399260102844000000000000000000000000000000000000000000000000000000E+101, --71
6.123445837688608686152407038527467274048000000000000000000000000000000000000000000000000000000E+103, --72
4.470115461512684340891257138125051110055000000000000000000000000000000000000000000000000000000E+105, --73
3.307885441519386412259530282212537821441000000000000000000000000000000000000000000000000000000E+107, --74
2.480914081139539809194647711659403366081000000000000000000000000000000000000000000000000000000E+109, --75
1.885494701666050254987932260861146558222000000000000000000000000000000000000000000000000000000E+111, --76
1.451830920282858696340707840863082849831000000000000000000000000000000000000000000000000000000E+113, --77
1.132428117820629783145752115873204622868000000000000000000000000000000000000000000000000000000E+115, --78
8.946182130782975286851441715398316520660000000000000000000000000000000000000000000000000000000E+116, --79
7.156945704626380229481153372318653216530000000000000000000000000000000000000000000000000000000E+118, --80
5.797126020747367985879734231578109105390000000000000000000000000000000000000000000000000000000E+120, --81
4.753643337012841748421382069894049466420000000000000000000000000000000000000000000000000000000E+122, --82
3.945523969720658651189747118012061057130000000000000000000000000000000000000000000000000000000E+124 --83
);
procedure assert(condition boolean, message varchar2)
is
begin
if not condition or condition is null then
raise_application_error(-20001, 'Assertion error: '||message);
end if;
end assert;
-- n!
function fac(n pls_integer) return number
is
begin
assert(n between 0 and 83, '0 <= n <= 83');
return c_fac(n+1);
end fac;
-- n!
function permutations(n pls_integer) return number
is
begin
return fac(n);
end permutations;
-- n! / (k1!*k2!*...*km!), where sum(k) <= n
function permutations_with_rep(n pls_integer, k number_nt) return number
is
l_sum pls_integer := 0;
l_res pls_integer;
begin
l_res := fac(n);
for i in 1..k.count loop
l_sum := l_sum + k(i);
assert(l_sum <= n, 'sum(k) <= n');
l_res := l_res/fac(k(i));
end loop;
return l_res;
end permutations_with_rep;
-- n! / (n-k)!
function allocations(n pls_integer, k pls_integer) return number
is
begin
return fac(n)/fac(n-k);
end allocations;
-- n to the k'th power
function allocations_with_rep(n pls_integer, k pls_integer) return number
is
begin
return power(n, k);
end allocations_with_rep;
-- n! / ((n-k)! * k!)
function combinations(n pls_integer, k pls_integer) return number
is
begin
return fac(n)/fac(n-k)/fac(k);
end combinations;
-- (k+n-1)! / ((n-1)! * k!)
function combinations_with_rep(n pls_integer, k pls_integer) return number
is
begin
return fac(k+n-1)/fac(n-1)/fac(k);
end combinations_with_rep;
-- another name for combinations
function n_choose_k(n pls_integer, k pls_integer) return number
is
begin
return combinations(n,k);
end n_choose_k;
end comics;
/
Я добавил проверку входных значений для функций пакета при помощи процедуры assert. Вот что будет, если ввести недопустимые значения:
SQL> select comics.fac(100) from dual;
ORA-20001: Assertion error: 0 <= n <= 83
ORA-06512: at "AY.ASSERT", line 5
ORA-06512: at "AY.COMICS", line 106
SQL> select comics.permutations_with_rep(5, number_nt(2,3,1)) from dual;
ORA-20001: Assertion error: sum(k) <= n
ORA-06512: at "AY.ASSERT", line 5
ORA-06512: at "AY.COMICS", line 126
Решим несколько задачек с помощью пакета comics.
Сколькими способами можно расставить слова в предложении "Белеет парус одинокий"?
SQL> select comics.permutations(3) from dual;
COMICS.PERMUTATIONS(3)
----------------------
6
Сколько разных чисел можно получить перестановкой цифр в числе 123234?
SQL> select comics.permutations_with_rep(6, number_nt(1,2,2,1)) from dual;
COMICS.PERMUTATIONS_WITH_REP(6
------------------------------
180
Сколько разных последовательностей из 5 карт можно вытащить из колоды в 52 карты, вынимая карты и не возвращая их в колоду?
SQL> select comics.allocations(52, 5) from dual;
COMICS.ALLOCATIONS(52,5)
------------------------
311875200
Сколько разных чисел можно записать, имея в своем распоряжении 5 десятичных разрядов? Иными словами, сколько существует разных десятичных чисел с разрядностью не больше пяти?
SQL> select comics.allocations_with_rep(10, 5) from dual;
COMICS.ALLOCATIONS_WITH_REP(10
------------------------------
100000
Сколько сочетаний по 7 можно получить из 49 элементов? (Это "Спортлото" 7 из 49-ти.)
SQL> select comics.combinations(49, 7) from dual;
COMICS.COMBINATIONS(49,7)
-------------------------
85900584
Сколькими способами можно составить букет из 5 роз, если у нас есть розы трех цветов?
SQL> select comics.combinations_with_rep(3, 5) from dual;
COMICS.COMBINATIONS_WITH_REP(3
------------------------------
21
В заключение, удаляю результаты экспериментов (но оставляю пакет comics):
SQL> drop function fac1;
Function dropped
SQL> drop function fac2;
Function dropped
SQL> drop function fac3;
Function dropped
Комментариев нет:
Отправить комментарий