Previous: Введение в работу с множествами, Up: Множества [Contents][Index]
Возвращает объединение множества a с {x}.
Функция adjoin вызывает ошибку, если a не является множеством.
Вызовы adjoin(x, a) и union(set(x), a)
эквивалентны, однако adjoin может быть несколько быстрее, чем union.
См. также disjoin.
Примеры:
(%i1) adjoin (c, {a, b});
(%o1) {a, b, c}
(%i2) adjoin (a, {a, b});
(%o2) {a, b}
Представляет n-ое число Белла.
belln(n) есть число разбиений множества с n элементами.
Для неотрицательного целого n,
belln(n) упрощается в n-ое число Белла.
Для других значений аргумента belln не упрощается.
Функция belln дистрибутивна по отношению к уравнениям, спискам, матрицам и множествам.
Примеры:
Функция belln, примененная к неотрицательным целым числам.
(%i1) makelist (belln (i), i, 0, 6);
(%o1) [1, 1, 2, 5, 15, 52, 203]
(%i2) is (cardinality (set_partitions ({})) = belln (0));
(%o2) true
(%i3) is (cardinality (set_partitions ({1, 2, 3, 4, 5, 6})) =
belln (6));
(%o3) true
Функция belln, примененная к аргументам, не являющимися неотрицательными
целыми числами.
(%i1) [belln (x), belln (sqrt(3)), belln (-9)]; (%o1) [belln(x), belln(sqrt(3)), belln(- 9)]
Возвращает число различных элементов множества a.
Функция cardinality игнорирует повторяющиеся элементы даже если упрощение
отключено.
Примеры:
(%i1) cardinality ({});
(%o1) 0
(%i2) cardinality ({a, a, b, c});
(%o2) 3
(%i3) simp : false;
(%o3) false
(%i4) cardinality ({a, a, b, c});
(%o4) 3
Возвращает множество списков формы [x_1, ..., x_n], где
x_1, ..., x_n есть элементы множеств b_1, ... , b_n соответственно.
Функция cartesian_product вызывает ошибку, если хотя бы один из ее аргументов
не является множеством.
Примеры:
(%i1) cartesian_product ({0, 1});
(%o1) {[0], [1]}
(%i2) cartesian_product ({0, 1}, {0, 1});
(%o2) {[0, 0], [0, 1], [1, 0], [1, 1]}
(%i3) cartesian_product ({x}, {y}, {z});
(%o3) {[x, y, z]}
(%i4) cartesian_product ({x}, {-1, 0, 1});
(%o4) {[x, - 1], [x, 0], [x, 1]}
Возвращает множество a без элемента x. Если x не является элементом a, то a возвращается неизменным.
Функция disjoin вызывает ошибку, если a не является множеством.
disjoin(x, a), delete(x, a) и
setdifference(a, set(x)) эквивалентны.
Из этих вариантов disjoin обычно быстрее других.
Примеры:
(%i1) disjoin (a, {a, b, c, d});
(%o1) {b, c, d}
(%i2) disjoin (a + b, {5, z, a + b, %pi});
(%o2) {5, %pi, z}
(%i3) disjoin (a - b, {5, z, a + b, %pi});
(%o3) {5, %pi, b + a, z}
Возвращает true тогда и только тогда, когда множества a и b не пересекаются.
Функция disjointp вызывает ошибку, если a или b не являются множествами.
Примеры:
(%i1) disjointp ({a, b, c}, {1, 2, 3});
(%o1) true
(%i2) disjointp ({a, b, 3}, {1, 2, 3});
(%o2) false
Представляет множество делителей n.
Функция divisors(n) упрощается до множества целых чисел, при этом
n является ненулевым целым числом.
Множество делителей включает 1 и n.
Делители отрицательного числа совпадают с таковыми для его абсолютного значения.
Функция divisors дистрибутивна по отношению к уравнениям, спискам, матрицам и множествам.
Примеры:
Мы можем проверить, что число 28 является совершенным, т.е. сумма делителей, за исключением самого числа, равна 28.
(%i1) s: divisors(28);
(%o1) {1, 2, 4, 7, 14, 28}
(%i2) lreduce ("+", args(s)) - 28;
(%o2) 28
Функция divisors является упрощающей.
Подстановка 8 для a в divisors(a)
дает делители без перевычисления divisors(8).
(%i1) divisors (a);
(%o1) divisors(a)
(%i2) subst (8, a, %);
(%o2) {1, 2, 4, 8}
Функция divisors дистрибутивна по отношению к уравнениям, спискам, матрицам и множествам.
(%i1) divisors (a = b);
(%o1) divisors(a) = divisors(b)
(%i2) divisors ([a, b, c]);
(%o2) [divisors(a), divisors(b), divisors(c)]
(%i3) divisors (matrix ([a, b], [c, d]));
[ divisors(a) divisors(b) ]
(%o3) [ ]
[ divisors(c) divisors(d) ]
(%i4) divisors ({a, b, c});
(%o4) {divisors(a), divisors(b), divisors(c)}
Возвращает true тогда и только тогда, когда x является элементом множества a.
Функция elementp вызывает ошибку, если a не является множеством.
Примеры:
(%i1) elementp (sin(1), {sin(1), sin(2), sin(3)});
(%o1) true
(%i2) elementp (sin(1), {cos(1), cos(2), cos(3)});
(%o2) false
Возвращает true тогда и только тогда, когда a есть пустое множество или список.
Примеры:
(%i1) map (emptyp, [{}, []]);
(%o1) [true, true]
(%i2) map (emptyp, [a + b, {{}}, %pi]);
(%o2) [false, false, false]
Возвращает множество классов эквивалентности множества s по отношению эквивалентности F.
F – есть функция двух переменных, определенная на Декартовом произведении s на s.
Возвращаемое F значение есть true или false,
либо выражение expr такое, что is(expr) дает true или false.
Если F не является отношением эквивалентности, то equiv_classes
применит его без возражения, но результат будет скорее всего неправильным.
Примеры:
Отношение эквивалентности является лямбда-выражением, возвращающим true или false.
(%i1) equiv_classes ({1, 1.0, 2, 2.0, 3, 3.0},
lambda ([x, y], is (equal (x, y))));
(%o1) {{1, 1.0}, {2, 2.0}, {3, 3.0}}
Отношение эквивалентности есть имя реляционной функции is, дающей true или false.
(%i1) equiv_classes ({1, 1.0, 2, 2.0, 3, 3.0}, equal);
(%o1) {{1, 1.0}, {2, 2.0}, {3, 3.0}}
Классы эквивалентности – числа отличающиеся на несколько чисел 3.
(%i1) equiv_classes ({1, 2, 3, 4, 5, 6, 7},
lambda ([x, y], remainder (x - y, 3) = 0));
(%o1) {{1, 4, 7}, {2, 5}, {3, 6}}
Возвращает true, если предикат f дает true для всех аргументов.
Если второй аргумент является множеством, то
every(f, s) возвращает true,
если is(f(a_i)) возвращает true для всех a_i в s.
every может вычислять f для всех a_i в s, а может и не для всех.
Т.к. множества не упорядочены, то every может вычислять f(a_i)
в произвольном порядке.
Примененная к одному или нескольким спискам,
every(f, L_1, ..., L_n) возвращает true,
если is(f(x_1, ..., x_n)) возвращает true
для всех x_1, ..., x_n в L_1, ..., L_n соответственно.
every может вычислять f для всех комбинаций x_1, ..., x_n, а может и не для всех.
every вычисляет списки в порядке возрастания индекса.
Для пустого множества {} и пустого списка [] every возвращает false.
Если глобальный флаг maperror равен true, то все списки
L_1, ..., L_n должны иметь одинаковую длину.
Если maperror равен false, то списки обрезаются до длины
самого короткого.
Значение предиката f, который вычисляется посредством is
в значение, отличное от true или false,
управляется глобальным флагом prederror.
Если prederror равен true, то данные
значения рассматриваются как false, и возвращаемое
every значение есть false.
Если prederror равен false, то такие значения
рассматриваются как unknown, и возвращаемое
every значение равно unknown.
Примеры:
every, примененная к одному списку.
Предикат является функцией одного аргумента.
(%i1) every (integerp, {1, 2, 3, 4, 5, 6});
(%o1) true
(%i2) every (atom, {1, 2, sin(3), 4, 5 + y, 6});
(%o2) false
every, примененная к двум спискам.
Предикат – функция двух аргументов.
(%i1) every ("=", [a, b, c], [a, b, c]);
(%o1) true
(%i2) every ("#", [a, b, c], [a, b, c]);
(%o2) false
Значение предиката f, вычисляемого в значение,
отличное от true или false,
управляется глобальным флагом prederror.
(%i1) prederror : false;
(%o1) false
(%i2) map (lambda ([a, b], is (a < b)), [x, y, z],
[x^2, y^2, z^2]);
(%o2) [unknown, unknown, unknown]
(%i3) every ("<", [x, y, z], [x^2, y^2, z^2]);
(%o3) unknown
(%i4) prederror : true;
(%o4) true
(%i5) every ("<", [x, y, z], [x^2, y^2, z^2]);
(%o5) false
Возвращает подмножество s, на котором функция f принимает минимальное или максимальное значение.
extremal_subset(s, f, max) возвращает подмножество множества или списка
s, для которого вещественнозначная функция f принимает максимальное значение.
extremal_subset(s, f, min) возвращает подмножество множества или списка
s, для которого вещественнозначная функция f принимает минимальное значение.
Примеры:
(%i1) extremal_subset ({-2, -1, 0, 1, 2}, abs, max);
(%o1) {- 2, 2}
(%i2) extremal_subset ({sqrt(2), 1.57, %pi/2}, sin, min);
(%o2) {sqrt(2)}
Собирает аргументы подвыражений, имеющих оператор верхнего уровня такой же как у expr, и строит выражение из этих собранных аргументов.
Аргументы, имеющие оператор верхнего уровня отличный от главного оператора expr,
копируются без модификации даже если они, в свою очередь, имеют некоторые подвыражения
с главным оператором expr.
Возможно, что flatten построит выражение с числом аргументов
недопустимым для данного типа оператора, что может привести к ошибке
упрощателя или вычислителя.
Функция flatten не пытается определить подобные ситуации.
Выражения, имеющие специальные представления, например, канонические рациональные выражения (КРВ),
не обрабатываются flatten. В этом случае flatten возвращает аргумент
без изменения.
Примеры:
Примененная к списку, flatten собирает все элементы, являющиеся списками.
(%i1) flatten ([a, b, [c, [d, e], f], [[g, h]], i, j]); (%o1) [a, b, c, d, e, f, g, h, i, j]
Примененная к множеству, flatten собирает все элементы, являющиеся множествами.
(%i1) flatten ({a, {b}, {{c}}});
(%o1) {a, b, c}
(%i2) flatten ({a, {[a], {a}}});
(%o2) {a, [a]}
Функция flatten похожа на объявление оператора n-арным.
Однако flatten не влияет на подвыражения, имеющие оператор, отличный от
главного оператора выражения, тогда как декларация оператора n-арным действует на них.
(%i1) expr: flatten (f (g (f (f (x))))); (%o1) f(g(f(f(x)))) (%i2) declare (f, nary); (%o2) done (%i3) ev (expr); (%o3) f(g(f(x)))
flatten трактует функции с индексом также как любые другие операторы.
(%i1) flatten (f[5] (f[5] (x, y), z));
(%o1) f (x, y, z)
5
Функция flatten может составить выражение, в котором число аргументов
отличается от объявленного числа аргументов оператора.
(%i1) 'mod (5, 'mod (7, 4)); (%o1) mod(5, mod(7, 4)) (%i2) flatten (%); (%o2) mod(5, 7, 4) (%i3) ''%, nouns; Wrong number of arguments to mod -- an error. Quitting. To debug this try debugmode(true);
Заменяет в a все множества на списки и возвращает результат.
full_listify заменяет операторы множества на операторы списка во вложенных подвыражениях,
даже если главный оператор не есть set.
Функция listify заменяет только главный оператор.
Примеры:
(%i1) full_listify ({a, b, {c, {d, e, f}, g}});
(%o1) [a, b, [c, [d, e, f], g]]
(%i2) full_listify (F (G ({a, b, H({c, d, e})})));
(%o2) F(G([a, b, H([c, d, e])]))
Если a является списком, то fullsetify заменяет оператор списка на оператор множества и
применяет fullsetify ко всем членам этого множества.
Если аргумент a не является списком, то он возвращается неизменным.
Функция setify заменяет только главный оператор.
Примеры:
В строке (%o2) аргумент f не преобразован в множество, т.к.
главный оператор не является списком f([b]).
(%i1) fullsetify ([a, [a]]);
(%o1) {a, {a}}
(%i2) fullsetify ([a, f([b])]);
(%o2) {a, f([b])}
Возвращает x для любого аргумента x.
Примеры:
Функция identity может использоваться как предикат, если параметры уже
являются логическими значениями.
(%i1) every (identity, [true, true]); (%o1) true
Возвращает целочисленные разбиения n, т.е. списки целых чисел, сумма которых равна n.
Функция integer_partitions(n) возвращает множество
всех разбиений n.
Каждое разбиение есть список, отсортированный от большего значения к меньшему.
Вызов integer_partitions(n, len)
возвращает все разбиения длины len или менее.
В этом случае к разбиениям, имеющим число членов меньшее, чем len,
добавляются нули, чтобы сделать все возвращаемые разбиения одинаковой
длины len.
Список [a_1, ..., a_m] есть разбиение неотрицательного целого числа n, если (1) каждое a_i есть ненулевое положительное число и (2) a_1 + ... + a_m = n. Таким образом, 0 не имеет разбиений.
Примеры:
(%i1) integer_partitions (3);
(%o1) {[1, 1, 1], [2, 1], [3]}
(%i2) s: integer_partitions (25)$
(%i3) cardinality (s);
(%o3) 1958
(%i4) map (lambda ([x], apply ("+", x)), s);
(%o4) {25}
(%i5) integer_partitions (5, 3);
(%o5) {[2, 2, 1], [3, 1, 1], [3, 2, 0], [4, 1, 0], [5, 0, 0]}
(%i6) integer_partitions (5, 2);
(%o6) {[3, 2], [4, 1], [5, 0]}
Для того, чтобы найти все разбиения, удовлетворяющие определенному условию, можно использовать функцию subset.
В следующем примере находятся все разбиения 10, состоящие из простых чисел.
(%i1) s: integer_partitions (10)$
(%i2) cardinality (s);
(%o2) 42
(%i3) xprimep(x) := integerp(x) and (x > 1) and primep(x)$
(%i4) subset (s, lambda ([x], every (xprimep, x)));
(%o4) {[2, 2, 2, 2, 2], [3, 3, 2, 2], [5, 3, 2], [5, 5], [7, 3]}
Функция intersect идентична intersection.
Возвращает множество, содержащие элементы, общие для всех множеств a_1, ..., a_n.
Функция intersection вызывает ошибку, если хотя бы один из аргументов не является множеством.
Примеры:
(%i1) S_1 : {a, b, c, d};
(%o1) {a, b, c, d}
(%i2) S_2 : {d, e, f, g};
(%o2) {d, e, f, g}
(%i3) S_3 : {c, d, e, f};
(%o3) {c, d, e, f}
(%i4) S_4 : {u, v, w};
(%o4) {u, v, w}
(%i5) intersection (S_1, S_2);
(%o5) {d}
(%i6) intersection (S_2, S_3);
(%o6) {d, e, f}
(%i7) intersection (S_1, S_2, S_3);
(%o7) {d}
(%i8) intersection (S_1, S_2, S_3, S_4);
(%o8) {}
Дельта-функция Кронекера.
kron_delta упрощается в 1, если x и y идентичны или очевидно эквивалентны,
и упрощается в 0, если x и y очевидно не эквивалентны.
Иначе, если эквивалентность или неэквивалентность x и y не ясна,
то kron_delta упрощается в невычисляемую форму (noun).
По отношению к числам с плавающей точкой kron_delta реализует осторожный подход.
Если разница x - y является числом с плавающей точкой, то
kron_delta упрощается в невычисляемую форму, даже когда x по-видимому эквивалентно y.
Функция
kron_delta(x, y) упрощается в 1,
если is(x = y) равно true.
kron_delta тоже упрощается в 1,
если sign(abs(x - y)) есть zero
и x - y не является числом с плавающей точкой
(ни обычное число с плавающей точкой, ни число с плавающей точкой повышенной точности).
kron_delta упрощается в 0, если sign(abs(x - y)) равно pos.
Если же sign(abs(x - y)) дает
что-то отличное от pos или zero,
или zero но x - y
есть число с плавающей точкой,
то kron_delta возвращает невычисляемое выражение.
Функция kron_delta объявлена симметричной.
Т.е.
kron_delta(x, y) равно kron_delta(y, x).
Примеры:
Аргументы kron_delta идентичны.
kron_delta упрощается в 1.
(%i1) kron_delta (a, a); (%o1) 1 (%i2) kron_delta (x^2 - y^2, x^2 - y^2); (%o2) 1 (%i3) float (kron_delta (1/10, 0.1)); (%o3) 1
Аргументы kron_delta эквивалентны, и их
разница не есть число с плавающей точкой.
kron_delta упрощается в 1.
(%i1) assume (equal (x, y)); (%o1) [equal(x, y)] (%i2) kron_delta (x, y); (%o2) 1
Аргументы kron_delta не эквивалентны.
kron_delta упрощается в 0.
(%i1) kron_delta (a + 1, a); (%o1) 0 (%i2) assume (a > b)$ (%i3) kron_delta (a, b); (%o3) 0 (%i4) kron_delta (1/5, 0.7); (%o4) 0
Аргументы kron_delta могут быть, а могут и не быть эквивалентны.
kron_delta упрощается в невычисляемое выражение.
(%i1) kron_delta (a, b); (%o1) kron_delta(a, b) (%i2) assume(x >= y)$ (%i3) kron_delta (x, y); (%o3) kron_delta(x, y)
Аргументы kron_delta эквивалентны, но их разница
является числом с плавающей точкой.
kron_delta упрощается в невычисляемое выражение.
(%i1) 1/4 - 0.25;
(%o1) 0.0
(%i2) 1/10 - 0.1;
(%o2) 0.0
(%i3) 0.25 - 0.25b0;
Warning: Float to bigfloat conversion of 0.25
(%o3) 0.0b0
(%i4) kron_delta (1/4, 0.25);
1
(%o4) kron_delta(-, 0.25)
4
(%i5) kron_delta (1/10, 0.1);
1
(%o5) kron_delta(--, 0.1)
10
(%i6) kron_delta (0.25, 0.25b0);
Warning: Float to bigfloat conversion of 0.25
(%o6) kron_delta(0.25, 2.5b-1)
Функция kron_delta симметрична.
(%i1) kron_delta (x, y); (%o1) kron_delta(x, y) (%i2) kron_delta (y, x); (%o2) kron_delta(x, y) (%i3) kron_delta (x, y) - kron_delta (y, x); (%o3) 0 (%i4) is (equal (kron_delta (x, y), kron_delta (y, x))); (%o4) true (%i5) is (kron_delta (x, y) = kron_delta (y, x)); (%o5) true
Возвращает список с элементами a, если a есть множество.
В противном случае listify возвращает a.
Функция full_listify заменяет все операторы множества в a на операторы списка.
Примеры:
(%i1) listify ({a, b, c, d});
(%o1) [a, b, c, d]
(%i2) listify (F ({a, b, c, d}));
(%o2) F({a, b, c, d})
Расширяет бинарную функцию F до n-арной методом композиции. Аргумент s является списком.
lreduce(F, s) возвращает F(... F(F(s_1, s_2), s_3), ... s_n).
Если присутствует необязательный аргумент s_0, то
результат эквивалентен lreduce(F, cons(s_0, s)).
Функция F сначала применяется к левой паре элементов списка, откуда происходит название "lreduce" (left reduce).
См. также rreduce, xreduce и tree_reduce.
Примеры:
lreduce без необязательного аргумента.
(%i1) lreduce (f, [1, 2, 3]); (%o1) f(f(1, 2), 3) (%i2) lreduce (f, [1, 2, 3, 4]); (%o2) f(f(f(1, 2), 3), 4)
lreduce с необязательным аргументом.
(%i1) lreduce (f, [1, 2, 3], 4); (%o1) f(f(f(4, 1), 2), 3)
lreduce примененная к встроенным бинарным операторам.
/ – есть оператор деления.
(%i1) lreduce ("^", args ({a, b, c, d}));
b c d
(%o1) ((a ) )
(%i2) lreduce ("/", args ({a, b, c, d}));
a
(%o2) -----
b c d
Возвращает множество с элементами, сгенерированными из выражения expr, где x есть список переменных expr, а s есть множество или список списков. Для определения элемента результирующего списка выражение expr вычисляется при переменных x, равным значениям из s (параллельное присваивание).
Каждый член s должен иметь ту же длину, что и x. Список переменных x должен быть списком символов без индексов. Даже если символ только один, то x должен быть одноэлементным списком, а каждый член s должен быть одноэлементным списком.
См. также makelist.
Примеры:
(%i1) makeset (i/j, [i, j], [[1, a], [2, b], [3, c], [4, d]]);
1 2 3 4
(%o1) {-, -, -, -}
a b c d
(%i2) S : {x, y, z}$
(%i3) S3 : cartesian_product (S, S, S);
(%o3) {[x, x, x], [x, x, y], [x, x, z], [x, y, x], [x, y, y],
[x, y, z], [x, z, x], [x, z, y], [x, z, z], [y, x, x],
[y, x, y], [y, x, z], [y, y, x], [y, y, y], [y, y, z],
[y, z, x], [y, z, y], [y, z, z], [z, x, x], [z, x, y],
[z, x, z], [z, y, x], [z, y, y], [z, y, z], [z, z, x],
[z, z, y], [z, z, z]}
(%i4) makeset (i + j + k, [i, j, k], S3);
(%o4) {3 x, 3 y, y + 2 x, 2 y + x, 3 z, z + 2 x, z + y + x,
z + 2 y, 2 z + x, 2 z + y}
(%i5) makeset (sin(x), [x], {[1], [2], [3]});
(%o5) {sin(1), sin(2), sin(3)}
Представляет функцию Мебиуса.
Если n есть произведение k различных простых чисел, то
moebius(n) упрощается до (-1)^k.
Если n = 1, то функция упрощается в 1.
Для всех остальных положительных целых функция упрощается в 0.
Функция moebius дистрибутивна по отношению к уравнениям, спискам, матрицам и множествам.
Примеры:
(%i1) moebius (1);
(%o1) 1
(%i2) moebius (2 * 3 * 5);
(%o2) - 1
(%i3) moebius (11 * 17 * 29 * 31);
(%o3) 1
(%i4) moebius (2^32);
(%o4) 0
(%i5) moebius (n);
(%o5) moebius(n)
(%i6) moebius (n = 12);
(%o6) moebius(n) = 0
(%i7) moebius ([11, 11 * 13, 11 * 13 * 15]);
(%o7) [- 1, 1, 1]
(%i8) moebius (matrix ([11, 12], [13, 14]));
[ - 1 0 ]
(%o8) [ ]
[ - 1 1 ]
(%i9) moebius ({21, 22, 23, 24});
(%o9) {- 1, 0, 1}
Возвращает мультиномиальный коэффициент.
Если каждое a_k есть неотрицательное целое число, то мультиномиальный коэффициент
дает число способов положить a_1 + ... + a_n различных объектов
в n ящиков с a_k элементами в k-ом ящике.
В целом, multinomial_coeff (a_1, ..., a_n)
равна (a_1 + ... + a_n)!/(a_1! ... a_n!).
multinomial_coeff() (без аргументов) дает 1.
minfactorial может упрощать значения, возвращаемые multinomial_coeff.
Примеры:
(%i1) multinomial_coeff (1, 2, x);
(x + 3)!
(%o1) --------
2 x!
(%i2) minfactorial (%);
(x + 1) (x + 2) (x + 3)
(%o2) -----------------------
2
(%i3) multinomial_coeff (-6, 2);
(- 4)!
(%o3) --------
2 (- 6)!
(%i4) minfactorial (%);
(%o4) 10
Возвращает число целочисленных разбиений с различными частями для n, если n – неотрицательное целое.
Иначе num_distinct_partitions возвращает невычисляемую форму.
num_distinct_partitions(n, list) возвращает список чисел
целочисленных разбиений с различными частями для 1, 2, 3, ..., n .
Разбиение числа n с различными частями есть список различных положительных целых k_1, ..., k_m, таких что n = k_1 + ... + k_m.
Примеры:
(%i1) num_distinct_partitions (12); (%o1) 15 (%i2) num_distinct_partitions (12, list); (%o2) [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15] (%i3) num_distinct_partitions (n); (%o3) num_distinct_partitions(n)
Возвращает число целочисленных разбиений числа n,
если n – неотрицательное целое.
Иначе num_partitions возвращает невычисляемую форму.
num_partitions(n, list) возвращает список чисел
целочисленных разбиений для 1, 2, 3, ..., n.
Для неотрицательного целого n, num_partitions(n) равна
cardinality(integer_partitions(n)).
На самом деле num_partitions не строит полное множество разбиений
и поэтому работает значительно быстрее.
Примеры:
(%i1) num_partitions (5) = cardinality (integer_partitions (5)); (%o1) 7 = 7 (%i2) num_partitions (8, list); (%o2) [1, 1, 2, 3, 5, 7, 11, 15, 22] (%i3) num_partitions (n); (%o3) num_partitions(n)
Разбивает множество a в соответствии с предикатом f.
Функция partition_set возвращает список двух множеств.
Первое множество состоит из элементов a, для которых f равен false,
а второе включает все остальные элементы a.
Функция partition_set не применяет is к возвращаемым f значениям.
partition_set вызывает ошибку, если a не является множеством.
См. также subset.
Примеры:
(%i1) partition_set ({2, 7, 1, 8, 2, 8}, evenp);
(%o1) [{1, 7}, {2, 8}]
(%i2) partition_set ({x, rat(y), rat(y) + z, 1},
lambda ([x], ratp(x)));
(%o2)/R/ [{1, x}, {y, y + z}]
Возвращает множество различных перестановок членов списка или множества a. Каждая перестановка является списком.
Если a является списком, то повторные члены a включаются в перестановки.
permutations вызывает ошибку, если a не является списком или множеством.
См. также random_permutation.
Примеры:
(%i1) permutations ([a, a]);
(%o1) {[a, a]}
(%i2) permutations ([a, a, b]);
(%o2) {[a, a, b], [a, b, a], [b, a, a]}
Возвращает множество всех подмножеств a или подмножество этого множества подмножеств.
powerset(a) возвращает множество всех подмножеств множества a.
powerset(a) имеет 2^cardinality(a) членов.
powerset(a, n) возвращает множество подмножеств a, которые имеют
мощность n.
powerset вызывает ошибку, если a не является множеством или n
не есть целое число.
Примеры:
(%i1) powerset ({a, b, c});
(%o1) {{}, {a}, {a, b}, {a, b, c}, {a, c}, {b}, {b, c}, {c}}
(%i2) powerset ({w, x, y, z}, 4);
(%o2) {{w, x, y, z}}
(%i3) powerset ({w, x, y, z}, 3);
(%o3) {{w, x, y}, {w, x, z}, {w, y, z}, {x, y, z}}
(%i4) powerset ({w, x, y, z}, 2);
(%o4) {{w, x}, {w, y}, {w, z}, {x, y}, {x, z}, {y, z}}
(%i5) powerset ({w, x, y, z}, 1);
(%o5) {{w}, {x}, {y}, {z}}
(%i6) powerset ({w, x, y, z}, 0);
(%o6) {{}}
Возвращает случайную перестановку множества или списка a, построенную при помощи алгоритма тасования Кнута.
Возвращаемое значение есть новый список, который отличен от исходного аргумента даже если все элементы совпадают. Однако элементы списка не копируются.
Примеры:
(%i1) random_permutation ([a, b, c, 1, 2, 3]);
(%o1) [c, 1, 2, 3, a, b]
(%i2) random_permutation ([a, b, c, 1, 2, 3]);
(%o2) [b, 3, 1, c, a, 2]
(%i3) random_permutation ({x + 1, y + 2, z + 3});
(%o3) [y + 2, z + 3, x + 1]
(%i4) random_permutation ({x + 1, y + 2, z + 3});
(%o4) [x + 1, y + 2, z + 3]
Расширяет бинарную функцию F до n-арной методом композиции. Аргумент s является списком.
rreduce(F, s) возвращает F(s_1, ... F(s_{n - 2}, F(s_{n - 1}, s_n))).
Если присутствует необязательный аргумент s_{n + 1}, то
результат эквивалентен rreduce(F, endcons(s_{n + 1}, s)).
Функция F сначала применяется к правой паре элементов списка, откуда происходит название "rreduce" (right reduce).
См. также lreduce, tree_reduce и xreduce.
Примеры:
rreduce без необязательного аргумента.
(%i1) rreduce (f, [1, 2, 3]); (%o1) f(1, f(2, 3)) (%i2) rreduce (f, [1, 2, 3, 4]); (%o2) f(1, f(2, f(3, 4)))
rreduce с необязательным аргументом.
(%i1) rreduce (f, [1, 2, 3], 4); (%o1) f(1, f(2, f(3, 4)))
rreduce примененный к встроенным операторам.
/ – есть оператор деления.
(%i1) rreduce ("^", args ({a, b, c, d}));
d
c
b
(%o1) a
(%i2) rreduce ("/", args ({a, b, c, d}));
a c
(%o2) ---
b d
Возвращает множество, содержащее элементы множества a, которые отсутствуют в множестве b.
setdifference вызывает ошибку, если a или b не являются множествами.
Примеры:
(%i1) S_1 : {a, b, c, x, y, z};
(%o1) {a, b, c, x, y, z}
(%i2) S_2 : {aa, bb, c, x, y, zz};
(%o2) {aa, bb, c, x, y, zz}
(%i3) setdifference (S_1, S_2);
(%o3) {a, b, z}
(%i4) setdifference (S_2, S_1);
(%o4) {aa, bb, zz}
(%i5) setdifference (S_1, S_1);
(%o5) {}
(%i6) setdifference (S_1, {});
(%o6) {a, b, c, x, y, z}
(%i7) setdifference ({}, S_1);
(%o7) {}
Возвращает true если a и b имеют одинаковое количество элементов,
и is(x = y) равно true
для x из a и y из b,
в порядке, определяемом listify.
Иначе setequalp возвращает false.
Примеры:
(%i1) setequalp ({1, 2, 3}, {1, 2, 3});
(%o1) true
(%i2) setequalp ({a, b, c}, {1, 2, 3});
(%o2) false
(%i3) setequalp ({x^2 - y^2}, {(x + y) * (x - y)});
(%o3) false
Составляет множество из элементов списка a. Повторяющиеся элементы списка a
удаляются, а элементы результирующего множества сортируются в соответствии с предикатом
orderlessp.
setify вызывает ошибку, если a не является списком.
Примеры:
(%i1) setify ([1, 2, 3, a, b, c]);
(%o1) {1, 2, 3, a, b, c}
(%i2) setify ([a, b, c, a, b, c]);
(%o2) {a, b, c}
(%i3) setify ([7, 13, 11, 1, 3, 9, 5]);
(%o3) {1, 3, 5, 7, 9, 11, 13}
Возвращает true тогда и только тогда, когда a является Maxima множеством.
setp возвращает true как для неупрощенных множеств (т.е. содержащих излишние элементы),
так и для упрощенных множеств.
setp is equivalent to the Maxima function
setp(a) := not atom(a) and op(a) = 'set.
Примеры:
(%i1) simp : false;
(%o1) false
(%i2) {a, a, a};
(%o2) {a, a, a}
(%i3) setp (%);
(%o3) true
Возвращает множество разбиений a или подмножество этого множества.
set_partitions(a, n) возвращает множество всех разбиений a в
n непустых непересекающихся подмножеств.
set_partitions(a) возвращает множество всех разбиений.
stirling2 возвращает мощность множества всех разбиений множества.
Множество множеств P есть разбиение множества S, если
Примеры:
Пустое множество есть разбиение самого себя, т.к. условия 1 и 2 очевидно выполняются.
(%i1) set_partitions ({});
(%o1) {{}}
Мощность множества разбиений может быть определена при помощи stirling2.
(%i1) s: {0, 1, 2, 3, 4, 5}$
(%i2) p: set_partitions (s, 3)$
(%i3) cardinality(p) = stirling2 (6, 3);
(%o3) 90 = 90
Каждый элемент p должен иметь n = 3 члена. Проверим:
(%i1) s: {0, 1, 2, 3, 4, 5}$
(%i2) p: set_partitions (s, 3)$
(%i3) map (cardinality, p);
(%o3) {3}
Наконец, для каждого члена p объединение всех членов должно совпадать с s.
Проверим:
(%i1) s: {0, 1, 2, 3, 4, 5}$
(%i2) p: set_partitions (s, 3)$
(%i3) map (lambda ([x], apply (union, listify (x))), p);
(%o3) {{0, 1, 2, 3, 4, 5}}
Возвращает true, если предикат f дает true для одного или более
аргументов.
Если второй параметр является множеством, то
some(f, s) возвращает true,
если is(f(a_i)) дает true для одного или более a_i из s.
some может вычислять f для всех или не для всех a_i из s.
Т.к. множества не упорядочены, то
some может вычислять f(a_i) в любом порядке.
Если аргументы являются одним или несколькими списками, то
some(f, L_1, ..., L_n) возвращает true,
если is(f(x_1, ..., x_n)) дает true
для одного или более x_1, ..., x_n из L_1, ..., L_n соответственно.
some может вычислять, а может и не вычислять f
для некоторых комбинаций x_1, ..., x_n.
some вычисляет списки в порядке возрастания индекса.
Для пустого множества {} или списка []
some возвращает false.
Если глобальный флаг maperror равен true, то все списки
L_1, ..., L_n должны иметь одинаковую длину.
Если maperror равен false, то списки обрезаются
до длины самого короткого.
Значения предиката f (вычисляемое посредством is)
отличное от true или false
управляется глобальным флагом prederror.
Если prederror равен true, то
такие значения трактуются как false.
Если prederror равен false, то
такие значения трактуются как unknown.
Примеры:
Функция some, примененная к одному множеству.
Предикат есть функция одного аргумента.
(%i1) some (integerp, {1, 2, 3, 4, 5, 6});
(%o1) true
(%i2) some (atom, {1, 2, sin(3), 4, 5 + y, 6});
(%o2) true
Функция some, примененная к спискам.
Предикат есть функция двух аргументов.
(%i1) some ("=", [a, b, c], [a, b, c]);
(%o1) true
(%i2) some ("#", [a, b, c], [a, b, c]);
(%o2) false
Значение предиката f, отличное от true или false,
управляется глобальным флагом prederror.
(%i1) prederror : false;
(%o1) false
(%i2) map (lambda ([a, b], is (a < b)), [x, y, z],
[x^2, y^2, z^2]);
(%o2) [unknown, unknown, unknown]
(%i3) some ("<", [x, y, z], [x^2, y^2, z^2]);
(%o3) unknown
(%i4) some ("<", [x, y, z], [x^2, y^2, z + 1]);
(%o4) true
(%i5) prederror : true;
(%o5) true
(%i6) some ("<", [x, y, z], [x^2, y^2, z^2]);
(%o6) false
(%i7) some ("<", [x, y, z], [x^2, y^2, z + 1]);
(%o7) true
Представляет число Стирлинга первого рода.
Для неотрицательных целых n и m величина
stirling1 (n, m) есть число перестановок множества из
n элементов, имеющих m циклов.
См. книгу Graham, Knuth и Patashnik Concrete Mathematics по поводу деталей.
Для определения stirling1 (n, m) с m,
меньшим нуля, Maxima использует рекуррентное соотношение.
Для n меньших нуля и нецелых аргументов функция не определена.
stirling1 является упрощающей функцией.
Maxima знает следующие тождества.
Эти тождества применяются, если аргументы являются целыми или символами, которые объявлены
целыми, и первый аргумент неотрицателен.
Функция stirling1 не упрощается для нецелых аргументов.
Ссылки:
[1] Donald Knuth, The Art of Computer Programming, third edition, Volume 1, Section 1.2.6, Equations 48, 49, and 50.
Примеры:
(%i1) declare (n, integer)$ (%i2) assume (n >= 0)$ (%i3) stirling1 (n, n); (%o3) 1
Функция stirling1 не упрощается для нецелых аргументов.
(%i1) stirling1 (sqrt(2), sqrt(2)); (%o1) stirling1(sqrt(2), sqrt(2))
Maxima применяет тождества для stirling1.
(%i1) declare (n, integer)$
(%i2) assume (n >= 0)$
(%i3) stirling1 (n + 1, n);
n (n + 1)
(%o3) ---------
2
(%i4) stirling1 (n + 1, 1);
(%o4) n!
Представляет число Стирлинга второго рода.
Для неотрицательных целых n и m число stirling2 (n, m)
есть число способов, которыми множество мощности n может быть разбито
на m непересекающихся подмножеств.
Для определения stirling2 (n, m) с m,
меньшим нуля, Maxima использует рекуррентное соотношение.
Для n меньших нуля и нецелых аргументов функция не определена.
stirling2 является упрощающей функцией.
Maxima знает следующие тождества.
Эти тождества применяются, если аргументы являются целыми или символами, которые объявлены
целыми, и первый аргумент неотрицателен.
Функция stirling2 не упрощается для нецелых аргументов.
Ссылки:
[1] Donald Knuth. The Art of Computer Programming, third edition, Volume 1, Section 1.2.6, Equations 48, 49, and 50.
[2] Graham, Knuth, and Patashnik. Concrete Mathematics, Table 264.
[3] Abramowitz and Stegun. Handbook of Mathematical Functions, Section 24.1.4.
Примеры:
(%i1) declare (n, integer)$ (%i2) assume (n >= 0)$ (%i3) stirling2 (n, n); (%o3) 1
Функция stirling2 не упрощается для нецелых аргументов.
(%i1) stirling2 (%pi, %pi); (%o1) stirling2(%pi, %pi)
Maxima применяет тождества для stirling2.
(%i1) declare (n, integer)$
(%i2) assume (n >= 0)$
(%i3) stirling2 (n + 9, n + 8);
(n + 8) (n + 9)
(%o3) ---------------
2
(%i4) stirling2 (n + 1, 2);
n
(%o4) 2 - 1
Возвращает подмножество множества a, которое удовлетворяет предикату f.
Функция subset возвращает множество, состоящее из элементов a,
для которых f возвращает любое значение, отличное от false.
Функция subset не применяет is к значению, возвращаемому f.
Функция subset вызывает ошибку, если a не является множеством.
См. также partition_set.
Примеры:
(%i1) subset ({1, 2, x, x + y, z, x + y + z}, atom);
(%o1) {1, 2, x, z}
(%i2) subset ({1, 2, 7, 8, 9, 14}, evenp);
(%o2) {2, 8, 14}
Возвращает true тогда и только тогда, когда a есть подмножество b.
Функция subsetp вызывает ошибку, если a или b не являются множествами.
Примеры:
(%i1) subsetp ({1, 2, 3}, {a, 1, b, 2, c, 3});
(%o1) true
(%i2) subsetp ({a, 1, b, 2, c, 3}, {1, 2, 3});
(%o2) false
Возвращает симметричную разницу, т.е. множество, элементы которого присутствуют только в одном множестве a_k.
При задании двух аргументов, symmdifference(a, b)
эквивалентно union ( setdifference (a, b ), setdifference (b, a)).
Функция symmdifference вызывает ошибку, если любой из ее аргументов не является множеством.
Примеры:
(%i1) S_1 : {a, b, c};
(%o1) {a, b, c}
(%i2) S_2 : {1, b, c};
(%o2) {1, b, c}
(%i3) S_3 : {a, b, z};
(%o3) {a, b, z}
(%i4) symmdifference ();
(%o4) {}
(%i5) symmdifference (S_1);
(%o5) {a, b, c}
(%i6) symmdifference (S_1, S_2);
(%o6) {1, a}
(%i7) symmdifference (S_1, S_2, S_3);
(%o7) {1, z}
(%i8) symmdifference ({}, S_1, S_2, S_3);
(%o8) {1, z}
Расширяет бинарную функцию F до n-арной методом композиции. Аргумент s является множеством или списком.
Функция tree_reduce действует следующим образом:
F применяется к последовательным парам элементов, чтобы сформировать новый список
[F(s_1, s_2), F(s_3, s_4), ...].
При этом если число элементов нечетно, то последний элемент остается неизменным.
Затем процесс повторяется до тех пор, пока не останется только один элемент списка,
который и возвращается в качестве значения.
Если присутствует необязательный элемент s_0, то
результат эквивалентен tree_reduce(F, cons(s_0, s).
Для сложения чисел с плавающей точкой tree_reduce может возвращать сумму с меньшей
ошибкой округления, чем rreduce или lreduce.
Элементы s и частичные результаты могут быть представлены в виде бинарного дерева минимальной глубины, откуда происходит название "tree_reduce".
Примеры:
Функция tree_reduce, примененная к списку с четным числом элементов.
(%i1) tree_reduce (f, [a, b, c, d]); (%o1) f(f(a, b), f(c, d))
Функция tree_reduce, примененная к списку с нечетным числом элементов.
(%i1) tree_reduce (f, [a, b, c, d, e]); (%o1) f(f(f(a, b), f(c, d)), e)
Возвращает объединение множеств от a_1 до a_n.
Вызов union() (без аргументов) возвращает пустое множество.
Функция union возвращает ошибку, если любой из ее аргументов не является множеством.
Примеры:
(%i1) S_1 : {a, b, c + d, %e};
(%o1) {%e, a, b, d + c}
(%i2) S_2 : {%pi, %i, %e, c + d};
(%o2) {%e, %i, %pi, d + c}
(%i3) S_3 : {17, 29, 1729, %pi, %i};
(%o3) {17, 29, 1729, %i, %pi}
(%i4) union ();
(%o4) {}
(%i5) union (S_1);
(%o5) {%e, a, b, d + c}
(%i6) union (S_1, S_2);
(%o6) {%e, %i, %pi, a, b, d + c}
(%i7) union (S_1, S_2, S_3);
(%o7) {17, 29, 1729, %e, %i, %pi, a, b, d + c}
(%i8) union ({}, S_1, S_2, S_3);
(%o8) {17, 29, 1729, %e, %i, %pi, a, b, d + c}
Расширяет функцию F до n-арной методом композиции или,
если F уже n-арная, применяет F к s.
Если F не является n-арной, то xreduce работает также, как lreduce.
Аргумент s является списком.
Известны следующие n-арные функции: сложение +,
умножение *, and, or, max,
min и append.
Функции могут быть объявлены n-арными при помощи declare(F, nary).
Для таких функций, xreduce работает быстрее, чем rreduce или lreduce.
Если задан необязательный аргумент s_0, то
результат эквивалентен xreduce(s, cons(s_0, s)).
Сложение чисел с плавающей точкой, строго говоря, не является ассоциативным.
Функция xreduce применяет n-арное сложение, если s содержит числа с плавающей точкой.
Примеры:
Функция xreduce, примененная к n-арной функции.
F вызывается однажды со всеми аргументами.
(%i1) declare (F, nary);
(%o1) done
(%i2) F ([L]) := L;
(%o2) F([L]) := L
(%i3) xreduce (F, [a, b, c, d, e]);
(%o3) [[[[[("[", simp), a], b], c], d], e]
Функция xreduce, примененная к не n-арной функции.
G вызывается несколько раз с двумя аргументами каждый раз.
(%i1) G ([L]) := L;
(%o1) G([L]) := L
(%i2) xreduce (G, [a, b, c, d, e]);
(%o2) [[[[[("[", simp), a], b], c], d], e]
(%i3) lreduce (G, [a, b, c, d, e]);
(%o3) [[[[a, b], c], d], e]
Previous: Введение в работу с множествами, Up: Множества [Contents][Index]