Subsets

The power set of $\{1, …, n\}$ — every subset, as a lazy indexed family of $2^n$.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaPower set↗MathWorldSubset↗PowerSet↗WikidataQ205170↗Encyclopedia of MathematicsPower_set↗nLabpower set↗Britannicatopic/power-set↗OEISA000079✓↗A320487✓↗A011782✓↗A131577✓↗A034008✓↗A166444✓↗Wolfram LanguageSubsets✓↗SageMathSubsets(n)✓↗SymPysubsets↗mathlib4Finset (Fin n)↗Rosetta CodePower set↗

Subsets(n)the $2^n$ subsets of $\{1, …, n\}$.

CombinatoricaSubsets[If[ListQ[n], n, Range[n]]]

Subsets(collection)the subsets of any finite collection.

CombinatoricaSubsets[If[ListQ[collection], collection, Range[collection]]]

Subsets(f(a, b, …))for any other head, its operands are the elements and each subset is built under the same head, as in $Subsets(a + b + c)$.

Subsets(n, k)the subsets of $\{1, …, n\}$ of size at most $k$.

Subsets(n, {k})the subsets of $\{1, …, n\}$ of size exactly $k$.

Subsets(n, {kmin, kmax, dn})the subsets of $\{1, …, n\}$ with size in $kmin, kmin+dn, …$ up to $kmax$; $dn$ defaults to $1$.

Typed signatures

Type	Package	Applies
(collection<any> | expression | integer, (integer | list<integer>)?) -> indexed_collection<finset> | list<finset | list<any>>	combinatorics	always

Domain: Collections

Details

• A lazy indexed collection: $Count(Subsets(n)) = 2^n$ in closed form and $At(Subsets(n), i)$ unranks the $i$-th subset, so no subset beyond the page in view is built.
• The subsets carrying a fixed size $k$ number $\binom{n}{k}$; summing over $k$ gives $2^n$. See Binomial.
• Each element is the subset's list of members; Length is its size.

Definition

Epsil, as the implementation runs it.

count(_n)

Fold(
      Function(gc + (Binomial(_n, gn) if True else 0), gc, gn),
      0,
      Range(0, _n, 1),
    )

unrank(_n, _r)

Apply(
       (gp: list<integer>) => Apply(
                                     (gm: list<integer>) => gm,
                                     Rest(Fold(
                                                Function(Apply(
                                                                (lc: list<integer>) => Join([lc[1]], Rest(ls_g), [lc[2]]),
                                                                Fold(
                                                                      Function(
                                                                                lp_g if lp_g[2] != 0 ||
                                                                                        lv_g <=
                                                                                        (0 if lj_g == 1 else ls_g[lj_g]) else [lp_g[1], lv_g] if lp_g[1] <
                                                                                                                 Binomial(_n - lv_g, gp[2] - lj_g) else [lp_g[1] -
                                                                                                                        Binomial(_n - lv_g, gp[2] - lj_g), 0],
                                                                                lp_g,
                                                                                lv_g,
                                                                              ),
                                                                      [
                                                                        ls_g[1],
                                                                        0,
                                                                      ],
                                                                      Range(
                                                                             1,
                                                                             _n,
                                                                             1,
                                                                           ),
                                                                    ),
                                                              ), ls_g, lj_g),
                                                [gp[1]],
                                                Range(1, gp[2], 1),
                                              )),
                                   ),
       Fold(
             Function(gs if gs[2] >= 0 else [gs[1], gk] if gs[1] <
                                                           (Binomial(_n, gk) if True else 0) else [gs[1] -
                                                                  (Binomial(
                                                                             _n,
                                                                             gk,
                                                                           ) if True else 0), -1], gs, gk),
             [_r, -1],
             Range(0, _n, 1),
           ),
     )

rank(_n, _x)

