Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #141947

Re: Anagrams

Show all headers | View raw

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Wednesday, 13 March 2019 15:15:14 UTC, Ben Bacarisse  wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>> 
>
>> > I use a subroutine called strcount(). This goes through the string
>> > counting instances of a passed character. You then simply step through 
>> > the strings checking that counts match. So it's O(N^2) in the case
>> > of a match, but usually returns quickly on a non-match.
>> 
>> Can you post the code?  I may be misunderstanding something, but it
>> sounds like you are a targeting a particular kind of use.
>> 
>> -- 
>> Ben.
>
> It is my program "Crossword Designer"
>
> https://sourceforge.net/projects/crossworddesign/
>
> static int isanagram(char *str1, char *str2)
> {
>   int i;
>
>   if(strlen(str1) != strlen(str2))
>     return 0;
>   for(i=0;str1[i];i++)
>     if(strcount(str1, str1[i]) != strcount(str2, str1[i]))
> 	  return 0;
>   return 1;
> }
>
>
> (strcount() just counts the instances of ch in str)
>
> The anagrams have to fit into a crossword and are checked against a
> dictionary of English words, which contains hundreds of thousands of
> entries. It needs to check the entire list in just noticeable time.
> But the words are unlikely to go over 12 characters.

Thanks.  I think I did misunderstand what you meant.  The algorithm is
designed for rare matches (as is usually the case for natural language)
but does not exploit the fact that many words are being tested against a
single word.

-- 
Ben.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

As the Web Turns 30, Its Inventor Explains 3 Ways It Went Wrong—and How to Fix It "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-03-12 20:06 +0800
  Re: As the Web Turns 30, Its Inventor Explains 3 Ways It Went Wrong—and How to Fix It gazelle@shell.xmission.com (Kenny McCormack) - 2019-03-12 12:12 +0000
    Re: As the Web Turns 30, Its Inventor Explains 3 Ways It Went Wrong—and How to Fix It "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-03-12 20:25 +0800
      Re: As the Web Turns 30, Its Inventor Explains 3 Ways It Went Wrong—and How to Fix It Martin Edwards <buzzard554@fastmail.co.uk> - 2019-03-13 07:14 +0000
        Re: As the Web Turns 30, Its Inventor Explains 3 Ways It Went Wrong—and How to Fix It "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-03-13 19:39 +0800
        Re: As the Web Turns 30, Its Inventor Explains 3 Ways It Went Wrong—and How to Fix It Wolf K <wolfmac@sympatico.ca> - 2019-03-13 10:59 -0400
          Re: As the Web Turns 30, Its Inventor Explains 3 Ways It Went Wrong—and How to Fix It Martin Edwards <buzzard554@fastmail.co.uk> - 2019-03-14 07:18 +0000
    Re: As the Web Turns 30, Its Inventor Explains 3 Ways It Went Wrong—and How to Fix It Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-03-12 06:40 -0700
    Re: As the Web Turns 30, Its Inventor Explains 3 Ways It Went Wrong—and How to Fix It "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-03-12 07:32 -0700
      Another Crackpot Production... gazelle@shell.xmission.com (Kenny McCormack) - 2019-03-12 14:43 +0000
        Re: Another Crackpot Production... "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-03-12 08:24 -0700
          Re: Another Crackpot Production... fir <profesor.fir@gmail.com> - 2019-03-12 09:30 -0700
            Re: Another Crackpot Production... fir <profesor.fir@gmail.com> - 2019-03-12 09:42 -0700
            Re: Another Crackpot Production... "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-03-12 09:54 -0700
              Re: Another Crackpot Production... fir <profesor.fir@gmail.com> - 2019-03-12 10:10 -0700
                Re: Another Crackpot Production... "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-03-12 10:29 -0700
                Re: Another Crackpot Production... fir <profesor.fir@gmail.com> - 2019-03-12 10:45 -0700
        Anagrams (was: Re: Another Crackpot Production...) Bart <bc@freeuk.com> - 2019-03-12 21:51 +0000
          Re: Anagrams (was: Re: Another Crackpot Production...) Eli the Bearded <*@eli.users.panix.com> - 2019-03-13 00:22 +0000
            Re: Anagrams Bart <bc@freeuk.com> - 2019-03-13 11:20 +0000
              Re: Anagrams Eli the Bearded <*@eli.users.panix.com> - 2019-03-14 20:25 +0000
                Re: Anagrams Learn to Filter you e-tard <cdalten@gmail.com> - 2019-03-15 08:02 -0700
                Re: Anagrams Wouter Verhelst <w@uter.be> - 2019-03-15 17:11 +0200
          Re: Anagrams (was: Re: Another Crackpot Production...) Ike Naar <ike@iceland.freeshell.org> - 2019-03-13 07:28 +0000
            Re: Anagrams Bart <bc@freeuk.com> - 2019-03-13 10:50 +0000
          Re: Anagrams Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-03-13 11:51 +0000
            Re: Anagrams Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-03-13 06:10 -0700
              Re: Anagrams Bart <bc@freeuk.com> - 2019-03-13 14:50 +0000
              Re: Anagrams Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-03-13 15:15 +0000
                Re: Anagrams Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-03-13 08:42 -0700
                Re: Anagrams Bart <bc@freeuk.com> - 2019-03-13 16:17 +0000
                Re: Anagrams Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-03-14 01:23 +0000
  2001: A Space Odyssey - HAL 9000 "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-03-13 20:28 +0800
    Re: 2001: A Space Odyssey - HAL 9000 Martin Edwards <buzzard554@fastmail.co.uk> - 2019-03-14 07:19 +0000
      Re: 2001: A Space Odyssey - HAL 9000 "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-03-14 22:30 +0800
        Re: 2001: A Space Odyssey - HAL 9000 gazelle@shell.xmission.com (Kenny McCormack) - 2019-03-14 14:32 +0000
          Re: 2001: A Space Odyssey - HAL 9000 "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-03-14 07:50 -0700
          Re: 2001: A Space Odyssey - HAL 9000 "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-03-15 00:16 +0800

csiph-web