r-Permutations With Repetitions

Problem : To generate all r-Permutation with repetitions of a set of distinct elements

Before we start discussing about the implementation we will go through the basic definitions of Permutations. Then we discuss the method to generate r-Permutations with repetitions with examples, and at last we implement a C Language Program of the problem. Continue reading.

Definitions

Permutation:

• A Permutation of a set of distinct objects is an ordered arrangement of these objects.

  Let A = {1,2,3} , then {1,2,3}, {1,3,2} , {2,1,3}, {2,3,1}, {3,2,1}, {3,1,2} are the permutations of set A

r-Permutation:

• An r-Permutation of a set of distinct objects is an ordered arrangement of some of these objects. Let there be n distinct elements in a set, then a permutation of r elements selected from that set is an r-Permutation of the set.

  Let A = {1,2,3} then {1,2},{2,1}{1,3},{3,1},{2,3},{3,2} are the 2-permutations of set A

r-Permutation with repetitions:

• An r-Permutation with repetitions of a set of distinct objects is an ordered arrangement of some of these objects, each allowed to be appear more than one time.

  Let A = {1,2,3} then {1,1},{1,2},{1,3},{2,1},{2,2},{2,3},{3,1},{3,2},{3,3} are the 2-permutations of set A

Let there be n elements in a set and we need to generate r all permutations of that set. Then by product rule we get there would be n^r such r-Permutations. For example if n = 10 and r = 3, then the first object of the permutation could be any of the 10 objects of the set. For each object in the first position of the permutation, the second position can have any 10 objects of the set, and for each object in the second position there can be also 10 objects in the third position of the permutation. That makes 10 * 10 * 10 = 1000 = 10³ permutations.

The Method

When we count the numbers in decimal number system, we actually generate r-permutation with repetitions with the ten decimal digits (0,1,2,3,4,5,6,7,8,9). Similarly when we count in binary we generate r-permutation with repetitions with the two bits (0 and 1) , and the same with octal and hexadecimal. In case of hexadecimal we use the first 6 alphabet as the last six symbols from the alphabet. Each position in a number runs from its minimum base value to its maximum base value. If there is a set with n symbols and we need to generate all r length permutations of that set, we will simply generate all the r length n base numbers and use the different symbols from the set to denote each different value. This technique is described elaborately with examples below.

Description

In a number the rightmost digit is called the LSB or the Least Significant Bit or Position and the leftmost digit is called the MSB or the Most Significant Bit or Position. (Here Bit, Digit and Symbols are used as the same thing). The left positions are of more significance and the right positions of a position is of more significance. Now note how a number is counted:
Let there be a 4 digit decimal number, and it starts from 0000. First the LSB (0th position) of the number will increase while it does not attain its maximum value, 9 . Thus we count the numbers 0000 to 0009. Next when we attempts to increase 9, we see that it already at the maximum value that a decimal digit can have, so the LSB is reset to 0 and the Next significant digit at position 1 is incremented from 0 to 1 and the number 0009 becomes 0010. Again the LSB increases from 0 to 9, thus counting from 0010 to 0019. In the next count the LSB is again reset and the Next significant position (position 1) is increased making it 0020. Similarly the LSB keeps on counting 0 to 9 and then again 0. At each 9 to 0 reset the Next more significant bit, the 1st digit increments. Let us see some more examples to make the thing clearer.

Let us consider the number is 0090 we will attempt to increment it. In this case the LSB will count from 0 to 9, and then reset to 0, then the next significant digit at position 1 attempts to increase, but it is already at 9 the maximum value, so position 1 resets to 0 , this triggers the 2nd position to increment from 0 to 1 thus making 0100.

In case of incrementing a number say 0099999, the 0th position will reset to 0 making the 1st position to increment which also resets to zero triggering 2nd position to increment, but this will also resets to zero and the 3rd position increments which also resets making 4th position to increment which again resets and increments 5th position from 0 to 1 and making the number 0100000 .

If there is a number 00969 the the LSB will be reset to 0 (it already is on it’s maximum value) and trigger the increment of 1st position making it 6 to 7 thus the number will become 00970. So a position will only increment if its next less significant position resets, and a position will reset when tried to increment it beyond the maximum value it can attain.

For an Octal number where each digit’s minimum and maximum attainable values are 0 and 7 respectively. In hexadecimal each digit can attain a minimum of 0 and the maximum of 15. The values from 10 to 15 are labeled with some symbols from the alphabet which are A to F respectively. Similarly say a 26 base number system will run from 0 to 25 (or 1 to 26) and we can assign the lowercase alphabets to each value.