Apply((gy: list<integer>) => Fold(
                                   Function(gb +
                                            (Binomial(_n, gt) if True else 0), gb, gt),
                                   0,
                                   Range(0, Length(_x) - 1, 1),
                                 ) + Fold(
                                          Function(kr + Fold(
                                                              Function(kq +
                                                                       Binomial(
                                                                                 _n - kv,
                                                                                 Length(_x) - kj,
                                                                               ), kq, kv),
                                                              0,
                                                              Range((0 if kj ==
                                                                          1 else gy[kj - 1]) +
                                                                    1, gy[kj] - 1, 1),
                                                            ), kr, kj),
                                          0,
                                          Range(1, Length(_x), 1),
                                        ), Apply(
                                                 (gx: list<integer>) => gx,
                                                 Sort(_x),
                                               ))

valid(_n, _x)

Fold(Function(
               (ReplaceAt(dm_seen, _x[dm_j], 1) if dm_seen[_x[dm_j]] == 0 else ReplaceAt(
                                                                                          dm_seen,
                                                                                          _n + 1,
                                                                                          1,
                                                                                        )) if 1 <= _x[dm_j] &&
                                                                                             _x[dm_j] <= _n else ReplaceAt(dm_seen, _n + 1, 1),
               dm_seen,
               dm_j,
             ), Map(Function(0, dm_z), Range(1, _n + 1, 1)), Range(
                                                                   1,
                                                                   Length(_x),
                                                                   1,
                                                                 ))[_n + 1] == 0 &&
True

Maps

Into and out of Finset, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.

From Finset

• BinaryWordFinset → BinaryWordinverseA subset of 1..n as its characteristic word: letter i is 1 when i is a member.

To Finset

• DescentSetPermutation → FinsetThe positions where the word falls.
• FinsetBinaryWord → FinsetinverseThe subset of 1..m a binary word of length m marks: the positions holding 1.
• PeakSetPermutation → FinsetThe interior positions that rise then fall.
• PermutahedronVertexPermutation → FinsetThe vertex (σ(1), …, σ(n)), or its Loday point, is an ordered tuple of coordinates, while finset is an unordered set of positions (the carrier DescentSet and PeakSet use). Reordering the coordinates gives a different vertex but the same finset, so the map would not be injective. A finset-valued PermutahedronVertex is a type mismatch, not a gap to close.

Enumeration

Examples

Basic #

The documented $Subsets(collection)$ form, listed in the family's binary-mask order

live ↗

