PermutationsAsCycles
Every permutation of in cycle notation, fixed points kept, listed by cycle type.
OEIS
A000142PermutationsAsCycles(n)every permutation of as a cycle decomposition, by cycle typeTyped signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<cycle_decomposition> | combinatorics | always |
Details
- The same permutations as SymmetricGroup, in another order: by cycle type, in IntegerPartitions' order (the -cycles first, the identity last), then by the canonical cycle form, lexicographically. The order is our choice, not something cycle notation implies.
- Each element is a CycleDecomposition, so every permutation statistic answers on it.
Definition
Epsil, as the implementation runs it.
count(_n)
_n!unrank(_n, _r)
[] if _n == 0 else Apply(
(ty: list<integer>) => Apply(
(cend: list<integer>) => Map(
Function(Map(
Function(cend[2 * _n + ep + 5], ep),
Filter(
Range(1, _n, 1),
Function(cend[3 * _n + eq + 5] ==
eu, eq),
),
), eu),
Range(1, cend[5], 1),
),
Fold(
Function(Apply((ct: integer) => Apply((cn: integer) => Apply((cj: integer) => Apply((cz: integer) => Apply((cnc: integer) => Apply((cm: integer) => Apply((cends: integer) => Apply(
(cfree: list<integer>) => Apply((cx: integer) => ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(cs, 2, cn - cj), 3, 1),
4,
(cz -
cz %
(cj * cm)) /
(cj * cm),
), 5, cnc + 1), cj + 5, cm - 1), _n + cx + 5, 1), 2 * _n + ck + 5, cx),
3 * _n + ck + 5,
cnc + 1,
), cfree[1]) if ct < cends else Apply((cr: integer) => Apply(
(cper: integer) => Apply((cd: integer) => Apply(
(cx: integer) => ReplaceAt(ReplaceAt(ReplaceAt(ReplaceAt(ReplaceAt(cs, 1, cr -
cd * cper), 3, cj + 1), _n + cx + 5, 1), 2 * _n + ck + 5, cx), 3 * _n + ck + 5, cnc),
cfree[cd + 1],
), (cr -
cr % cper) /
cper),
((cn - cj -
1)! *
Fold(Function(la +
lq *
cs[lq + 5], la, lq), 0, Range(cj + 1, _n, 1)) -
(cn - cj -
1)! *
Fold(Function(la +
lq *
cs[lq + 5], la, lq), 0, Range(cj + 1, _n, 1)) %
cz) /
cz,
), ct - cends),
Filter(Range(1, _n, 1), Function(cs[_n + fq + 5] ==
0, fq)),
), ((cn - cj)! * cj * cm -
(cn - cj)! * cj * cm %
cz) /
cz), cs[cj + 5]), cs[5]), cs[4]), cs[3]), cs[2]), cs[1]), cs, ck),
Join(
[
ty[1],
_n,
1,
Fold(
Function(zz *
zk ^
ty[zk + 3] *
ty[zk + 3]!, zz, zk),
1,
Range(1, _n, 1),
),
1,
],
Drop(ty, 3),
Join(
[1],
Map(
Function(0, fz),
Range(2, _n, 1),
),
),
Join(
[1],
Map(
Function(0, fz),
Range(2, _n, 1),
),
),
Join(
[1],
Map(
Function(0, fz),
Range(2, _n, 1),
),
),
),
Range(2, _n, 1),
),
),
Fold(
Function(Apply((tr: integer) => Apply((tm: integer) => Apply((tf: integer) => Apply((tt: integer) => Apply(
(tp: list<integer>) => ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(ts, 1, tp[1]), 2, tm -
ta * tp[2]),
3,
tf *
(tm! /
((tm -
ta * tp[2])! *
ta ^ tp[2] *
tp[2]!)),
), ta + 3, tp[2]),
Fold(
Function(sc if 0 < sc[2] else Apply(
(sb: integer) => [sc[1], tt + 1 -
ti] if sc[1] < sb else [sc[1] - sb, 0],
tf *
(tm! /
((tm -
ta *
(tt + 1 -
ti))! *
ta ^
(tt + 1 -
ti) *
(tt + 1 -
ti)!)) *
_tables[(ta - 1) *
(_n + 1) +
(tm -
ta *
(tt + 1 -
ti)) +
1],
), sc, ti),
[tr, 0],
Range(1, tt, 1),
),
), (tm -
tm % ta) /
ta), ts[3]), ts[2]), ts[1]), ts, ta),
Join(
[_r, _n, 1],
Map(Function(0, tz), Range(1, _n, 1)),
),
Range(_n, 1, -1),
),
)rank(_n, _x)
0 if _n == 0 else Apply((flat: list<integer>) => Apply((lens: list<integer>) => Apply(
(rc: list<integer>) => Apply(
(starts: list<integer>) => Apply(
(off: integer) => off +
Fold(
Function(Apply((rx: integer) => Apply((rt: integer) => Apply((rn: integer) => Apply((rj: integer) => Apply((rz: integer) => Apply(
(rm: integer) => ReplaceAt(ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(rs, 2, rn - rj), 3, 1),
4,
(rz -
rz %
(rj * rm)) /
(rj * rm),
), rj + 5, rm - 1), _n + rx + 5, 1) if Contains(starts, rk) else Apply((rends: integer) => Apply(
(rper: integer) => Apply(
(rd: integer) => ReplaceAt(ReplaceAt(ReplaceAt(rs, 1, rt + rends + rd * rper), 3, rj + 1), _n + rx + 5, 1),
Count(Filter(Range(1, rx - 1, 1), Function(rs[_n + rq + 5] ==
0, rq))),
),
((rn - rj -
1)! *
Fold(Function(la +
lq *
rs[lq + 5], la, lq), 0, Range(rj + 1, _n, 1)) -
(rn - rj -
1)! *
Fold(Function(la +
lq *
rs[lq + 5], la, lq), 0, Range(rj + 1, _n, 1)) %
rz) /
rz,
), ((rn - rj)! * rj * rm -
(rn - rj)! * rj * rm %
rz) /
rz),
rs[rj + 5],
), rs[4]), rs[3]), rs[2]), rs[1]), flat[rk]), rs, rk),
Join(
[0, _n, 1, Fold(Function(zz *
zk ^ rc[zk] *
rc[zk]!, zz, zk), 1, Range(1, _n, 1)), 0],
rc,
Join([1], Map(Function(0, fz), Range(2, _n, 1))),
),
Range(2, _n, 1),
)[1],
Fold(
Function(Apply((`oo`: integer) => Apply((orm: integer) => Apply((of: integer) => Apply((om: integer) => [`oo` +
of *
Fold(Function(os2 +
orm! /
((orm -
oa * oj)! *
oa ^ oj *
oj!) *
_tables[(oa - 1) *
(_n + 1) +
(orm -
oa * oj) +
1], os2, oj), 0, Range(om + 1, (orm -
orm % oa) /
oa, 1)), orm -
oa * om, of *
(orm! /
((orm -
oa * om)! *
oa ^ om *
om!))], rc[oa]), os[3]), os[2]), os[1]), os, oa),
[0, _n, 1],
Range(_n, 1, -1),
)[1],
),
Fold(
Function(Join(sa, [sa[Length(sa)] + lens[si]]), sa, si),
[1],
Range(1, Length(lens) - 1, 1),
),
),
Map(
Function(Count(Filter(lens, Function(ll == ra, ll))), ra),
Range(1, _n, 1),
),
), Map(Function(Length(lc), lc), _x)), Flatten(_x))valid(_n, _x)
Apply((flat: list<integer>) => Fold(Function(
ok_vi && Length(_x[vi]) >= 1,
ok_vi,
vi,
), True, Range(1, Length(_x), 1)) &&
Length(flat) == _n && Fold(
Function(ok_vp &&
Contains(flat, vp), ok_vp, vp),
True,
Range(1, _n, 1),
) && Fold(
Function(ok_vc &&
Fold(
Function(ok_vq &&
_x[vc][vq] >= _x[vc][1], ok_vq, vq),
True,
Range(1, Length(_x[vc]), 1),
), ok_vc, vc),
True,
Range(
1,
Length(_x),
1,
),
) && Fold(
Function(ok_vk &&
_x[vk][1] <
_x[vk + 1][1], ok_vk, vk),
True,
Range(
1,
Length(_x) - 1,
1,
),
), Flatten(_x))tables(_n)
Fold(Function(Join(
w_t,
Fold(
Function(ReplaceAt(
w_row,
w_c + 1,
Fold(
Function(wa + w_c! / ((w_c -
w_s *
wm)! *
w_s ^
wm * wm!) *
w_t[(w_s - 1) *
(_n + 1) + (w_c -
w_s *
wm) + 1], wa, wm),
0,
Range(
0,
(w_c - w_c % w_s) /
w_s,
1,
),
),
), w_row, w_c),
Map(Function(0, w_z), Range(0, _n + 1 - 1, 1)),
Range(0, _n + 1 - 1, 1),
),
), w_t, w_s), Fold(
Function(ReplaceAt(
w_row,
w_c + 1,
1 if w_c == 0 else 0,
), w_row, w_c),
Map(
Function(0, w_z),
Range(0, _n + 1 - 1, 1),
),
Range(0, _n + 1 - 1, 1),
), Range(1, _n + 1 - 1, 1))Maps
Into and out of CycleDecomposition, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
From CycleDecomposition
- PermutationCycleDecomposition → PermutationinverseThe permutation a cycle decomposition describes.
To CycleDecomposition
- CycleDecompositionPermutation → CycleDecompositioninverseA permutation in cycle notation, fixed points kept: each cycle from its least point, cycles in order of those points.
Enumeration
Examples
1 more kept as data, checked against the oraclesStatistics #
About
| Examples | 4 |
|---|---|
| Crosswalk | OEIS |
See also: SymmetricGroup, CycleDecomposition, IntegerPartitions