Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #141934
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Anagrams |
| Date | 2019-03-13 15:15 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87muly7qmi.fsf@bsb.me.uk> (permalink) |
| References | (2 earlier) <aef0988f-9023-4294-96d1-f1f4ba1d214b@googlegroups.com> <q68gi2$kgc$1@news.xmission.com> <5SVhE.204037$U64.101380@fx20.am4> <875zsn800y.fsf@bsb.me.uk> <56392276-db00-48a6-bfec-654c4ec88ae9@googlegroups.com> |
Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> On Wednesday, 13 March 2019 11:52:06 UTC, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:
>>
>> > (Alternative algorithm: sort s and t, and compare for equality. The
>> > above was simpler to write.)
>>
>> Another algorithm just counts the frequencies. I think it's simpler to
>> write than either of the others:
>>
>> bool anagram(const char *s1, const char *s2)
>> {
>> long int count[CHAR_MAX - CHAR_MIN + 1] = {0};
>> while (*s1 && *s2) {
>> count[*s1++ - CHAR_MIN] += 1;
>> count[*s2++ - CHAR_MIN] -= 1;
>> }
>> if (*s1 || *s2)
>> return false;
>> for (size_t c = 0; c < sizeof count / sizeof count[0]; c++)
>> if (count[c])
>> return false;
>> return true;
>> }
>>
>> One could just count letters, which would make the count array smaller,
>> and at the risk of non-portability to peculiar architectures, the last
>> four lines could be simply:
>>
>> return !memcmp(count, (char [sizeof count]){0}, sizeof count);
>>
> That one assumes 8 bit chars, unless you're prepared to gobble memory
> and runtime.
It doesn't assume 8-bit chars. For example, it would not gobble up much
memory with 9-bit chars. I think you mean that it assumes that
characters are represented by single chars, and that a char won't be
very wide.
> Also, even with 8 bit chars, it's not especially fast
> for short anagrams, which crossword puzzles usually are. Speed can be
> important if you're searching a database of all English words for
> an anagram.
I was suggesting an improvement on the algorithms that had been proposed
so far. I don't think you'd use any general "is this pair an anagram"
function for the case you describe here. Testing one string against
many is always going to be faster using some other function.
> 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.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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