Question

III. ASSIGNMENT 2.1

As discussed in class, the example program enumerates all possible strings (or if we interpret as numbers, numbers) of base-b and a given length, say l. The number of strings enumerated is b l . Now if we interpret the outputs as strings, or lists, rather than base-b numbers and decide that we only want to enumerate those strings that have unique members, the number of possible strings reduces from b l to b!. Furthermore, consider a case where b = 2. If we were to enumerate all possible strings where l = 2, we would have the following collection: {00, 01, 10, 11}, that is a collection of size 2 2 or 4. Now, if we were to consider the case where we restrict to what is termed in this problem unique members we have only {01, 10} as in both cases {00, 11} we have either 0 or 1 appear more than once in the string. Lets look at a case where b = 3 and l = 3. The enumeration of all possible strings is listed below.

{000, 001, 002, 010, 011, 012, 020, 021, 022,

100, 101, 102, 110, 111, 112, 120, 121, 122,

200, 201, 202, 210, 211, 212, 220, 221, 222}

This is 3 ^3 or 27 possible strings.

Now lets look at those strings with unique members (per position).

{012, 021, 102, 120, 201, 210}

This is 3! or 6 possible strings.

Programming assignment 2.1 is to produce a list of all possible strings with only unique members or digits given a base b such that 2 ≤ b ≤ 10 and length l where b = l.

IV. ASSIGNMENT 2.2

Programming assignment 2.2 is to produce a list of all possible strings of unique members or digits given a base b such that 2 ≤ b ≤ 10 and length l where b > l.

V. SAMPLE OUTPUT

A sample output for assignments 2.1 and 2.2 is listed below. The solutions should adhere to the below listed output format.

01

10

b: 2 l: 2 runtime: 0 ms.

First line of output is the first string in ascending order of magnitude when evaluated as a base b number. Each consecutive line lists the next string in ascending order of magnitude when evaluated as a base b number. Then two line breaks and a descriptive output of run time execution. The runtime execution output should be exactly in the format listed above.

If possible please use sample code:

#include<iostream>
#include<cmath>
#include <chrono>
using namespace std;
using namespace std::chrono;

int generator(int base, int length){

   /** Algorithm only supports base 2 (binary) to base 9 **/
   if(base < 2 || base > 10){
       cout << "Err: Invalid Base Provided";
       return 1;
   }
   /** Algorithm only supports base 2 (binary) to base 9 **/

   /** Compute number of all possibile strings, this is a string that does not have any uniqueness constraint **/
   int possible = pow(base, length);
   /** Compute number of all possibile strings, this is a string that does not have any uniqueness constraint **/

   /** Instantiate an array that supports all possible strings for given length and base **/
   int generated[possible][length];
   /** Instantiate an array that supports all possible strings for given length and base **/
  
   /** Initialize each element in the array for all possible strings to 0 **/
   for(int i = 0; i < possible; i++){
for(int j = 0; j < length; j++){
generated[i][j] = 0;
}
   }
   /** Initialize each element in the array for all possible strings to 0 **/

    /** An iterator that increments per position in a given string **/
   int iteration = 0;
   /** An iterator that increments per position in a given string **/

   /** An iterator that increments per segment of a given string **/
   int steps = base;
   /** An iterator that increments per segment of a given string **/

   while(iteration < length){
       /** Algorithm logic to be clarified during lecture **/
       int repetitions = possible/steps;
       int value = 0;
       int position = 0;
       for(int s = 0; s < steps; s++){
           for(int r = 0; r < repetitions; r++){
               generated[position][iteration] = value;
               /**
               Begin: DEBUG
               cout << "steps: " << steps << " repetitions: " << repetitions << " value: " << value << " position: " << position <<"\n";
               End: DEBUG
               **/
               position += 1;
           }
           value = (value+1)%base;
          
       }
       steps *= base;
       iteration += 1;
       /** Algorithm logic to be clarified during lecture **/
   }

   /** Outputting all possible strings for a given base and length **/
   for(int i = 0; i < possible; i++){
       for(int j = 0; j < length; j++){
           cout << generated[i][j];
       }
       cout << "\n";
   }
   /** Outputting all possible strings for a given base and length **/
   return 0;
}