The basic thing is a digit in a certain position will increase when the digit on its right side (the next less significant position) is reset, in other words when a digit resets from its maximum value to its minimum the next more significant digit will increase one count. Thus the reset of each digit triggers the increment of the next more significant position digit.

Now just think that you are given 10 characters say “abcdefghij” and you are told to generate all 4-permutation with repetitions of this set, that is generate all possible permutations of length 4 with repetitions. There will be a total of 10¹⁰ permutations. Can you find the similarity of this problem with counting all four digit decimal numbers from 0000 to 9999 ? If we just relabel the ten digits of the decimal number system with the characters in the set, and instead of printing out digit symbols we print out the characters, then we have the solution.

If we label 0 with a , 1 with b , 2 with c …. 9 with j , then the number 1654 will represent the string “bfed” , 6874 will represent “fhgd” etc. So counting up from 0000 to 9999 and labeling each number with the set characters will generate all r-permutation with repetitions of the set.
Notice that this problem does not depend on which characters you have to permute, because you can assign any label to the corresponding numbers. This depends the cardinality of the set, that is the number of characters i the set to permute. If there are 8 characters say “oklijhut” in the set to permute then the problem would be same , but the count would be like counting octal or 8 base number and then assigning labels to corresponding digit values.

Let us say there are 13 characters to permute, say “qwertyuiopasd” . Then the count would be like a 13 base number system. The minimum attainable value of a digit position would be 0 and the maximum attainable value would be 12 (0 to 12 are thirteen values). The LSB would increase from 0 to 12 and then reset to 0 making the next significant position to 1, and the counting would proceed as described above and then labeling each value with corresponding labels from the character set will generate the r-permutations of the set. If a number in 13 base is (6)(10)(9)(12)(5) then we get “ypost” after labeling each value with its corresponding symbol from the set.

Generally, if the set with which we need to generate r-permutation with repetitions has cardinality n , then we need to generate all r length numbers of base n number system, and then label each values of the number system with the elements of the set. Thus any arbitrary length of set can be permuted by generating all n base numbers with r length.

For example if the set consists of all alpha (upper case and lower case) numeric symbols and we need a 5-permutation with repetitions, then we will count all the 5 length numbers of a 26 + 26 + 10 = 62 base number system (a total of 62 ⁵ = 916132832 permutations).

Program Implementation

The complete source code and it’s description is shown below

/* Program to generate all r-Permutation of a set with distinct element 
 * This code is a part of https://phoxis.wordpress.com/2009/08/01/rpermrep/
 */
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

/* type values used in init_char_set() function */
#define UPPER  1
#define LOWER  2
#define NUM    4
#define PUNCT  16
#define ALPHA  3
#define ALNUM  7
#define ALL    23
#define CUSTOM 32

/* pre defined char sets used in init_char_set() function */
#define UPPER_CHAR_SET "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define LOWER_CHAR_SET "abcdefghijklmnopqrstuvwxyz"
#define DIGIT_CHAR_SET "0123456789"
#define PUNCT_CHAR_SET "~!@#$%^&*()_+{}|[]:\"<>?,./;'\\=-"

#define MAX_CHARS 150
#define MAX_GUESS 20

#ifndef NUL
#define NUL ''
#endif

/* Function Prototypes */
void permute_rep (const char *set, int n, int r);
char *init_char_set (short int type, char *custom);
int *init_perm_array (int len);
void make_perm_string (int *perm, const char *set, char *perm_str, int len, int print_flag);

/* Main Function, Drives the permute_rep() function */
int
main (void)
{
  char *set = NULL, custom[MAX_CHARS];
  int r;

  printf ("\nr-Permutation with repetitions.\n");

  printf ("Enter String Set To Permute: ");
  scanf ("%s", custom);

  printf ("\nLength Of Permutations (r): ");
  scanf ("%d", &r);

  set = init_char_set (CUSTOM, custom);
  printf ("\nPermutation Symbol set: \"%s\"\n", set);

  permute_rep (set, strlen (set), r);

  printf ("\nfinished\n");
  return 0;
}

/* Function Name : permute_rep
 * Parameters    : 
 *               @ (const char *) set : Pointer to the symbol sets to permute
 *               @ (int) n            : The length upto which the set would be used
 *               @ (int) r            : The length of the generated permutations
 * Return Value  : (void)
 * Description   : Generates all the Permutation with repetitions of length 'r' from the 'set' upto length 'n' .
 *                 Optionally prints them in stdout.
 */