In$\mathrm{Subsets}(\bigl\lbrack a, b, c\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack a\bigr\rbrack, \bigl\lbrack b\bigr\rbrack, \bigl\lbrack c\bigr\rbrack, \bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack a, c\bigr\rbrack, \bigl\lbrack b, c\bigr\rbrack, \bigl\lbrack a, b, c\bigr\rbrack\bigr\rbrack$

$2^4$ subsets

live ↗

In$\mathrm{Count}(\mathrm{Subsets}(4))$Out$16$

the empty subset

live ↗

In$\mathrm{Subsets}(3)[1]$Out$\operatorname{Finset}((3,\bigl\lbrack\bigr\rbrack))$

live ↗

In$\mathrm{Subsets}(\bigl\lbrack a, b, c, d\bigr\rbrack, 2)$Out$\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack a\bigr\rbrack, \bigl\lbrack b\bigr\rbrack, \bigl\lbrack c\bigr\rbrack, \bigl\lbrack d\bigr\rbrack, \bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack a, c\bigr\rbrack, \bigl\lbrack a, d\bigr\rbrack, \bigl\lbrack b, c\bigr\rbrack, \bigl\lbrack b, d\bigr\rbrack, \bigl\lbrack c, d\bigr\rbrack\bigr\rbrack$

live ↗

In$\mathrm{Subsets}(\bigl\lbrack a, b, c, d\bigr\rbrack, \bigl\lbrack2\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack a, c\bigr\rbrack, \bigl\lbrack a, d\bigr\rbrack, \bigl\lbrack b, c\bigr\rbrack, \bigl\lbrack b, d\bigr\rbrack, \bigl\lbrack c, d\bigr\rbrack\bigr\rbrack$

Scope #

A size bound: the subsets with at most 2 elements, $1 + 4 + 6$

live ↗

In$\mathrm{Count}(\mathrm{Subsets}(4, 2))$Out$11$

An exact size $\{2\}$: $\binom{4}{2}$ subsets

live ↗

In$\mathrm{Count}(\mathrm{Subsets}(4, \bigl\lbrack2\bigr\rbrack))$Out$6$

A size range $\{0, 5, 2\}$, the even-size subsets, $2^{4}$ of them

live ↗

In$\mathrm{Count}(\mathrm{Subsets}(5, \bigl\lbrack0, 5, 2\bigr\rbrack))$Out$16$

live ↗

In$\mathrm{Subsets}(\bigl\lbrack a, b, c, d\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack a\bigr\rbrack, \bigl\lbrack b\bigr\rbrack, \bigl\lbrack c\bigr\rbrack, \bigl\lbrack d\bigr\rbrack, \bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack a, c\bigr\rbrack, \bigl\lbrack a, d\bigr\rbrack, \bigl\lbrack b, c\bigr\rbrack, \bigl\lbrack b, d\bigr\rbrack, \bigl\lbrack c, d\bigr\rbrack, \bigl\lbrack a, b, c\bigr\rbrack, \bigl\lbrack a, b, d\bigr\rbrack, \bigl\lbrack a, c, d\bigr\rbrack, \bigl\lbrack b, c, d\bigr\rbrack, \bigl\lbrack a, b, c, d\bigr\rbrack\bigr\rbrack$

live ↗

In$\mathrm{Subsets}(a+b+c)$Out$\bigl\lbrack0, a, b, c, a+b, a+c, b+c, a+b+c\bigr\rbrack$

live ↗

In$\mathrm{Subsets}(\bigl\lbrack a, b, c, d, k\bigr\rbrack, \bigl\lbrack0, 5, 2\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack a, c\bigr\rbrack, \bigl\lbrack a, d\bigr\rbrack, \bigl\lbrack a, k\bigr\rbrack, \bigl\lbrack b, c\bigr\rbrack, \bigl\lbrack b, d\bigr\rbrack, \bigl\lbrack b, k\bigr\rbrack, \bigl\lbrack c, d\bigr\rbrack, \bigl\lbrack c, k\bigr\rbrack, \bigl\lbrack d, k\bigr\rbrack, \bigl\lbrack a, b, c, d\bigr\rbrack, \bigl\lbrack a, b, c, k\bigr\rbrack, \bigl\lbrack a, b, d, k\bigr\rbrack, \bigl\lbrack a, c, d, k\bigr\rbrack, \bigl\lbrack b, c, d, k\bigr\rbrack\bigr\rbrack$

Applications #

live ↗

In$\mathrm{Subsets}(\mathrm{Divisors}(10))$Out$\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack1\bigr\rbrack, \bigl\lbrack2\bigr\rbrack, \bigl\lbrack5\bigr\rbrack, \bigl\lbrack10\bigr\rbrack, \bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack1, 5\bigr\rbrack, \bigl\lbrack1, 10\bigr\rbrack, \bigl\lbrack2, 5\bigr\rbrack, \bigl\lbrack2, 10\bigr\rbrack, \bigl\lbrack5, 10\bigr\rbrack, \bigl\lbrack1, 2, 5\bigr\rbrack, \bigl\lbrack1, 2, 10\bigr\rbrack, \bigl\lbrack1, 5, 10\bigr\rbrack, \bigl\lbrack2, 5, 10\bigr\rbrack, \bigl\lbrack1, 2, 5, 10\bigr\rbrack\bigr\rbrack$

All 3-element subsets of a 4-element set

live ↗

In$\mathrm{Subsets}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack, \bigl\lbrack3\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack1, 2, 3\bigr\rbrack, \bigl\lbrack1, 2, 4\bigr\rbrack, \bigl\lbrack1, 3, 4\bigr\rbrack, \bigl\lbrack2, 3, 4\bigr\rbrack\bigr\rbrack$

live ↗

In$\sum\mathrm{Subsets}(abcdk, \bigl\lbrack3\bigr\rbrack)$Out$abc+abd+acd+bcd+abk+ack+bck+adk+bdk+cdk$

live ↗

In$\mathrm{Subsets}(\bigl\lbrack1, 2, 4, 8, 16\bigr\rbrack, \bigl\lbrack3\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack1, 2, 4\bigr\rbrack, \bigl\lbrack1, 2, 8\bigr\rbrack, \bigl\lbrack1, 2, 16\bigr\rbrack, \bigl\lbrack1, 4, 8\bigr\rbrack, \bigl\lbrack1, 4, 16\bigr\rbrack, \bigl\lbrack1, 8, 16\bigr\rbrack, \bigl\lbrack2, 4, 8\bigr\rbrack, \bigl\lbrack2, 4, 16\bigr\rbrack, \bigl\lbrack2, 8, 16\bigr\rbrack, \bigl\lbrack4, 8, 16\bigr\rbrack\bigr\rbrack$

Properties #

A set of $n$ elements has $2^n$ subsets: $Count(Subsets(list)) = 2^n$

live ↗

In$\mathrm{Length}(\mathrm{Subsets}(1..10))$Out$1\,024$

Counting by size: $\sum_k \binom{n}{k} = 2^n$ subsets of a 5-set. See Binomial

live ↗

In$\sum_{k=0}^5\binom{5}{k}$Out$32$

live ↗

In$\mathrm{Subsets}(\bigl\lbrack c, b, a\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack c\bigr\rbrack, \bigl\lbrack b\bigr\rbrack, \bigl\lbrack a\bigr\rbrack, \bigl\lbrack c, b\bigr\rbrack, \bigl\lbrack c, a\bigr\rbrack, \bigl\lbrack b, a\bigr\rbrack, \bigl\lbrack c, b, a\bigr\rbrack\bigr\rbrack$

The three 2-element subsets of $\{a,b,c\}$, in lexicographic order

live ↗

In$\mathrm{Subsets}(\bigl\lbrack a, b, c\bigr\rbrack, \bigl\lbrack2\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack a, c\bigr\rbrack, \bigl\lbrack b, c\bigr\rbrack\bigr\rbrack$

live ↗

In$\mathrm{Subsets}(\bigl\lbrack a, b, b, b\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack a\bigr\rbrack, \bigl\lbrack b\bigr\rbrack, \bigl\lbrack b\bigr\rbrack, \bigl\lbrack b\bigr\rbrack, \bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack b, b\bigr\rbrack, \bigl\lbrack b, b\bigr\rbrack, \bigl\lbrack b, b\bigr\rbrack, \bigl\lbrack a, b, b\bigr\rbrack, \bigl\lbrack a, b, b\bigr\rbrack, \bigl\lbrack a, b, b\bigr\rbrack, \bigl\lbrack b, b, b\bigr\rbrack, \bigl\lbrack a, b, b, b\bigr\rbrack\bigr\rbrack$

About

Examples	20
Checked against	Wolfram Language 20 agreeCombinatorica 8 agree1 differSageMath 1 agreeSymPy 1 agreemathlib4 1 agree
Crosswalk	WikipediaMathWorld ×2WikidataEncyclopedia of MathematicsnLabBritannicaOEIS ×6Wolfram LanguageCombinatoricaSageMathSymPymathlib4Rosetta Code

Implementation

mappedcombinatoricapackages/oracle/src/mappings.ts

Subsets of 1..n, or of a list, by size and then lexicographically.

See also: Binomial, Length, Count, At, KSubsets, Multisets, Tuples