IsAnagram bug (per element counts)

Open Beginner friendly
#153 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
2/5
Estimated time
1-3 hours
Newbie friendliness
70/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Stale
Domain
testing-qa

Research direction

The issue is in the Permutations.IsAnagram method. Look at the unit tests to understand the current behavior. The bug is that it doesn't check per-element counts. The fix involves updating the algorithm to count occurrences of each character. The provided external link shows a corrected implementation. Add the failing test case first, then modify the method to pass it.

Written by the indexing model from the issue text.

Description

Describe the bug

The IsAnagram function is not checking per-element counts. It is only checking if they have the same elements, but not if the count of each element matches.

A more appropriate name for the current logic is something like ContainsNoDifferingElements or IntersectsMatch rather than IsAnagram. I would recommend changing the name or the logic of the method.

Note: If you aren't going to check per-element counts, then you should also get rid of this check in IsAnagrams:

if (source.Length != other.Length)
    return false;

because length doesn't matter if you don't also check per-element counts.

To Reproduce

Add the following case to the IsAnagram unit tests:

string aab = "aab";
string abb = "abb";
Assert.False(Permutations.IsAnargram(aab, abb));
Expected behavior

Spans of the same length and elements but different per-element counts should not be considered re-orders/anagrams of each other.

Environment:

master branch

Additional context

I have written my own version of this algorithm in C# (that fixes this issue) if interested here...

Source Code: https://github.com/ZacharyPatten/Towel/blob/d2660e208ad3a44ab22f192834760c5b93dc82ac/Sources/Towel/Statics-SequenceAnalysis.cs#L1321
Examples: https://github.com/ZacharyPatten/Towel/blob/d2660e208ad3a44ab22f192834760c5b93dc82ac/Examples/BasicsAndExtensions/Program.cs#L406
Testing: https://github.com/ZacharyPatten/Towel/blob/d2660e208ad3a44ab22f192834760c5b93dc82ac/Tools/Towel_Testing/Statics.cs#L2086
Note: MapHashLinked is my version of a Dictionary if you look at the source code.

Dominant language
C#
Stars
6.2k
Forks
1.4k
No merged PRs in 30d

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from aalhour/C-Sharp-Algorithms

All issues in aalhour/C-Sharp-Algorithms

Similar issues

More C# issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.