Generating combination of letters

Question

Hi All,

Given a set of letters, say from A.. F, how can one generate a combination of these letters for a specific length. i.e for length 4, generate all string containing these letters {AAAA, ABCD, ...} (duplicates included). I am not able to understand how to come out with a code that does it.This is pertaining to the Mastermind game that I am trying to simulate. Is there any algorithm to perform this generation.

regards,
darkie

Answer 1

There is an algorithm called Heap's Algorithm for generating permutations. This might suit your purposes. I found an example implementation here

Answer 2

I'm not sure what the name would be of such an algorithm, but it is a recursive one. That is, have a method that figures out one character, and simply keep calling itself until you're at the desired length of string that you want, then start filling in your array. Here's some sample C# code that should help:

    public void GetPermutations()
    {
        string currentPrefix = ""; // Just a starting point
        int currentLength = 1; // one-based
        int desiredLength = 4; // one-based
        string alphabet = "ABCDEF"; // Characters to build permutations from
        List<string> permutations = new List<string>();

        FillPermutations(currentPrefix, currentLength, alphabet, desiredLength, permutations);
    }

    public void FillPermutations(string currentPrefix, int currentLength, string alphabet, int desiredLength, List<string> permutations)
    {
        // If we're not at the desired depth yet, keep calling this function recursively
        // until we attain what we want.
        for (int i = 0; i < alphabet.Length; i++)
        {
            string currentPermutation = currentPrefix + alphabet[i].ToString();

            if (currentLength < desiredLength)
            {
                // Increase current length by one and recurse.  Current permutation becomes new prefix
                int newCurrentLength = currentLength + 1;
                FillPermutations(currentPermutation, newCurrentLength, alphabet, desiredLength, permutations);
            }
            else
            {
                // We're at the desired length, so add this permutation to the list
                permutations.Add(currentPermutation);
            }
        }
    }