3

I am working on an unscramble type program where a user is able to input random letters and the program iterates through the letters and a wordlist to try and find words that contain these some or all random letters in the wordlist.

For example:

if Input = "sasdfle"
words found in wordlist = "sad", "fleas", "flea", etc...

Words can only contains letters that are input from the user and each letter cant be repeated. I have found multiple questions on here that find anagrams but I cant seem to find an algorithm that will do what I stated above.

I don't want to post the whole code here but here is the main part that I am having trouble with:

re.m7
  • 85
  • 6
  • 1
    can you show us what you have tried on your own..? there are some examples out there but I am sure others would like to see what you are currently doing vs just providing you a quick answer.. what have you tried ? – MethodMan Sep 11 '16 at 18:21
  • Consider posting your code about what you tried so far – Rahul Sep 11 '16 at 18:28
  • I updated the post. I hope its clear. – re.m7 Sep 11 '16 at 18:40

1 Answers1

3

Providing that you have an appropriate English words collection, e.g. 

private static HashSet<String> s_Words = new HashSet<String>() {
  "abacus",
  //...
  "flea",
  "fleas",
  //...
  "sad",
  "sea",
  // ...
  "zoom",
};

you can convert it into more convenient aggregated dictionary with key being an initial string with all letters sorted within it ("flea" => "aefl", "sad" => "ads" etc.). If two or more words have the same key, they should be combined into a collection, say, an array: 

"ale", "lea" => "ael" : ["ale", "lea"]

You can implement such a dictionary via Linq:

private static Dictionary<String, String[]> s_Dict = s_Words
  .Select(word => new {
    Key = String.Concat(word.OrderBy(c => c)),
    Value = word})
  .GroupBy(item => item.Key, item => item.Value)
  .ToDictionary(chunk => chunk.Key, chunk => chunk.ToArray());

Then given a string 

String Input = "sasdfle"

all you need to do is to sort it and check just 256 (2 ** (length + 1) == 256) combinations including and excuding each letter:

string source = String.Concat(Input.OrderBy(c => c)); 

// all combinations of the set with empty one excluded, see
// http://stackoverflow.com/questions/30081908/c-sharp-linq-combinatorics-all-combinations-of-a-set-without-the-empty-set/30082360#30082360  
var result = Enumerable
  .Range(1, (1 << source.Length) - 1)
  .Select(index => string.Concat(source.Where((item, idx) => ((1 << idx) & index) != 0)))
  .SelectMany(key => {
     String[] words;

     if (s_Dict.TryGetValue(key, out words))
       return words;
     else
       return new String[0]; })
  .Distinct() // some words can be built in many ways
  .OrderBy(word => word);
//.ToArray(); // if you want to represent words as array

Test

Console.Write(String.Join(Environment.NewLine, result));

will return

flea
fleas
sad
sea
Dmitry Bychenko
  • 180,369
  • 20
  • 160
  • 215
  • I haven't written in LINQ before so it makes it complicated trying to read the code. Can you maybe add some comments to some of the code so I can understand it? Or maybe look at my code and see what I could be doing wrong. – re.m7 Sep 11 '16 at 20:54
  • @re.m7: *Linq* is just a convenient way to solve the problem, you can well create an aggregated dictionary as well as subsets with loops. The only complex part of the code is in the last query `var result = Enumerable.Range(...).Select(...).`, which is generating all subsets from the given set with empty one excluded. See my answer http://stackoverflow.com/questions/30081908/c-sharp-linq-combinatorics-all-combinations-of-a-set-without-the-empty-set/30082360#30082360 for details – Dmitry Bychenko Sep 11 '16 at 21:13