2
$\begingroup$

Firstly, thank you for looking at my question.

I would like to know what this kind of problem is called in mathematics:

Given a set of letters, find all possible 'words' you can make with those letters. For example for 'abc' the solution would be:

a, b, c, ab, ac, abc, ba, bac, bca, ca, cab, cba

Some background, I am writing a computer program to play Scrabble and need to generate all possible words given from a set of letters. I'm researching algorithms for this problem but couldn't quite figure out what the general name is for this type of problem. I'm curious to find out so I thought I would ask.

I thought this was a type of permutation problem but reading up on Permutations I see that the length of the result is set, not variable. And it's not a Combination since the order matters.

  • 3
    Where are `bc`, `cb`, and `acb`? Did you leave those out on purpose or by mistake?2012-10-21
  • 1
    (Supposing that it was by accidents, what you want is called "all the permutations of a subset of a multiset of letters. The "multiset" might be important, since for Scrabble you might have more than one of a certain letter.2012-10-21
  • 0
    It is permutations because like you said -- order matters. If you apply the permutation formula you will get a number of permutations not a set and certainly not a variable.2012-10-21
  • 0
    Since you are interested in actual words you need something else. You need some kind of an algorithm that distinguished between words and meaningless strings of letters.2012-10-21
  • 1
    Obviously we would just compare his possible words against some word list.2012-10-21
  • 0
    The essential thing is not the name, but the exact definition of acceptable words (e.g., whether a word may contain the same letters more than once) and which "combinations" of letters count as the same word.2012-10-22

2 Answers 2