GelfandTsetlin
Gelfand–Tsetlin patterns — triangular interlacing arrays of rows with entries in — as a lazy indexed family.
SageMath
GelfandTsetlinPatterns(n, k)GelfandTsetlin(rows, max_entry)the triangular arrays with rows rows (lengths ), entries from 0 to max_entry, each row interlacing the row above it.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>, integer<0..>) -> indexed_collection<list<list<integer>>> | combinatorics | always |
Details
- A lazy indexed collection; the count is the closed-form dimension formula .
- Each element is the array's rows, top (length ) to bottom (length 1); row interlaces row : within a row entries weakly decrease, and .
- Unranked in backtracking generation order — rows built top-down, each row's entries enumerated within the bounds the row above imposes.
Definition
Epsil, as the implementation runs it.
count(_n, _k)
Fold(Function(Apply(
(gc_e: integer) => Fold(
Function(gc_w * gc_p, gc_w, gc_k),
gc_acc,
Range(1, gc_e, 1),
),
Apply((gc_st_init: list<integer>) => Fold(
(
gc_st: list<integer>,
gc_j,
) => Apply(
(gc_st_next: list<integer>) => gc_st_next,
gc_st if gc_st[2] >
_k +
2 * _n -
1 else Apply((gc_q: integer) => [gc_st[1] +
(Fold(Function(gc_a +
Fold(Function(gc_b +
(1 if (_k + gc_i + gc_j -
1) %
gc_q ==
0 else 0), gc_b, gc_j), 0, Range(gc_i, _n, 1)), gc_a, gc_i), 0, Range(1, _n, 1)) -
Fold(Function(gc_a +
Fold(Function(gc_b +
(1 if (gc_i + gc_j -
1) %
gc_q ==
0 else 0), gc_b, gc_j), 0, Range(gc_i, _n, 1)), gc_a, gc_i), 0, Range(1, _n, 1))), gc_q * gc_p], gc_st[2]),
),
gc_st_init,
Range(
1,
_k + 2 *
_n - 1,
1,
),
), [0, gc_p])[1],
) if Fold(
Function(
ok_gc_d && gc_p % gc_d != 0,
ok_gc_d,
gc_d,
),
True,
Range(2, gc_p - 1, 1),
) else gc_acc, gc_acc, gc_p), 1, Range(
2,
_k + 2 * _n -
1,
1,
))unrank(_n, _k, _r)
Apply(
(gu_end: list<integer>) => Map(
Function(Take(
Drop(
gu_end,
(gu_i - 1) *
(_n + 1) - ((gu_i - 1) *
gu_i - (gu_i - 1) *
gu_i % 2) / 2 + 1,
),
_n + 1 - gu_i,
), gu_i),
Range(1, _n, 1),
),
Apply(
(gu_state_init: list<integer>) => Fold((
gu_state: list<integer>,
gu_l,
) => Apply(
(gu_state_next: list<integer>) => gu_state_next,
Apply((gu_flat: list<integer>) => Apply((gt_m: integer) => Apply(
(gt_cap: list<integer>) => Apply(
(gt_lo: list<integer>) => Apply(
(gu_found: list<integer>) => Join(
[gu_found[1]],
Take(gu_flat, (gu_l - 1) *
(_n + 1) -
((gu_l - 1) *
gu_l -
(gu_l - 1) *
gu_l %
2) /
2),
Drop(gu_found, 2),
Drop(gu_flat, (gu_l - 1) *
(_n + 1) -
((gu_l - 1) *
gu_l -
(gu_l - 1) *
gu_l %
2) /
2 +
gt_m),
),
Apply((gu_s_init: list<integer>) => Fold(
(gu_s: list<integer>, gu_t) => Apply(
(gu_s_next: list<integer>) => gu_s_next,
gu_s if gu_s[2] == 1 else Apply((gu_row: list<integer>) => Apply(
(gu_w: integer) => Join([gu_s[1], 1], gu_row) if gu_s[1] < gu_w else Join(
[gu_s[1] - gu_w, 0],
Apply(
(gn_at: integer) => gu_row if gn_at == 0 else Apply((gn_c_init: list<integer>) => Fold((gn_c: list<integer>, gn_j) => Apply((gn_c_next: list<integer>) => gn_c_next, ReplaceAt(gn_c, gn_j, gu_row[gn_j] if gn_j < gn_at else gu_row[gn_j] + 1 if gn_j == gn_at else gt_lo[gn_j])), gn_c_init, Range(1, gt_m, 1)), gu_row),
Fold(Function(gn_i if gu_row[gn_i] <
(gt_cap[1] if gn_i == 1 else Min(gt_cap[gn_i], gu_row[gn_i - 1])) else gn_r, gn_r, gn_i), 0, Range(1, gt_m, 1)),
),
),
Fold(
Function(Apply(
(gw_e: integer) => Fold(Function(gw_w * gw_p, gw_w, gw_k), gw_acc, Range(1, gw_e, 1)),
Apply((gw_st_init: list<integer>) => Fold((gw_st: list<integer>, gw_j) => Apply(
(gw_st_next: list<integer>) => gw_st_next,
gw_st if gw_st[2] >
_k + gt_m else Apply((gw_q: integer) => [gw_st[1] +
(Fold(Function(gu_a +
Fold(Function(gu_b +
(1 if (gu_row[gu_i] - gu_row[gu_j] +
(gu_j - gu_i)) %
gw_q ==
0 else 0), gu_b, gu_j), 0, Range(gu_i + 1, gt_m, 1)), gu_a, gu_i), 0, Range(1, gt_m, 1)) -
Fold(Function(gv_a +
Fold(Function(gv_b +
(1 if (gv_j - gv_i) %
gw_q ==
0 else 0), gv_b, gv_j), 0, Range(gv_i + 1, gt_m, 1)), gv_a, gv_i), 0, Range(1, gt_m, 1))), gw_q * gw_p], gw_st[2]),
), gw_st_init, Range(1, _k + gt_m, 1)), [0, gw_p])[1],
) if Fold(Function(ok_gw_d &&
gw_p % gw_d !=
0, ok_gw_d, gw_d), True, Range(2, gw_p - 1, 1)) else gw_acc, gw_acc, gw_p),
1,
Range(2, _k + gt_m, 1),
),
), Drop(gu_s, 2)),
),
gu_s_init,
Range(1, (Binomial(_n + _k, _n) if 0 <= _n &&
_n <=
_n + _k else 0) if gu_l == 1 else Fold(Function(gt_p *
(gt_cap[gt_i] - gt_lo[gt_i] +
1), gt_p, gt_i), 1, Range(1, gt_m, 1)), 1),
), Join([gu_state[1], 0], gt_lo)),
),
Map(Function(0, gt_z), Range(1, _n + 1 -
gu_l, 1)) if gu_l == 1 else Take(Drop(gu_flat, (gu_l - 1 -
1) *
(_n + 1) -
((gu_l - 1 -
1) *
(gu_l - 1) -
(gu_l - 1 -
1) *
(gu_l - 1) %
2) /
2 +
1), _n + 1 -
gu_l),
),
Map(
Function(_k, gt_z),
Range(1, _n + 1 -
gu_l, 1),
) if gu_l == 1 else Take(Drop(
gu_flat,
(gu_l - 1 -
1) *
(_n + 1) -
((gu_l - 1 -
1) *
(gu_l - 1) -
(gu_l - 1 -
1) *
(gu_l - 1) %
2) /
2,
), _n + 1 -
gu_l),
), _n + 1 -
gu_l), Drop(gu_state, 1)),
), gu_state_init, Range(1, _n, 1)),
Join(
[_r],
Map(
Function(0, gt_z),
Range(1, (_n * (_n + 1) - _n * (_n + 1) % 2) / 2, 1),
),
),
),
)rank(_n, _k, _x)
Apply(
(gr_flat: list<integer>) => Fold(Function(Apply((gt_m: integer) => Apply(
(gt_cap: list<integer>) => Apply(
(gt_lo: list<integer>) => Apply(
(gr_target: list<integer>) => gr_acc +
Apply((gr_s_init: list<integer>) => Fold(
(gr_s: list<integer>, gr_t) => Apply(
(gr_s_next: list<integer>) => gr_s_next,
gr_s if gr_s[2] == 1 else Apply((gr_row: list<integer>) => Join([gr_s[1], 1], gr_row) if 0 ==
Fold(Function(gt_d +
Abs(gr_row[gt_i] - gr_target[gt_i]), gt_d, gt_i), 0, Range(1, gt_m, 1)) else Join([gr_s[1] +
Fold(
Function(Apply(
(gw_e: integer) => Fold(Function(gw_w * gw_p, gw_w, gw_k), gw_acc, Range(1, gw_e, 1)),
Apply((gw_st_init: list<integer>) => Fold((gw_st: list<integer>, gw_j) => Apply(
(gw_st_next: list<integer>) => gw_st_next,
gw_st if gw_st[2] >
_k + gt_m else Apply((gw_q: integer) => [gw_st[1] +
(Fold(Function(gu_a +
Fold(Function(gu_b +
(1 if (gr_row[gu_i] - gr_row[gu_j] +
(gu_j - gu_i)) %
gw_q ==
0 else 0), gu_b, gu_j), 0, Range(gu_i + 1, gt_m, 1)), gu_a, gu_i), 0, Range(1, gt_m, 1)) -
Fold(Function(gv_a +
Fold(Function(gv_b +
(1 if (gv_j - gv_i) %
gw_q ==
0 else 0), gv_b, gv_j), 0, Range(gv_i + 1, gt_m, 1)), gv_a, gv_i), 0, Range(1, gt_m, 1))), gw_q * gw_p], gw_st[2]),
), gw_st_init, Range(1, _k + gt_m, 1)), [0, gw_p])[1],
) if Fold(Function(ok_gw_d &&
gw_p % gw_d !=
0, ok_gw_d, gw_d), True, Range(2, gw_p - 1, 1)) else gw_acc, gw_acc, gw_p),
1,
Range(2, _k + gt_m, 1),
), 0], Apply(
(gn_at: integer) => gr_row if gn_at == 0 else Apply((gn_c_init: list<integer>) => Fold(
(gn_c: list<integer>, gn_j) => Apply((gn_c_next: list<integer>) => gn_c_next, ReplaceAt(gn_c, gn_j, gr_row[gn_j] if gn_j < gn_at else gr_row[gn_j] + 1 if gn_j == gn_at else gt_lo[gn_j])),
gn_c_init,
Range(1, gt_m, 1),
), gr_row),
Fold(Function(gn_i if gr_row[gn_i] <
(gt_cap[1] if gn_i == 1 else Min(gt_cap[gn_i], gr_row[gn_i - 1])) else gn_r, gn_r, gn_i), 0, Range(1, gt_m, 1)),
)), Drop(gr_s, 2)),
),
gr_s_init,
Range(1, (Binomial(_n + _k, _n) if 0 <= _n &&
_n <=
_n + _k else 0) if gr_l == 1 else Fold(Function(gt_p *
(gt_cap[gt_i] - gt_lo[gt_i] +
1), gt_p, gt_i), 1, Range(1, gt_m, 1)), 1),
), Join([0, 0], gt_lo))[1],
Take(Drop(gr_flat, (gr_l - 1) *
(_n + 1) -
((gr_l - 1) *
gr_l -
(gr_l - 1) *
gr_l %
2) /
2), gt_m),
),
Map(
Function(0, gt_z),
Range(1, _n + 1 -
gr_l, 1),
) if gr_l == 1 else Take(Drop(
gr_flat,
(gr_l - 1 -
1) *
(_n + 1) -
((gr_l - 1 -
1) *
(gr_l - 1) -
(gr_l - 1 -
1) *
(gr_l - 1) %
2) /
2 +
1,
), _n + 1 -
gr_l),
),
Map(
Function(_k, gt_z),
Range(1, _n + 1 -
gr_l, 1),
) if gr_l == 1 else Take(Drop(
gr_flat,
(gr_l - 1 -
1) *
(_n + 1) -
((gr_l - 1 -
1) *
(gr_l - 1) -
(gr_l - 1 -
1) *
(gr_l - 1) %
2) /
2,
), _n + 1 -
gr_l),
), _n + 1 -
gr_l), gr_acc, gr_l), 0, Range(1, _n, 1)),
Apply((gr_f_init: list<integer>) => Fold(
(gr_f: list<integer>, gr_i) => Apply(
(gr_f_next: list<integer>) => gr_f_next,
Join(gr_f, _x[gr_i]),
),
gr_f_init,
Range(1, Length(_x), 1),
), []),
)valid(_n, _k, _x)
Fold(
Function(ok_gv_i && Apply((gv_r: list<integer>) => Length(gv_r) == _n + 1 -
gv_i &&
Fold(
Function(
ok_gv_j &&
gv_r[gv_j] >=
0 && gv_r[gv_j] <=
_k,
ok_gv_j,
gv_j,
),
True,
Range(
1,
Length(gv_r),
1,
),
) && Fold(
Function(ok_gv_k &&
gv_r[gv_k - 1] >=
gv_r[gv_k], ok_gv_k, gv_k),
True,
Range(
2,
Length(gv_r),
1,
),
), _x[gv_i]), ok_gv_i, gv_i),
True,
Range(1, Length(_x), 1),
) && Fold(
Function(ok_gv_l && Apply((gv_a: list<integer>) => Apply(
(gv_b: list<integer>) => Fold(
Function(ok_gv_m &&
gv_a[gv_m] >= gv_b[gv_m] &&
gv_b[gv_m] >=
gv_a[gv_m + 1], ok_gv_m, gv_m),
True,
Range(1, Length(gv_b), 1),
),
_x[gv_l],
), _x[gv_l -
1]), ok_gv_l, gv_l),
True,
Range(2, Length(_x), 1),
) if Length(_x) == _n else FalseEnumeration
Examples
1 more kept as data, checked against the oraclesAbout
| Examples | 2 |
|---|---|
| Crosswalk | SageMath |