Generating String Combinations of Characters in Java

In my post here, I shared an algorithm to generate all possible combinations of a given set of characters for a specified range of lengths. In this post, I shall share a code sample written in Java that implements the algorithm shared before. It does not use any goto keyword and hence does not create sphagetti code.

The code uses the concurrency API of Java and is fully parallelized. It maxes out the CPU cores of a multi-core CPU and achieves a few million iterations per second. The code sample uses a custom utility function ‘power’ for calculating powers of integers. It is made static for more execution speed.
The code is commented in places to help readers understand it.

As with the algorithm, I take no responsibility for what is done with this code.

package stringgenerator;

import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

public class StringGenerator implements Runnable
{
  private static char[] dict = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l'};  //allowed characters
  
  private static ExecutorService ex;
  
  private static AtomicLong attempts = new AtomicLong(0); //count the number of combinations generated
  
  private static Object locker = new Object();
  
  private static long maxAttempts = 0; //total possible combinations of characters of specified lengths
  
  private static int maxLen = 0;
  
  private static long getMaxAttempts(int radix, int maxLen)
  {
    maxAttempts = (power(radix, maxLen) - 1)*radix /(radix-1);
    
    return maxAttempts;
  }
  
  //utility function to calculate powers of integers
  private static long power(int base, int exp)
  {
    if(exp < 0)
    {
      return 1/power(base, -exp);
    }
    else if(exp == 0)
    {
      return 1;
    }
    else{
      long pow = 1;
      for(int p = 1; p <= exp; p++)
      {
        pow*=base;
      }
      
      return pow;
    }
  }
  
  //the main work horse of this program, breaking all possible numbers into combinations
  private static void resolveRadix(int len, long num)
  {
    long[] retVal = new long[len];
    
    int pow = 0;
    int i = -1;

    int radix = len;
    
    for(i = 0; power(radix ,i ) <= num; i++ );
    
    for(int j = 0; j < len - i; j++)
    {
      retVal[j] = 0;
    }
    
    for(int k = len - i; k < len; k++)
    {
      long t = power(radix, i - 1);
      if(i > 1)
      {
      
        retVal[k] = (long)((num - (num % t)) / t);
      
      }
      else
      {
        retVal[k] = (num % radix);
      }
      num -= (retVal[k] * t);
      
      i--;
    }
    
    char[] combo = new char[len];
    
    for(int j = 0; j < len; j++)
    {
      combo[j] = dict[(int)retVal[j]];
    }
    
    String str = new String(combo);
    
    final long attemptsVal = attempts.incrementAndGet();
    
    attempts.set(attemptsVal);
  }
  
  private void generate()
  {
    for(int length = 1; length <= maxLen; length++)
    {
      int radix = dict.length;
      
      long max = (long)power(radix, length);

      for(int i=0;i<max;i++)
      {
        resolveRadix(radix, i);
      }
    }
    
  }
  
  public void run()
  {
    generate();
    
    synchronized(locker)
    {
      locker.notify();
    }
      
    ex.shutdownNow();
    
  }
  
  public static void main(String[] args)
  {
    
    ex = Executors.newSingleThreadExecutor();
    
    maxLen = 6;
    
    long atts = getMaxAttempts(dict.length, maxLen);
    
    StringGenerator threads = new StringGenerator();
    
    long start = System.currentTimeMillis();  //execution start time
    
    ex.execute(threads); //execute code parallelly
    
    try{
        
      synchronized(locker)
      {
        locker.wait();
      }
    }
    catch(InterruptedException ie)
    {
      ie.printStackTrace();
    }
    
    long attemptsVal = attempts.get(); //final total number of attempts
    
    long end = System.currentTimeMillis(); //execution end time
    
    double speed = (double)((1000 * attemptsVal)/(end - start)); //rate of generating combos
    
    double seconds = (double)(end - start) / 1000;
    
    System.out.println("per sec = "+speed);
    
    System.out.println("sec = "+seconds);
    
    System.out.println("words = "+attemptsVal);
    
    System.out.println("max words = "+atts);
    
  }
}

Execution after compilation is shown below:

Leave a Reply

Your email address will not be published. Required fields are marked *