The problem asks us to brands of length N with unique characters from a supplied set of characters for each letter position. The easy way to do this is to use recursion -- a subroutine that calls itself. Each call to the subroutine processes one more character slot in the output brand. The subroutine prints out the brand when the final slot is filled in. The subroutine is not called if an unused character is not available.
Thus, each call to the subroutine concerns itself with the addition of a single character to the end of the code string. The subroutine's parameters are: the character slot to be filled and a bit-array of the characters that have been used. This is quite handy since the number of character slot can subscript a two dimensional array of available characters.
All characters are stored in arrays of characters -- NOT in Java strings. Why? Speed! Strings are much slower to access and manipulate than simple 1-D and 2-D character arrays.
Thanks to Jacob Steinhart for translating my code to Java. Comments in the code explain the rest of the algorithm.
import java.io.*; import java.util.*; public class brand3 { /* declarations and file boilerplate: */ static char[][] brandset; /* allowed chars for each row */ static int nbrandset, nbrandsmade; static char[] curstring; static char ch; static int lengths[]; static int start, finish; /* just print brands #start through #finish */ static PrintWriter outfile; /* the recursive routine 'search': */ static void search (int depth, int seen) { if (depth == nbrandset) { /* filled all slots? print ID! */ nbrandsmade++; if (start <= nbrandsmade && nbrandsmade <= finish) { for(int i=0; i<=nbrandset; i++) /* newline is stored at end of string */ outfile.print(curstring[i]); } if (nbrandsmade > finish) { /* we're done; gracefully exit */ outfile.close(); System.exit (0); } return; } /* not all slots filled, try to find a character for next slot: */ for (int i=0;i<lengths[depth];i++) { ch = brandset[depth][i]; /* potential character */ if ((seen & (1<<(ch-'A'))) != 0 ) continue; /* bitmap says already seen */ curstring[depth]=ch; /* assign this character */ search (depth+1, seen | (1<<(ch-'A'))); /* search for next, marking 'ch' as being used */ } } public static void main (String[] args) throws Exception { brandset = new char[15][]; curstring = new char[16]; lengths = new int[16]; BufferedReader infile = new BufferedReader(new ileReader("brand3.in")); int i; outfile = new PrintWriter(new BufferedWriter(new FileWriter("brand3.out"))); StringTokenizer st = new StringTokenizer(infile.readLine()); /* get all the input: */ nbrandset = Integer.parseInt(st.nextToken()); start = Integer.parseInt(st.nextToken()); finish = Integer.parseInt(st.nextToken()); for (i = 0; i < nbrandset; i++) { brandset[i] = infile.readLine().toCharArray(); lengths[i] = brandset[i].length; } curstring[nbrandset]='\n'; /* start the search */ search (/*depth:*/ 0, /*seen:*/ 0); outfile.close(); System.exit (0); } }