void
permute_rep (const char *set, int n, int r)
{
  int *perm;
  char perm_str[MAX_CHARS];
  int i, j;

  perm = init_perm_array (r);
  
  while (perm[r] == 0)
    {
      for (j = 0; j < n; j++)
	{
	  make_perm_string (perm, set, perm_str, r, 1);
	  perm[0]++;
	}
      perm[0]++;
      for (i = 0; i < r; i++)
	{
	  if (perm[i] >= n)
	    {
	      perm[i] = 0;
	      perm[i + 1]++;
	    }
	}
    }
}


/* Function Name : init_char_set
 * Parameters    : 
 *               @ (short int) type   : The inbuilt type values to select character sets.
 *                                      'type' could be:
 *                                      1, 2, 4, 16, 32 or any of these values ORed. These are #defined
 *               @ (char *) custom    : Pointer to a custom symbol set to initialize. type should be 32 in,
 *                                      else this pointer is ignored.
 * Return Value  : (char *)           : Returns a pointer to the initialized character set
 * Description   : Allocates and initializes a pointer with a string of symbols to be permuted, and returns it
 */
char *
init_char_set (short int type, char *custom)
{
  char upper[] = UPPER_CHAR_SET;
  char lower[] = LOWER_CHAR_SET;
  char num[] = DIGIT_CHAR_SET;
  char punct[] = PUNCT_CHAR_SET;
  char *set;

  set = (char *) malloc (sizeof (char) * MAX_CHARS);

  if (type & UPPER)
    {
      strcat (set, upper);
    }
  if (type & LOWER)
    {
      strcat (set, lower);
    }
  if (type & NUM)
    {
      strcat (set, num);
    }
  if (type & PUNCT)
    {
      strcat (set, punct);
    }
  /* Remove redundant elements from custom string and build set. If input set is "hello"
   * then it will be reduced to "helo"
   */
  if (type & CUSTOM)
    {
      int i, j, k, n = strlen (custom), flag;
      for (i = 0, k = 0; i < n; i++)
	{
	  for (flag = 0, j = 0; j < k; j++)
	    {
	      if (custom[i] == set[j])
		{
		  flag = 1;
		  break;
		}
	    }
	  if (flag == 0)
	    {
	      set[k] = custom[i];
	      k++;
	    }
	}
    }
  return set;
}

/* Function Name : init_perm_array
 * Parameters    : 
 *               @ (int) len          : The length of the array
 * Return Value  : (int *)            : A pointer to the allocated permutation array
 * Description   : Allocates and initializes with 0 an array, which is used for generating 'r' base numbers
 */
int *
init_perm_array (int len)
{
  int *perm;
  perm = (int *) calloc (len + 1, sizeof (int));
  return perm;
}

/* Function Name : make_perm_string
 * Parameters    : 
 *               @ (int *) perm       : Pointer to the current permutation count state
 *               @ (const char *) set : Pointer to the symbol set to be permuted
 *               @ (char *) perm_str  : Pointer to the string containing permutation
 *               @ (int) len          : The length of permutation
 *               @ (int) print_state  : A flag. If true prints the permutation in stdout, else does not.
 * Return Value  : (void)
 * Description   : Makes a NULL terminated string representing the permutation of the symbols,
 *                 from the 'set' represented by 'perm' state. This labels each position of 'perm'
 *                 with the symbols from 'set' makes a string and returns it.
 *                 Also prints the string if 'print_state' is true.
 */
void
make_perm_string (int *perm, const char *set, char *perm_str, int len, int print_state)
{
  int i, j;

  for (i = len - 1, j = 0; i >= 0; i--, j++)
    {
      perm_str[j] = set[*(perm + i)];
    }
  perm_str[j] = NUL;

  if (print_state)
    printf ("%s\n", perm_str);
}

Click Here To Download this code

Description of permute_rep() function:

This receives a const char type pointer set which contains the symbols which are to be permuted, the value of n an integer which indicates the length of the set to be used (generally strlen(set)) and also determines the number system base which would be counted, and it accepts r that is the length of the generated permutations (the value of r in r-permutation). So if we want to generate 4-permutations with repetitions of a set “qwerty” then the call would be

Note: If you think to use the whole length of the string you pass everytime, then you may calculate strlen(set) inside permute_rep() and omit passing n.

