AlternatingSignMatrices
The alternating sign matrices — entries in , every row and column summing to 1 with alternating nonzero signs — as a lazy indexed family.
Wikipedia
Alternating sign matrixMathWorldAlternatingSignMatrixWikidataQ3848436OEISA005130SageMathAlternatingSignMatrices(n)AlternatingSignMatrices(size)the ASMs of size size × size.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<list<list<integer>>> | combinatorics | always |
Details
- A lazy indexed collection; the count is the ASM number (the Robbins numbers, OEIS A005130) — .
- Each element is the matrix's rows; every row and column sums to 1, and every partial sum reading a row or column from its start lies in — the alternating-sign condition.
- The permutation matrices are exactly the ASMs with no entry; for every , with equality only at .
Definition
Epsil, as the implementation runs it.
count(_n)
Fold(Function(Apply(
(ac_e: integer) => Fold(
Function(ac_w * ac_p, ac_w, ac_k),
ac_acc,
Range(1, ac_e, 1),
),
Apply((ac_st_init: list<integer>) => Fold(
(
ac_st: list<integer>,
ac_j,
) => Apply(
(ac_st_next: list<integer>) => ac_st_next,
ac_st if ac_st[2] >
3 * _n else Apply((ac_q: integer) => [ac_st[1] +
(Fold(
Function(ac_a +
(3ac_j + 1 -
(3ac_j + 1) %
ac_q) /
ac_q, ac_a, ac_j),
0,
Range(0, _n - 1, 1),
) -
Fold(
Function(ac_a +
(_n + ac_j -
(_n + ac_j) %
ac_q) /
ac_q, ac_a, ac_j),
0,
Range(0, _n - 1, 1),
)), ac_q * ac_p], ac_st[2]),
),
ac_st_init,
Range(
1,
3 * _n,
1,
),
), [0, ac_p])[1],
) if Fold(
Function(
ok_ac_d && ac_p % ac_d != 0,
ok_ac_d,
ac_d,
),
True,
Range(2, ac_p - 1, 1),
) else ac_acc, ac_acc, ac_p), 1, Range(2, 3 * _n, 1))unrank(_n, _r)
Apply(
(au_end: list<integer>) => Map(
Function(Take(
Drop(
au_end,
2 + au_j * _n,
),
_n,
), au_j),
Range(0, _n - 1, 1),
),
Fold(Function(Apply(
(au_f: list<integer>) => Apply((au_to: integer) => Join(
[au_f[1], au_to],
Drop(au_u, 2),
Map(Function((au_to -
au_to %
2 ^
(_n - au_c)) /
2 ^
(_n - au_c) %
2 -
(au_u[2] -
au_u[2] %
2 ^
(_n - au_c)) /
2 ^
(_n - au_c) %
2, au_c), Range(1, _n, 1)),
), au_f[2]),
Fold(
Function(au_s if au_s[2] >= 0 else Apply(
(au_w: integer) => [au_s[1], au_o] if au_s[1] < au_w else [au_s[1] - au_w, -1],
_tables[2 ^ _n +
au_o +
1],
) if _tables[au_o + 1] ==
au_i +
1 &&
Apply(
(au_f_s: list<integer>) => 1 if au_f_s[1] == 1 &&
au_f_s[2] == 1 else 0,
Fold(
Function(Apply(
(au_f_p: integer) => [au_f_p, 1 if au_f_a[2] == 1 &&
au_f_p >= 0 &&
au_f_p <= 1 else 0],
au_f_a[1] +
((au_o -
au_o %
2 ^
(_n - au_f_c)) /
2 ^
(_n - au_f_c) %
2 -
(au_u[2] -
au_u[2] %
2 ^
(_n - au_f_c)) /
2 ^
(_n - au_f_c) %
2),
), au_f_a, au_f_c),
[0, 1],
Range(1, _n, 1),
),
) ==
1 else au_s, au_s, au_o),
[au_u[1], -1],
Range(0, 2 ^ _n - 1, 1),
),
), au_u, au_i), [_r, 0], Range(0, _n - 1, 1)),
)rank(_n, _x)
Fold(
Function(Apply((ar_row: list<integer>) => Apply(
(ar_to: integer) => [ar_a[1] +
Fold(
Function(ar_w +
(_tables[2 ^ _n + ar_o + 1] if _tables[ar_o + 1] ==
ar_i + 1 &&
Apply(
(ar_f_s: list<integer>) => 1 if ar_f_s[1] == 1 &&
ar_f_s[2] == 1 else 0,
Fold(
Function(Apply(
(ar_f_p: integer) => [ar_f_p, 1 if ar_f_a[2] == 1 &&
ar_f_p >= 0 &&
ar_f_p <= 1 else 0],
ar_f_a[1] +
((ar_o -
ar_o %
2 ^
(_n - ar_f_c)) /
2 ^
(_n - ar_f_c) %
2 -
(ar_a[2] -
ar_a[2] %
2 ^
(_n - ar_f_c)) /
2 ^
(_n - ar_f_c) %
2),
), ar_f_a, ar_f_c),
[0, 1],
Range(1, _n, 1),
),
) ==
1 else 0), ar_w, ar_o),
0,
Range(0, ar_to - 1, 1),
), ar_to],
Fold(
Function(as_k + ((ar_a[2] -
ar_a[2] %
2 ^
(_n - as_c)) /
2 ^
(_n -
as_c) %
2 +
ar_row[as_c]) *
2 ^
(_n -
as_c), as_k, as_c),
0,
Range(1, _n, 1),
),
), _x[ar_i + 1]), ar_a, ar_i),
[0, 0],
Range(0, _n - 1, 1),
)[1]valid(_n, _x)
(Fold(Function(ok_av_j && Apply(
(av_v_s: list<integer>) => av_v_s[1] == 1 && av_v_s[2] ==
1,
Fold(
Function(Apply(
(av_v_p: integer) => [
av_v_p,
1 if av_v_a[2] == 1 &&
av_v_p >= 0 &&
av_v_p <= 1 else 0,
],
av_v_a[1] + Apply(
(av_q: list<integer>) => av_q[av_j],
_x[av_v_k],
),
), av_v_a, av_v_k),
[0, 1],
Range(1, _n, 1),
),
), ok_av_j, av_j), True, Range(1, _n, 1)) if Fold(
Function(ok_av_i &&
Apply((av_r: list<integer>) => Apply(
(av_w_s: list<integer>) => av_w_s[1] == 1 &&
av_w_s[2] == 1,
Fold(
Function(Apply((av_w_p: integer) => [av_w_p, 1 if av_w_a[2] == 1 &&
av_w_p >= 0 &&
av_w_p <= 1 else 0], av_w_a[1] + av_r[av_w_k]), av_w_a, av_w_k),
[0, 1],
Range(1, _n, 1),
),
) if Length(av_r) == _n else False, _x[av_i]), ok_av_i, av_i),
True,
Range(1, Length(_x), 1),
) else False) if Length(_x) == _n else Falsetables(_n)
Apply((as_pop: list<integer>) => Join(
as_pop,
Fold(
Function(Apply((as_i: integer) => Fold(
Function(ReplaceAt(
as_t,
as_m + 1,
Fold(
Function(as_w +
(Apply(
(as_f_s: list<integer>) => 1 if as_f_s[1] == 1 &&
as_f_s[2] == 1 else 0,
Fold(
Function(Apply(
(as_f_p: integer) => [as_f_p, 1 if as_f_a[2] == 1 &&
as_f_p >= 0 &&
as_f_p <= 1 else 0],
as_f_a[1] +
((as_o -
as_o %
2 ^
(_n - as_f_c)) /
2 ^
(_n - as_f_c) %
2 -
(as_m -
as_m %
2 ^
(_n - as_f_c)) /
2 ^
(_n - as_f_c) %
2),
), as_f_a, as_f_c),
[0, 1],
Range(1, _n, 1),
),
) *
as_t[as_o + 1] if as_pop[as_o + 1] ==
as_i + 1 else 0), as_w, as_o),
0,
Range(0, 2 ^ _n -
1, 1),
),
) if as_pop[as_m + 1] ==
as_i else as_t, as_t, as_m),
as_u,
Range(0, 2 ^ _n -
1, 1),
), _n - 1 -
as_l), as_u, as_l),
ReplaceAt(Map(
Function(0, as_z),
Range(1, 2 ^ _n, 1),
), 2 ^ _n, 1),
Range(0, _n - 1, 1),
),
), Map(
Function(Fold(
Function(as_pc_a + (as_m -
as_m %
2 ^
(_n - as_pc_c)) /
2 ^
(_n -
as_pc_c) %
2, as_pc_a, as_pc_c),
0,
Range(1, _n, 1),
), as_m),
Range(0, 2 ^ _n - 1, 1),
))