Generates all subsets of n items in a minimal change order.

Category: | Combinatorial |

Restriction: | The GRAYCODE function cannot be executed when you use the %SYSFUNC macro. |

specifies a numeric variable. Initialize k to either of the following values before executing the GRAYCODE function:

specifies numeric variables
that have values of 0 or 1 which are updated when GRAYCODE is executed.
A value of 1 for numeric-variable-j indicates that the j^{th} item is in the subset. A value of 0 for numeric-variable-j indicates that the j^{th} item is not in
the subset.

specifies a character
variable that has a length of at least n characters. The first n characters
indicate which items are in the subset. By default, an "I" in the j^{th} position indicates
that the j^{th} item is in the subset, and an "O" in the j^{th} position indicates that the j^{th} item is out of
the subset. You can change the two characters by specifying the in-out argument.

specifies a numeric constant, variable, or expression. By default, n is the length of character-variable.

specifies a character constant, variable, or expression. The default value is "IO." The first character is used to indicate that an item is in the subset. The second character is used to indicate that an item is out of the subset.

When you execute GRAYCODE
with a negative value of k,
the subset is initialized to be empty. The GRAYCODE function returns
zero.

When you execute GRAYCODE
with an integer value of k between
0 and n inclusive, one item
is either added to the subset or removed from the subset, and the
value of k is updated to equal
the number of items in the subset. If the j^{th} item is added to the subset or removed
from the subset, the GRAYCODE function returns j.

To generate all subsets
of n items, you can initialize k to a negative value and execute GRAYCODE in
a loop that iterates 2**n times.
If you want to start with a non-empty subset, then initialize k to be the number of items in the subset, initialize
the other arguments to specify the desired initial subset, and execute
GRAYCODE in a loop that iterates 2**n-1 times. The sequence of subsets that are generated by GRAYCODE
is cyclical, so you can begin with any subset that you want.

The following program
uses numeric variables to generate subsets in a minimal change order.

data _null_; array x[4]; n=dim(x); k=-1; nsubs=2**n; do i=1 to nsubs; rc=graycode(k, of x[*]); put i 5. +3 k= ' x=' x[*] +3 rc=; end; run;

SAS writes the following
output to the log:

1 k=0 x=0 0 0 0 rc=0 2 k=1 x=1 0 0 0 rc=1 3 k=2 x=1 1 0 0 rc=2 4 k=1 x=0 1 0 0 rc=1 5 k=2 x=0 1 1 0 rc=3 6 k=3 x=1 1 1 0 rc=1 7 k=2 x=1 0 1 0 rc=2 8 k=1 x=0 0 1 0 rc=1 9 k=2 x=0 0 1 1 rc=4 10 k=3 x=1 0 1 1 rc=1 11 k=4 x=1 1 1 1 rc=2 12 k=3 x=0 1 1 1 rc=1 13 k=2 x=0 1 0 1 rc=3 14 k=3 x=1 1 0 1 rc=1 15 k=2 x=1 0 0 1 rc=2 16 k=1 x=0 0 0 1 rc=1

The following example
uses a character variable to generate subsets in a minimal change
order.

data _null_; x='++++'; n=length(x); k=countc(x, '+'); put ' 1' +3 k= +2 x=; nsubs=2**n; do i=2 to nsubs; rc=graycode(k, x, n, '+-'); put i 5. +3 k= +2 x= +3 rc=; end; run;

SAS writes the following
output to the log:

1 k=4 x=++++ 2 k=3 x=-+++ rc=1 3 k=2 x=-+-+ rc=3 4 k=3 x=++-+ rc=1 5 k=2 x=+--+ rc=2 6 k=1 x=---+ rc=1 7 k=0 x=---- rc=4 8 k=1 x=+--- rc=1 9 k=2 x=++-- rc=2 10 k=1 x=-+-- rc=1 11 k=2 x=-++- rc=3 12 k=3 x=+++- rc=1 13 k=2 x=+-+- rc=2 14 k=1 x=--+- rc=1 15 k=2 x=--++ rc=4 16 k=3 x=+-++ rc=1

Copyright © SAS Institute Inc. All rights reserved.