How to form combinations out of a random generated characters?

Question

I'm making a program in winforms application where in it generates random patterns with seven length of characters such as 2Vowels-5consonants, 3Vowels-4Consonants and so on..after which it generates random letters specific to the pattern generated..

After the letters are generated, I want to list all possible combinations of letters to that generated letters.. and try to check if the generated combinations are present on the system's dictionary..

-Sample Input-

Pattern : 3V-4C Letters: AIOLMNC Combinations: AIO AOL OIL .... MAIL .... CLAIM .... and so on...

-Output-

Words Found: OIL MAIL CLAIM ... and so on...

This program is intended for word games.. I'm asking for help and any suggestions that may help me to solve my problem. I can't think of proper way to start the algorithm and how to code it..

Answer 1

I don't normally do this, but I came up with an even better solution for your problem, and it deserves its own answer! This AnagramSolver solution is WAY more optimized than my other answer, because it doesn't create every-single-permutation of a word, and dictionary lookups are very optimized. Try it out:

Usage Example:

string[] dictionary = ReadDictionary(...);
var solver = new AnagramSolver(dictionary);

int minimumLength = 1;
IEnumerable<string> results = solver.SolveAnagram("AEMNS", minimumLength);

// Output the results:
foreach (var result in results)
{
    Console.WriteLine(result);
}
// Output example: 
// "NAMES", "MANES", "MEANS", "AMEN", "MANE", "MEAN", "NAME", "MAN", "MAE", "AM", "NA", "AN", "MA", "A",

Code:

public class AnagramSolver
{
    public AnagramSolver(IEnumerable<string> dictionary)
    {
        // Create our lookup by keying on the sorted letters:
        this.dictionary = dictionary.ToLookup<string, string>(SortLetters);
    }

    private ILookup<string, string> dictionary;

    public IEnumerable<string> SolveAnagram(string anagram, int minimumLength)
    {
        return CreateCombinations(anagram, minimumLength)
            // Sort the letters:
            .Select<string, string>(SortLetters)
            // Make sure we don't have duplicates:
            .Distinct()
            // Find all words that can be made from these letters:
            .SelectMany(combo => dictionary[combo])
            ;
    }

    private static string SortLetters(string letters)
    {
        char[] chars = letters.ToCharArray();
        Array.Sort(chars);
        return new string(chars);
    }

    /// <summary> Creates all possible combinations of all lengths from the anagram. </summary>
    private static IEnumerable<string> CreateCombinations(string anagram, int minimumLength)
    {
        var letters = anagram.ToCharArray();

        // Create combinations of every length:
        for (int length = letters.Length; length >= minimumLength; length--)
        {
            yield return new string(letters, 0, length);
            // Swap characters to form every combination:
            for (int a = 0; a < length; a++)
            {
                for (int b = length; b < letters.Length; b++)
                {
                    // Swap a <> b if necessary:
                    char temp = letters[a];
                    if (temp != letters[b]) // reduces duplication
                    {
                        letters[a] = letters[b];
                        letters[b] = temp;
                        yield return new string(letters, 0, length);
                    }
                }
            }
        }
    }

}

Here's a summary of the algorithm:

The basic idea is that every set of anagrams derive from the same set of letters.
If we sort the letters, we can group together sets of anagrams.
I got this idea from Algorithm for grouping anagram words.
For example, a set of anagrams ("NAMES", "MANES", "MEANS") can be keyed on "AEMNS".
Therefore, once we create our dictionary lookup, it's incredibly easy and fast to solve the anagram -- simply sort the letters of the anagram and perform the lookup.

The next challenge is to find all "smaller" anagrams -- for example, finding "NAME", "SANE", "MAN", "AN", "A", etc.
This can be done by finding all combinations of the anagram.
Combinations are much easier to find than permutations. No recursion is needed. I implemented complete combinations with 3 loops and a simple swap! It took a while to get the algorithm right, but now that it's cleaned up, it's very pretty.
For each combination found, we must again sort the letters and perform the lookup.

This gives us all possible solutions to the anagram!

Answer 2

  public static string RandomCharacters(int size = 5)
    {
        string alphabet = "abcdefgijkmnopqrstuvwxyz";
        Random ran = new Random();
       
       return       string.Join("",  (string.Join(',', alphabet.ToCharArray()) +
                     string.Join(',', alphabet.Reverse()) +
                     string.Join(',', alphabet.ToUpper().ToCharArray()) +
                     string.Join(',', shorturl_chars_ucase.ToUpper().Reverse())
                            ).Split(',')
                             .OrderBy(x => ran.Next(alphabet.Length * 4))
                             .Take(size)
                             .ToArray()
                              );
     }
        

RandomCharacters(10);

Answer 3

Update

This solution directly answers your question ("How do I form all combinations of characters"), but this is not a very efficient way to solve anagrams. I decided to create a better solution for solving anagrams, so please see my other answer.

---

This sounds like a fun puzzle.
To begin, here's how you can create your "random" inputs:

Random rng = new Random();
const string vowels = "AEIOU";
const string consonants = "BCDFGHJKLMNPQRSTVWXYZ";
string CreatePuzzle(int vowelCount, int consonantCount){
    
    var result = new StringBuilder(vowelCount + consonantCount);
    for (int i = 0; i < vowelCount; i++) {
        result.Append(vowels[rng.Next(5)]);
    }
    for (int i = 0; i < consonantCount; i++) {
        result.Append(consonants[rng.Next(21)]);
    }
    
    return result.ToString();
}

Then you'll need to create all permutations of these letters. This is a great job for recursion. The following code is an implementation of Heap's Algorithm that I found at http://www.cut-the-knot.org/do_you_know/AllPerm.shtml. Another helpful resource is http://www.codeproject.com/KB/recipes/Combinatorics.aspx

/// <summary>
/// Returns all permutations of the puzzle.
/// Uses "Heap's Algorithm" found at http://www.cut-the-knot.org/do_you_know/AllPerm.shtml
/// </summary>
IEnumerable<string> CreatePermutations(string puzzle) {
    // It is easier to manipulate an array; start off the recursion:
    return CreatePermutations(puzzle.ToCharArray(), puzzle.Length);
}
IEnumerable<string> CreatePermutations(char[] puzzle, int n) {
    if (n == 0) {
        // Convert the char array to a string and return it:
        yield return new string(puzzle);
    } else {
        // Return the sub-string:
        if (n < puzzle.Length) {
            yield return new string(puzzle, n, puzzle.Length - n);
        }
        // Create all permutations:
        for (int i = 0; i < n; i++) {
            // Use recursion, and pass-through the values:
            foreach (string perm in CreatePermutations(puzzle, n-1)) {
                yield return perm;
            }
            // Create each permutation by swapping characters: (Heap's Algorithm)
            int swap = (n % 2 == 1) ? 0 : i;
            char temp = puzzle[n-1];
            puzzle[n-1] = puzzle[swap];
            puzzle[swap] = temp;
        }
    }
}

Note that this algorithm doesn't check for duplicates, so an input like "AAA" will still result in 6 permutations. Therefore, it might make sense to call .Distinct() on the results (although the CodeProject article has an algorithm that skips duplicates, but is more complicated).

The final step, as you stated, is to check all permutations against your dictionary.

Optimizations

This solution is fairly simple, and will probably work really well if your puzzles remain small. However, it is definitely a "brute force" kind of method, and as the puzzle gets bigger, performance drops exponentially!