GrayCodeSubsets

The subsets of $\{1, \dots, n\}$ in binary-reflected Gray-code order: consecutive subsets differ by exactly one element.

✓ checked against that system · ! checked, with disagreements (hover a chip)OEISA000079✓↗A320487✓↗A011782✓↗A131577✓↗A034008✓↗A166444✓↗

GrayCodeSubsets(n)the subsets of $\{1, \dots, n\}$ in binary-reflected Gray-code order

CombinatoricaMap[Sort[n + 1 - #] &, GrayCodeSubsets[Range[n]]]

Typed signatures

Type	Package	Applies
(integer<0..>) -> indexed_collection<list<integer>>	combinatorics	always

Domain: Collections

Definition

Epsil, as the implementation runs it.

count(_n)

2 ^ _n

unrank(_n, _r)

Filter(
        Range(1, _n, 1),
        Function((_r - _r % 2 ^ (i - 1)) / 2 ^ (i - 1) % 2 != (_r - _r % 2 ^ i) /
                                                              2 ^ i % 2, i),
      )

rank(_n, _x)

Fold(Function(
               acc + 2 ^ m * (Fold(Function(
                                             c + (1 if _x[t] >= m + 1 else 0),
                                             c,
                                             t,
                                           ), 0, Range(1, Length(_x), 1)) % 2),
               acc,
               m,
             ), 0, Range(0, _n - 1, 1))

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

Examples

Basic #

Consecutive subsets differ by exactly one element

live ↗

In$\mathrm{Take}(\mathrm{GrayCodeSubsets}(3), 8)$Out$\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack1\bigr\rbrack, \bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack2\bigr\rbrack, \bigl\lbrack2, 3\bigr\rbrack, \bigl\lbrack1, 2, 3\bigr\rbrack, \bigl\lbrack1, 3\bigr\rbrack, \bigl\lbrack3\bigr\rbrack\bigr\rbrack$

About

Examples	1
Checked against	Combinatorica 1 agree
Crosswalk	OEIS ×6Combinatorica

Implementation

mappedcombinatoricapackages/oracle/src/mappings.ts

Combinatorica's Gray code runs the other way round, from the last element; reflecting each element i to n + 1 - i gives ours.

See also: Subsets, GrayCodes