int main() {
   //Set value of base and length
   int base = 2;
    int length = 3;
   //Capture Time Prior to Execution
   milliseconds initial = duration_cast< milliseconds >(system_clock::now().time_since_epoch());
   //Execute our algorithm that models a growth rate.
   generator(base, length);
   //Capture Time of Execution Completion
   milliseconds resulting = duration_cast< milliseconds >(system_clock::now().time_since_epoch());
   //Compute the Duration of Execution
   milliseconds duration = resulting - initial;
   //Output Execution Duration
   cout << "b: " << base << " l: " << length << " runtime: " << std::to_string(duration.count()) << " ms.\n";
   return 0;
}

Answer 1

ASSIGNMENT 2.1 & 2.2

#include<iostream>
#include<cmath>
#include <chrono>
#include <vector>
using namespace std;
using namespace std::chrono;

/** vector of strings to store the generated strings of base b and length l **/
vector< string > generated;
/** vector of strings to store the generated strings of base b and length l **/

void generateUnique(int base, int length, string s, bool done[11]){
   /** base condition to check if the string is of the required length or not **/
   if(s.length()==length){
      
       /** inserting the string into the collection if done **/
       generated.push_back(s);
       /** inserting the string into the collection if done **/
      
       return;
   }
   /** base condition to check if the string is of the required length or not **/
  
   /** loop to check the numbers which have not been used yet and calling the iterative function for them **/
   for(int i=0;i<base;i++){
       if(!done[i])
       {
           done[i]=1;
           generateUnique(base , length ,s+(char)(i+'0') , done);
           done[i]=0;
       }
   }
   /** loop to check the numbers which have not been used yet and calling the iterative function for them **/
}

int generator(int base, int length){
  
   /** Algorithm only supports base 2 (binary) to base 10 **/
    if(base < 2 || base > 10){
       cout << "Err: Invalid Base Provided";
       return 1;
    }
    /** Algorithm only supports base 2 (binary) to base 10 **/
   
    /** string which will contain the current string **/
    string s;
    /** string which will contain the current string **/
   
    /** boolean array to check if a number from 0 to (b-1) has been already used or not **/
    bool done[11]={0};
    /** boolean array to check if a number from 0 to (b-1) has been already used or not **/
   
    /** recursive function to generate the strings **/
    generateUnique( base, length, s, done);
    /** recursive function to generate the strings **/
   
    /** outputing the collection **/
      for(int i=0;i<generated.size(); i++)
      cout<<generated[i]<<"\n";
   /** outputing the collection **/  
      
   return 0;  
}

int main() {
   //Set value of base and length
   int base = 4;
   int length = 2;

   //Capture Time Prior to Execution
   milliseconds initial = duration_cast< milliseconds >(system_clock::now().time_since_epoch());

   //Execute our algorithm that models a growth rate.
   generator(base, length);

   //Capture Time of Execution Completion
   milliseconds resulting = duration_cast< milliseconds >(system_clock::now().time_since_epoch());

   //Compute the Duration of Execution
   milliseconds duration = resulting - initial;

   //Output Execution Duration
   cout << "b: " << base << " l: " << length << " runtime: " << std::to_string(duration.count()) << " ms.\n";
   return 0;
}

OUTPUT:

01
02
03
10
12
13
20
21
23
30
31
32
b: 4 l: 2 runtime: 16 ms.

The above program recursively generates the required strings with unique characters .This program can be used for both the assignments 2.1 and 2.2. The recursive function maintains an array of boolean to check which characters have been already used and whch not. Thus it generates all the unique strings of the given length having base b.