How to compare lines (one line random sequence)

Question

I want to compare 2 lines, but the one line is in a random sequence. I use text boxes, like this:

Textbox1:
friends
pals
elephant

Textbox2:
aspl

Now when I hit a button I want Textbox3 to show the following:

Textbox3:
pals

What I got so far:

            Textbox3.Clear();
            string[] lines1 = Textbox2.Lines;
            foreach (string line1 in lines1)
            {
                string[] lines = Textbox1.Lines;
                foreach (string line in lines)
                {
                    if (line.Contains(line1))
                    {

                        Textbox3.Text += line;
                        Textbox3.Text += "\r\n";
                    }
                }

             }

But this will only copy the line to Textbox3 if the line in Textbox1 and Textbox2 is totally identical, not just if the characters is identical.

So my question is: How do I do that?

Do you want to only copy lines over if they're in the same order? Or do you want to ignore order on the *lines* as well as the characters? — Merlyn Morgan-Graham, Aug 20 '11 at 20:19

score 1 · Answer 1 · answered Aug 20 '11 at 20:22

The way I would go about this is

Count the number of times each letter of your target word (textbox2) occurs
Loop through the list of possible entries (textbox1) you have
Count the number of times each letter of your possible entry occurs.
If match, save word to textbox3, if not, continue.

To make this process even faster, as already pointed out, count the length of the string of the possible word first, if no match, then abandon this word and continue onto the next.

A further enhancement, when counting the letters of the possible entries, if you find a letter that is not in your target word, then abandon, and continue to the next word.

Eddy · Accepted Answer · 2011-08-20T21:10:58.957

Simply sort the strings and compare the results assuming they are equal length and not null this works:

    private static bool IsPermutation(string one, string two)
    {
        var oneSorted = String.Join("", one.OrderBy(c => c).Select(x => x.ToString()).ToArray());
        var twoSorted = String.Join("", two.OrderBy(c => c).Select(x => x.ToString()).ToArray());

        return oneSorted == twoSorted;
    }

EDIT: To answer the comment. Add that method to your class and replace the code inside your foreach with

if (line.Length == line1.Length && IsPermutation(line, line1)) 
{
   Textbox3.Text += line;
   Textbox3.Text += "\r\n";                    
}

This looks pretty good, but can you please explain how to use it? — Peter, Aug 20 '11 at 21:04

score 0 · Answer 3 · answered Aug 20 '11 at 20:16

0

I would iterate through both lists. If the length of the strings is the same, continue (potential match). Given a potential match (same string lengths), then iterate through the characters in the source string, and ensure each exists in the string you are comparing it with.

answered Aug 20 '11 at 20:16

Nathanial Woolls

5,231
24
32

He hasn't specified if he cares about the order of the lines. I know the existing code requires them to be in the same order, but that doesn't mean that this is actually what the OP is looking for. BTW, I didn't down-vote... – Merlyn Morgan-Graham Aug 20 '11 at 20:20
This fails unless you remove matched chars from the string. If you don't then aabc will match with abbc (each char in aabc exists in abbc and the strings are equal length). – Eddy Aug 20 '11 at 20:39

score 0 · Answer 4 · edited May 23 '17 at 11:47

0

You'll have to generate all the possible permutations of the random input and then compare each against the data. Like Nathaniel said you can optimize it by checking lengths first.

See http://msdn.microsoft.com/en-us/magazine/cc163513.aspx for code that generates string permutations (you'll want to get all character permutations of the random input string)

Edit

An answer to the question: Listing all permutations of a string/integer has a permutation generator that is more suited to your needs. Just add a List<string> parameter to the go and setper methods and replace Console.Write (list); with results.Add(list). When the method returns, the list you provided will have all the permutations.

edited May 23 '17 at 11:47

Community

1
1

answered Aug 20 '11 at 20:18

Nithin Philips

331
1
6

No down-vote, as this would work. But you absolutely don't have to do that. Something much faster would be to count the characters and stuff them into a dictionary of char -> count, then compare the dictionaries. – Merlyn Morgan-Graham Aug 20 '11 at 20:22
Come to think of it, a SortedList would work too. I agree that permutations will be extremely slow for any string of a sizable length. – Nithin Philips Aug 20 '11 at 20:31
I bet this would work, but its so complicated I can't make the code make any sense to me.. – Peter Aug 20 '11 at 20:59

How to compare lines (one line random sequence)

4 Answers4