Month: October 2020

Sample Code for Algorithm to Create Combinations of Characters

In my post here, I described an algorithm to create all possible combinations from a set of characters. However, it allows repetitions of characters in the generated combinations. e.g aas, aaa and so on.
In this post, I will demonstrate an implementation of this algorithm in PHP, without any parallelization of any kind. I don’t know if it’s even possible to parallelize code in PHP.

You can run this code on LAMPP, WAMP, MAMP or XAMPP if you like. Successive trials of code execution may be faster than previous ones. Maybe, you all won’t like this code since it uses the “goto” keyword which is believed to lead to the creation of spaghetti code.  However, this was the easiest way to implement the algo for me.

<?php 

$dictionary = array('a', 'b', 'c', 'd', 'e');

$startLen = 1;
$stopLen = 4;

$currLen = 1;

//function to create string combination from array of indices
function getStringFromChars($indices)
{
  global $dictionary;
  $str='';

  for($j = 0; $j < count($indices); $j++)
  {
    $str.=$dictionary[$indices[$j]];
  }
  
  return $str;
}

//check condition to stop generating combos
function timeToStop($indices)
{
  
  global $dictionary;
  
  $stop = false;
  
  for($j = 0; $j < count($indices); $j++)
  {
    if($indices[$j] < count($dictionary) - 1)
    {
      return $stop;
    }
  }

  $stop = true;
  
  return $stop;
}

//main function
function generate($startLen, $stopLen)
{
  global $dictionary;
  $attempts = 0;
  
  for($currLen = $startLen; $currLen <= $stopLen; $currLen++)
  {
    step3:
    $chars = array();
    
    $indices = array();
    
    //init the arrays
    for($i = 0; $i < $currLen; $i++ )
    {
      $indices[$i] = 0;
      
      $chars[$i] = $dictionary[$indices[$i]];
    }
    
    step4:
    $working_index = $currLen - 1;
    
    step5:
    $str = getStringFromChars($indices);
    
    step6:
    echo $str;
    echo "<br />";
    $attempts++;
    
    if(timeToStop($indices))
    {
      if($currLen < $stopLen)
      {
        
        continue;
      }
      else
      {
        break;
      }
    }
    
    if($indices[$working_index] < count($dictionary) - 1)
    {
      $indices[$working_index]++;
      goto step5;
    }
    else
    {	
      if($currLen > 1)
      {

      
        while($indices[$working_index] == count($dictionary) - 1)
          $working_index--;
          
        if($working_index == -1)
        {
          if($currLen < $stopLen)
          {
            
            continue;
          }
          else
            break;
        }
        else
        {				
          $indices[$working_index]++;
          //set all indices to the right of working_index to 0
          
          for($k = $working_index + 1; $k < count($indices); $k++)
          {
            $indices[$k] = 0;
          }
          
          goto step4;
        }	
      }
      else
      {
      
        if($currLen < $stopLen)
        {
          
          continue;
        }
        else
          break;
      }
    }
    
  }

  return $attempts;
}

$start = microtime(true);

$atts = generate($startLen, $stopLen);

$end = microtime(true);

$time_taken = $end - $start;

$rate = $atts / $time_taken;

echo "Time(seconds): ".$time_taken;
echo "<br />";

echo "Attempts: ".$atts;
echo "<br />";

echo "Rate: ".$rate." iterations per second";

 

Algorithm to create all combinations from a set of characters

In this post, I shall reveal an algorithm that generates all possible combinations of a given set of characters of a specified range of lengths. The algorithm is as follows:

1.  take dict as a character array of possible characters in your string combinations
take currLen as integer, startLen as integer, stopLen as integer, chars as character array,  indices as integer array

2.  initialize currLen = startLen

3.  Set length of chars array to currLen, length of indices array to currLen

4.  set working_index  = currLen - 1

5.  get string from chars array as follows

i.  set i'th element of chars array to indices[i]'th element of dict

ii. Do the operation in the previous step (i) from i = 0 to i = currLen - 1

iii. concatenate the elements of chars array to generate a string combination of characters

6.  print string in step 5

7.  if all elements of indices equal length of dict - 1

         if currLen < stopLen

              increment currLen by 1

              go to step 3

         else

              quit

8.  if element of indices at position = working_index < length of dict - 1

        increment element of indices at position = working_index by 1

        go to Step 5

    else

        if currLen > 1

             decrement working_index by 1 till element of

             indices at position = working_index equals length of dict - 1

             if working_index equals -1

                 if currLen < stopLen

                     increment currLen by 1

                     go to Step 3

                 else

                     quit

              else

                  increment element of indices at position = working_index by 1

                  set all elements of indices to the right of position = working_index to 0

                  go to Step 4

        else

            if currLen < stopLen

               increment currLen by 1

               go to Step 3

            else

               quit

 

At first glance, this algorithm may look like a brute force algorithm, but I seriously doubt that it can be used to do naughty things like cracking passwords. Of course, to unleash the full power of this algorithm, one needs to parallelize the code in his implementation of this algorithm. That way we can max out the cpu cores and enjoy a very large number of iterations per second.

It may, however, be used to create a reverse lookup database of one way cryptographic hash functions. But, with the use of salts being common nowadays, such a database of all possible plaintexts and their hashes may not be useful after all.

The best part about this algorithm is that it is non-recursive and so avoids an inordinately large number of function calls and a potential call stack overflow. This is true especially when the dictionary of characters is very large.

So, all in all, this algorithm may be used as a fun academic exercise. Or, perhaps one of you guys may come up with a practical use for this algorithm.