Re: generating unique letter combinations

From: Ian Woods (newspub2_at_wuggyNOCAPS.org)
Date: 11/11/03 

Date: Tue, 11 Nov 2003 00:05:24 +0000 (UTC)

Thad Smith <thadsmith@acm.org> wrote in news:3FAFCFD7.9A1BABCE@acm.org:

> Ian Woods wrote:
>>
>> "Jason" <jason.carney1@btinternet.com> wrote in
>> news:boodpd$e3a$1@hercules.btinternet.com:
>>
>> > I want to be able to generate all unique combinations of a string,
>> > for example, abc = abc, ab, ac, bc, a, b, c for any length string.
>> > Is there an algorithm that is well known and efficient for this or
>> > should i just make something up?
>>
>> It's called counting. Instead of counting numbers, you count letters
>> instead. If your character set has all of the letters contiguous
>> (like ASCII), you can merely count in an array so that each value is
>> between 0 and the number of letters, and then add the base value of
>> the first letter.
>
> Counting in this manner would generate duplicate combinations, such as
> ab and ba. There might also be an issue of duplicate letters,
> although the OP didn't mention it, such as "aabc" allowing aab, but
> not abb or aaab.

Yes, you're right. I'd misread the example the OP posted so my response
is not as good as it could have been. I'm glad it's not completely off-
target!

> If each letter is unique, the easiest way to generate all unique
> combinations is to associate a bit with each letter, then count in
> binary, substituting the corresponding letter for each 1 bit.

Indeed. I think it might be useful to generalise the idea because there
are a number of common problems all solvable by 'counting'.

The general form has two components: the counter and a function which
creates solutions from a counter value. The tricky bit is coming up with
the function.

My solution earlier shows a mapping from a counter to a string produced
from a set of symbols, with repetitions.

Thad's solution shows a mapping from a counter to a string produced from
a list of symbols which are only produced in order.

There's bound to be other useful ones out there. Would anyone care to
share so more?

I know I could certainly benefit from hearing mappings from others since
I usually wind up 'playing around' until I create a function I need.
 
Ian Woods

Relevant Pages

  • Re: How to examine tokens?
    ... Okay, I was a little vague about the project, it's not just counting ... letters, it has to figure out how many letters are in each word, how ... compare this damn tokento a character. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Help on word counting
    ... For a Text field in a FileMaker database, then counting the words and ... letters is fairly easy. ... question marks, exclamation marks, etc. ... text into separate words and then count or summarise (using Summary ...
    (comp.databases.filemaker)
  • Re: generating unique letter combinations
    ... > example, abc = abc, ab, ac, bc, a, b, c for any length string. ... Instead of counting numbers, you count letters ... If your character set has all of the letters contiguous (like ...
    (comp.programming)
  • Re: range in ascii
    ... But counting the letters I have declared my ... > upper case letters and other ASCII char. ... How should I declare my range ...
    (comp.lang.ada)
  • Re: flac/mp3 tagging Latin characters
    ... The standard way of encoding Latin letters is the ASCII encoding. ... If and when it becomes universal, then character set ...
    (Fedora)