Binary Permutations

Would you like to store more than one value in a single variable or column? Doing so can save considerable space resulting in less network traffic and faster throughput. Inspiration and credit for this post came from the SAS Global Forum paper "Deciphering PROC COMPARE Codes: The Use of the bAND Function" by Hinson and Coughlin.

To keep things simple, consider that we have four books A, B, C and D and need to track every combination of those four. That is someone may have no books or only B and C. To make this all work, assign values using the power of 2 from 0 forward as follows:

• 1 as 2⁰ = 1
• 2 as 2¹ = 2
• 3 as 2² = 4
• 4 as 2³ = 8
• 5 as 2⁴ = 16
• 6 as 2⁵ = 32
• 7 as 2⁶ = 64
• 8 as 2⁷ = 128

Using permutation with replacement of 4 objects taken 2 at a time (have it or not) there are 4² or 16 possible combinations. This can be stored in a single column via the use of bitwise operators such as SAS's band function (the bitwise logical AND of two arguments). The following code will help better illustrate how this works.

data x(drop = value);
  value = 15;
  do num = 0 to 15;
    binary = put(num, binary4.);
    if num > 0 then binval = 2 ** (num - 1);
    binsum + binval;
    if num > 0 then match = band(binval, value);
    format binval binsum comma8.;
    output;
  end;
run;

The binval column contains the value associated with the num column. So if you want books B and C that is the sum of 2 + 4 or 6. If all books were desired, the value is 15 in the binsum column or the cumulative sum of the binval column. You can look at the binary column to see these values in binary format reading back from right to left every combination is covered.

Below is the sample books data set followed by the actual macro function code. The use of low level functions are used to read the data and return the matched column values. This does assume that the data set is in the correct sorted order and only has the same number of rows as needed and no more. The limit to this process is 15 combination which is one less than 2¹⁵ or 32,767

data books;
  length i 3 book $6;
  do i = 1 to 4;
    book = cat("Book ", byte(64 + i));
    output;
  end;
run;

%macro band_permutations(
     dsn       =
   , column    =
   , value     = 
   , seperator = %str(,)
);
  %local dsid position type i binval retval;
    
  %let dsid = %sysfunc(open(&dsn, i));  /* open data set */
  %if &dsid %then %do;
    %let position = %sysfunc(varnum(&dsid, &column)); /* find position of column */
    %let type = %sysfunc(vartype(&dsid, &position));  /* is it 'C'har or 'N'um */
    %do i = 1 %to %sysfunc(attrn(&dsid, nlobs));      /* how many rows in data set */
      %let binval = %eval(2 ** %eval(&i - 1);         /* Calc the binary value */
   
      %if %sysfunc(band(&binval, &value)) > 0 %then %do;  /* Did value match */
        %if %sysfunc(fetchobs(&dsid, &i)) = 0 %then %do;  /* Retrive the row */
          %if %length(&retval) = 0 %then 
            %let retval = %sysfunc(getvar&type(&dsid, &position)); /* read column value */
 
            %else %let retval=&retval &seperator %sysfunc(getvar&type(&dsid, &position));
          %end;
          %else %sysfunc(sysmsg());  /* Write out message */
        %end;
      %end;  
      %let dsid = %sysfunc(close(&dsid)); /* close data set */
    %end; 
  %else %put %sysfunc(sysmsg());  /* unable to open the data set */
   
  /* return the value */
  &retval
%mend;

/* below resolves to result = Book B, Book C */
%put result = %band_permutations(dsn=books, column = book, value = 6);