C#: Find all permutations of a string, parse a dictionary, cheat at Scrabble.

This program has been expanded in a later post:
C#: Scrabble Player; Part 2 – Find all permutations of a string, parse a dictionary, cheat at Scrabble.

Find all possible permutations of a string.  Parse an XML dictionary http://www.ibiblio.org/webster/.  Compare permutations with dictionary and display results.  Ofcourse, the following program will only find words the same length as letters inputted.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;
using System.Text.RegularExpressions;
using System.Collections;
namespace ScrabblePlayer
{
public partial class Form1 : Form
{
private LinkedList dictionary = new LinkedList();
public Form1()
{InitializeComponent();}
private void btn_Scrabble_Click(object sender, EventArgs e)
{
txtPossibleWords.Clear();
dictionary.Clear();
char[] alphabet = {‘A’,’B’,’C’,’D’,’E’,’F’,’G’,’H’,’I’,
‘J’,’K’,’L’,’M’,’N’,’O’,’P’,’Q’,’R’,’S’,’T’,’U’,’V’,’W’,’X’,’Y’,’Z’ };
if (dictionary.Count == 0)
{
for (int i = 0; i < alphabet.Length; i++)
{
StreamReader wordStream;
wordStream = File.OpenText(“C:\\dictionary\\” + alphabet[i] + “.xml”);
string fullXMLList = “”;
fullXMLList = wordStream.ReadToEnd();
wordStream.Close();
MatchCollection wordCollection =
Regex.Matches(fullXMLList, @”(.*?)”, RegexOptions.Multiline);
for (int j = 0; j < wordCollection.Count; j++)
{
dictionary.AddLast(Regex.Replace(wordCollection[j].ToString().ToLower(),
“||\\.|\\]|\\[|,|\\?|:|\\(|\\)|;|-|!|\\*|\”|`”, “”));
}
}
}
string inputLine = txtLetters.Text;
Recursion rec = new Recursion();
rec.InputSet = rec.MakeCharArray(inputLine);
rec.CalcPermutation(0);
LinkedList combo = rec.getComboList();
label2.Text = “ditionary total: ” + dictionary.Count;
label3.Text = “combination total: ” + combo.Count;
foreach (var word in combo)
{
if(dictionary.Contains(“”+word))
{
txtPossibleWords.Text += word + “\r\n”;
}
}
}
}
/*
The “Recursion” class below, is written in c# by Gary Stafford
posted at http://www.codeproject.com/KB/recipes/Premutations.aspx
whom references

Algorithm Source: A. Bogomolny, Counting And Listing
All Permutations from Interactive Mathematics Miscellany and Puzzles
http://www.cut-the-knot.org/do_you_know/AllPerm.shtml,
* Accessed 11 June 2009
whom references

1. A. Levitin, Introduction to The Design & Analysis of Algorithms,
* Addison Wesley, 2003
2. E. W. Dijkstra, A Discipline of Programming,
* Prentice-Hall,
3. R. Sedgewick, Algorithms in C, Addison-Wesley,
* 3rd edition (August 31, 2001)
*/
class Recursion
{
private int elementLevel = -1;
private int numberOfElements;
private int[] permutationValue = new int[0];
private string txtCombo = “”;
private LinkedList comboList = new LinkedList();
private char[] inputSet;
public char[] InputSet
{
get { return inputSet; }
set { inputSet = value; }
}
private int permutationCount = 0;
public int PermutationCount
{
get { return permutationCount; }
set { permutationCount = value; }
}
public char[] MakeCharArray(string InputString)
{
char[] charString = InputString.ToCharArray();
Array.Resize(ref permutationValue, charString.Length);
numberOfElements = charString.Length;
return charString;
}
public void CalcPermutation(int k)
{
elementLevel++;
permutationValue.SetValue(elementLevel, k);
if (elementLevel == numberOfElements)
{
OutputPermutation(permutationValue);
}
else
{
for (int i = 0; i < numberOfElements; i++)
{
if (permutationValue[i] == 0)
{
CalcPermutation(i);
}
}
}
elementLevel–;
permutationValue.SetValue(0, k);
}
private void OutputPermutation(int[] value)
{
string word = “”;
foreach (int i in value)
{
txtCombo +=(inputSet.GetValue(i – 1));
word += (inputSet.GetValue(i – 1));
}
txtCombo += “\r\n”;
if (comboList.Contains(word)){}
else
{comboList.AddLast(word);}
PermutationCount++;
}
public string getCombo()
{ return txtCombo; }
public LinkedList getComboList()
{ return comboList; }
}
}

Leave a Reply

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