GRAYCODE Function

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.

Syntax

GRAYCODE(k, numeric-variable-1, ..., numeric-variable-n)

GRAYCODE(k, character-variable <, n <, in-out> > )

Required Arguments

k

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

a negative number to cause GRAYCODE to initialize the subset to be empty
the number of items in the initial set indicated by numeric-variable-1 through numeric-variable-n, or character-variable, which must be an integer value between 0 and n inclusive

The value of k is updated when GRAYCODE is executed. The value that is returned is the number of items in the subset.

numeric-variable

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.

If you assign a negative value to k before you execute GRAYCODE, then you do not need to initialize numeric-variable-1 through numeric-variable-n before executing GRAYCODE unless you want to suppress the note about uninitialized variables.

If you assign a value between 0 and n inclusive to k before you execute GRAYCODE, then you must initialize numeric-variable-1 through numeric-variable-n to k values of 1 and n-k values of 0.

character-variable

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.

If you assign a negative value to k before you execute GRAYCODE, then you do not need to initialize character-variable before executing GRAYCODE unless you want to suppress the note about an uninitialized variable.

If you assign a value between 0 and n inclusive to k before you execute GRAYCODE, then you must initialize character-variable to k characters that indicate an item is in the subset, and n-k characters that indicate an item is out of the subset.

Optional Arguments

n

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

in-out

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.

Details

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.

Examples

Example 1: Using n=4 Numeric Variables and Negative Initial k

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

Example 2: Using a Character Variable and Positive Initial k

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;