NEXT SUBSET

NEXT SUBSET (LET)

Let Subcommand

Generate the next subset of an n-set.

A basic combinatorial problem is to generate the 2ⁿ subsets of the set {1, 2, ..., n}. For a given value of n there are 2ⁿ subsets.

This command can be used to generate all of these subsets for a given value of n. Each time this command is called for a given value of n, the next subset is returned. Note that the first call with a given value of n has a slightly different syntax than the subsequent calls since the subsequent calls need to specify the most recent subset generated.

The output is an array of zero and one values where zero for the ith element of the set indicates the element is not present and a value of one indicates the ith element is present. For example, if n = 5 an output array of

1 0 0 1 1

specifies that elements 1, 4, and 5 are present while elements 2 and 3 are not.

LET <y> = NEXT SUBSET <n>
where <n> is a number or parameter that specifies the size of the set;
and      <y> is a variable where the current subset is saved.

This syntax is used to return the first subset in the sequence of subsets.

LET <y> = NEXT SUBSET <n> <yprev>
where <n> is a number or parameter that specifies the size of the set;
            <yprev> is a variable that contains the most recently generated subset for the given value of <n>;
and      <y> is a variable where the current subset is saved.

This syntax is used to return all subsets in the sequence of subsets after the first subset has been generated.

LET Y = NEXT SUBSET N
LET Y = NEXT SUBSET N YPREV

Dataplot implements this command using the algorithm NEXSUB described in Nijenhuis and Wilf (see Reference section below).

Dataplot saves the internal parameter LASTSEQU when this command is entered. If LASTSEQU = 1, this indicates that the current subset is the last subset in the sequence for the given value of n. Otherwise, the value of LASTSEQU will be set to 0.

None

None

LET	= Generate data transformations.
RANDOM PERMUTATION	= Generate a random permutation.
RANDOM K-SET OF N-SET	= Generate a random k-set of n-set.
RANDOM COMPOSITION	= Generate a random composition.
RANDOM PARTITION	= Generate a random partition.
RANDOM SUBSET	= Generate a random subset.
RANDOM EQUIVALENCE RELATION	= Generate a random equivalence relation.
NEXT PERMUTATION	= Generate the next permutation.
NEXT K-SET OF N-SET	= Generate the next k-set of n-set.
NEXT COMPOSITION	= Generate the next composition.
NEXT PARTITION	= Generate the next partition.
NEXT EQUIVALENCE RELATION	= Generate the next composition.

Nijenhuis and Wilf (1978), "Combinatorial Algorithms", Second Edition, Academic Press, Chapter 1.

Combinatorial Analysis

2009/1

 
LET N = 3
LET NTOT = 2**N
SET WRITE REWIND OFF
WRITE SUBSET.OUT "ALL SUBSETS FOR N = 3"
LET Y = NEXT SUBSET N
LET YPREV = Y
PRINT Y
WRITE SUBSET.OUT "SUBSAMPLE 1:"
WRITE SUBSET.OUT Y
WRITE SUBSET.OUT " "
WRITE SUBSET.OUT " "
LOOP FOR K = 1 1 NTOT
    LET Y = NEXT SUBSET N YPREV
    WRITE SUBSET.OUT "SUBSAMPLE ^K:"
    WRITE SUBSET.OUT Y
    WRITE SUBSET.OUT " "
    WRITE SUBSET.OUT " "
    LET YPREV = Y
END OF LOOP
    

The file SUBSET.OUT contains

ALL SUBSETS FOR N = 3
SUBSAMPLE 1:
          0
          0
          0
 
 
SUBSAMPLE 2:
          1
          0
          0
 
 
SUBSAMPLE 3:
          1
          1
          0
 
 
SUBSAMPLE 4:
          0
          1
          0
 
 
SUBSAMPLE 5:
          0
          1
          1
 
 
SUBSAMPLE 6:
          1
          1
          1
 
 
SUBSAMPLE 7:
          1
          0
          1
 
 
SUBSAMPLE 8:
          0
          0
          1