permute_rep ("qwerty",sizeof("qwerty"),4);

The permute_rep() function first executes the perm = init_perm_array(r) which allocates an integer array of length r and returns its base address.

The outer while loop controls the count and limits the length of the count to r. This works like this: When r = 4 , we are only using position 0,1,2 and 3 . After the count 09999 the next number is 10000 , that is the count goes beyond position 4 making position 5 to change to 1, indicating all 4 permutations have been generated. This acts as a control flag. That is why an extra cell is allocated to perm in the init_perm_array() function. This loop also prints the generated permutation with the help of make_perm_string() (passing print_state = 1).

The first for loop counts the LSB from its minimum to maximum. The next statement perm[0]++ makes the LSB exceed it’s maximum attainable value then making it invalid (for the current). That is if n = 18 (when permuting 18 element set) then the first for loop will count the LSB from 0 to 17 and the next statement will take the LSB from 17 to 18, making it invalid. This invalid position is detected in the next for loop and it is reset to zero and the next significant place is incremented and checked again for an invalid value. That is the second for loop is used to reset and increment all the positions except the LSB. This loop runs until the number has not end or it has detected a valid value.

Other Functions:

Two other functions are defined which are make_guess_string() and init_char_set(). The make_perm_string() function simply labels the values in the perm array with the different symbols from set. Although the make_perm_string() constructs the string in reverse order, it is not needed. the print_state parameter tells the function if to also print the generated permutation or just return the string. This could be helpful generating brute force password hashes and attempting to crack a password. init_char_set() initializes the set of symbols to be permuted. This is made for easy using. Inbuilt types are defines like UPPER, LOWER,NUM,PUNCT,ALNUM,ALPHA,ALL and CUSTOM. Calling this with

set = init_char_set (UPPER, set, NULL);

will allocate and initialize the pointer set with uppercase alphabets

set = init_char_set (UPPER | LOWER, set, NULL);
or
set = init_char_set (ALPHA, set, NULL);

will allocate and initialize set with uppercase and lowercase alphabets

set = init_char_set (CUSTOM, set, "qwerty");

will allocate and initialize set with “qwerty”

This function also removes redundant symbols from the custom set. that is “aabbccdd” is considered “abcd” . The last parameter is ignored if type is not CUSTOM.

A 20 Digit Decimal Counter

We will make a 20 Digit or more digit decimal counter with the help of the above process. It can simply be seen that is the set = "0123456789" and r = 1,2,3 ... 20 , the above program could generate this thing.

for ( i = 0; i < n; i++)
  permute_rep (set, strlen(set), i);

What we will do is reduce the above function and design to only count decimal numbers, and remove additional functions to label the permutations and save computation. We will initilize the permutation array with the symbols itself. Because the decimal symbols (0 to 9) are adjacent in the ASCII table we can just increment normally to get the next count, and reset is done with the ASCII value of 0. In this case we need to generate permutation in a certain order, for example a decimal counter which is capable to count 20 digit number or a 50 digit number. Normal data-types would overflow several times counting such a large number. which assigns line numbers to a very long file.

This method is applied in the GNU cat program with the -n or -b switches are on. A sample of a 20digit decimal counter is presented below:

void generate_line_number (void);

#define LSB 20			/* pre calculated value 22 - 2, skipping the last two places */
#define LENGTH 23

/* length is 22 valid number length 20 last two positions for null and \t */
char line_number[LENGTH] =
  { ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',	/* Upper 10 digits */
    '\r', ' ', ' ', ' ', '\r', ' ',' ', ' ', ' ',' ',	/* Lower 10 digits */
    '0', '\t'						/* Null terminated and tab character */
};

void
generate_line_number (void)
{
  int i;

  line_number[LSB]++;
  if (line_number[LSB] == ':')
    {
      for (i = LSB; i >= 0; i--)
	{
	  if (line_number[i] == ':')
	    {
	      line_number[i] = '0';
	      if (line_number[i - 1] <= ' ')
		line_number[i - 1] = '1';
	      else
		line_number[i - 1]++;
	    }
	  else
	    break;
	}
    }
}

Note that in this implementation the LSB is the rightmost position. The line_number is a pre-formatted array. Each time this function is called it generates a new decimal number. This code was used in the cat equivalent program of Whitix OS project. This does not needs to construct the permutation, as the line_number is already a NULL terminated and tab aligned string.

Update Information

14.10.2009 : Source code update. Memory leak fixed.