VB6: Best way to find all permutations of a given string in a file - Contest

Yes, Merri... You I know. But the whole concept was to get unconventional method that could be used to achieve the goal. I'm afraid they would be scared off by the whole focus on speed...

Contests that have speed involved would be better off without fully accounting my code in, because you could assume my participation automatically turns other potential participants off. Simply because they know I can come up with very fast code in many situatations. So I'd be ok for taking part in giving reference code.

Besides, if the prize would be something that isn't virtual, mailing it all the way to Finland would make you poor :D

Merri, mailing it to anyone else would make him poor I would say...I mean, he's probably the only person (or at least only one of a few) from Hawaii who posts here regularly :-P

And yeah, I agree with you about only taking part in these as a "guru" rather than actually taking part as a player. That or amateur and pro level competitions, but we don't have enough pros here (taking part) for that to work fairly...if I was in the pro league I'd definitely lose and I know it, I'm an amateur programmer and always will be (unique and original sometimes, but amateur always :-))

A project like this needs a bit more planning among the people taking part too. I noticed that the rules changed from day to day as it was progressing with new rules being added all the time (like 64k block size, saving not being a part of the timing, etc) and that didn't help :-P

smUX,

The rules never changed, you just have to READ them. It was all there in writing. But remember who got the file size wrong even though it was in writing and that NEVER changed (100mb instead of 10mb) :-)

Quote:

---

Originally Posted by smUX

Merri, mailing it to anyone else would make him poor I would say...I mean, he's probably the only person (or at least only one of a few) from Hawaii who posts here regularly :-P

---

And what does me living in Hawaii have to do with it???

Quote:

---

Originally Posted by randem

smUX, The rules never changed, you just have to READ them. It was all there in writing.

---

So how come the original post changed more times than a politician's promises? The 64k block size was never in the original post when I first started writing the code, that was an added rule

Quote:

---

Originally Posted by randem

But remember who got the file size wrong even though it was in writing and that NEVER changed (100mb instead of 10mb) :-)

---

You did, why? I think if you follow your own suggestion of READING you might find when I said I was going to test out my prog with a 100MB file and Merri did the same when I did so...neither of us thought for a second that you said 100MB file

Quote:

---

Originally Posted by randem

And what does me living in Hawaii have to do with it???

---

So you can send a parcel to any country for a low price? Certainly worth knowing, and I am sure you could earn tons selling this service to the companies in the US spending millions on international postage!

As far as I am aware, US postage rates are exactly the same in all 50 states, regardless of the destination.

Even to Finland, the UK, Germany, Australia...and other international destinations? That's why I said any *country*...the US *is* a country, and you're talking about states now

I can see it is summer and global warming is having side effects. Please enjoy a very cold ice tea.

*looks at his avatar*

Humm, maybe being hot is ok.


(Read: less off, more topic, please)

Question: should the code work with more than one of some specific character? Ie. "aabb" doesn't work with my code (but it does work with the InStr and Replace versions I made, although I haven't tested that).

Yes, The original characters were different but it should work with repeating characters to be a true permutation processor.

My code would find "aabb" 4 times (with the 4 different permutations) but would cancel out successive doubles...I assume that would be the right thing to do :-)

???? aabb has 6 different permutations... What do you mean???

Looks like I have some more work to do then.

Well, each permutation comes up 4 times the same I mean...aabb, abab, abba, bbaa, baba and baab will all come up 4 times in the permutations list

Edit: Correction...With *my* code, the permutator would throw all permutations out because it checks for doubles in the string. I was talking theoretically above, and realised that I was wrong in *my* case. I probably need to work on a better way to do this in future, but the permutator isn't a part of the main project anyway :-)

I think I have an idea for a way to efficiently generate the strings effectively...and it isn't much work at all to do :-)

Very Wrong... Permutation are part of the project. How can you find them if you cannot create a proper permutation list. The "asdf" is just the main example. Ones program "AS NOTED IN THE THREAD TOPIC" is to find ALL permutations of a given string not a Hard Coded or Fixed one...

BTW: The app posted that creates the test file will also create just the permutation of any given string also so that one can check if their permutation output is correct.

Just put your permutation string in and click the "Permutate String" button the output will go to the screen.

Quote:

---

Originally Posted by randem

How can you find them if you cannot create a proper permutation list.

---

Without saying how, all I can do is assure you that it is possible. My code finds all permutations of the input string within the file without determining what those permutations are. Merri mentioned that his code functions similarly.

Yup, although the need to detect two same characters in the permutation string made my original code null and void. Atm I have a slightly fixed code, but it gives too many results at the moment. Probably an error somewhere, this is what you get when you have to change existing logic to something else.

Although I believe randem wanted to say that with the assumption code needs the proper permutations in order to work, which is how smUX's code works, and what smUX means with the four he is talking about... well, I don't know what he means and randem assumes he is talking about the permutations, but I guess smUX isn't talking about that.

Life is complex.

Quote:

---

Originally Posted by randem

Very Wrong... Permutation are part of the project. How can you find them if you cannot create a proper permutation list.

---

However, the original post never stated that *generating* the permutations was a part of the project...the project is simply *finding* all permutations...

...although the modification I've made does generate all permutations of any given string so it's still within the requirements, as I stated above :-P

Quote:

---

Originally Posted by Merri

smUX means with the four he is talking about... well, I don't know what he means and randem assumes he is talking about the permutations, but I guess smUX isn't talking about that.

---

Putting it simply, if the string was "aabb" there are obviously 24 different permutations...6 different ones occuring 4x each...there's no point in looking for "aabb" 4 times when it'll be the same results as the first time...and the results (if programmed correctly anyway) would cancel out doubles...

...thus there's 6 permutations possible from "aabb". When I said 4 different permutations, I meant 4 different instances of the same permutation string (4 different instances of "aabb" for instance)

Logophobic,

Yes, I am well aware that finding all permutation without knowing what they are. I was referring to one post who is using the Brute force method. To clarify... When using the brute force method of finding permutation strings if you cannot generate the list correctly if you cannot create all the possible permutations.

Brute Force Method: Generating all possible permutations then checking for each different permutation.

Quote:

---

Originally Posted by Merri

Yup, although the need to detect two same characters in the permutation string made my original code null and void. Atm I have a slightly fixed code, but it gives too many results at the moment. Probably an error somewhere, this is what you get when you have to change existing logic to something else.

---

My situation is quite the reverse. My code originally handled duplicate characters in the input string properly, but removing the otherwise unnecessary checks improved speed significantly in the case of "asdf" where each character is unique. I guess I'll have to revert to the previous, slower code to maintain functionality.

Quote:

---

Originally Posted by Logophobic

My code originally handled duplicate characters in the input string properly, but removing the otherwise unnecessary checks improved speed significantly in the case of "asdf" where each character is unique. I guess I'll have to revert to the previous, slower code to maintain functionality.

---

Logo, the *milliseconds* saved by doing away with the unique checker really isn't an issue IMO...but if it's that bad, why don't you simply check to see if each character in the string is unique and if not then deal with the duplicates...if all are unique, skip the duplicate checking :-)

Milliseconds, indeed. The difference in time for the 10MB file was about 20 milliseconds. Believe it or not, this was significant. :)

My code has more or less retained it's speed this far, but of course it doesn't work correctly yet. Fixing the problem is a job for another day.

Logo, there should be no difference in time regardless of the size with regards to the unique checking *I* was talking about...I was talking about the different permutations generated from the original "asdf" (or other) string. Filesize shouldn't have any effect on this :-P

BTW, I went back to an old idea for my duplicate checking and it's proven to be very successful. I also rewrote the generation code to make it slightly faster :-)

TO ALL CONTESTANTS!!!

When you submit your module, please name your module with what method you are using to find the permutations (ex. FindUsingBruteForceInstr_randem. I do not want to have to decode or debug your app to find out. This is part of the requirements for the winner(s) also. Please send your files in .zip format.

Also please read the first post carefully... Especially


The winners will be determined by several methods:

1 - Speed
2 - Understandability (ease of verification)
3 - Readability (how the code was written and commented)
4 - Method used
5 - Originality


Please double check your work. I have already found glaring errors such as returning the wrong offsets and no permutations at those locations. Remember you MUST return the Offsets of the permutation and the Permutation at that offset. This is needed for verification. ALL CODE NEEDS VERIFICATION!

Thank you for your interest!

Randem, I'll send you my code today sometime...I use peerguardian (recently started) and found out that it's been blocking my access to VBF so haven't been able to get on...but I will get the code ready and send soon :-)

With the help of Merri, there is a new skeleton for your module to fit into. I made some changes so that testing would be easier (well for me anyway). If you code your module to these standards your module should plug and play with this skeleton.

The areas to note:

The Data Class clsContestants. This is where any flags are set for the module to take independent operation. You can set these flags in the call that calls your routine.

In the top of frmPermFunctBench there is an area to add your function name and the enum to be used as a key for it.

In the class clsContestantFunctions you can add the call to your function. Please adhere to the naming conventions.

Thank you and good luck.

Any questions...

You still added too much into the functions, 1.4 seconds vs. 5.8 seconds is a big difference when I run the 100 MB file (4.4 seconds only because of extra string array that holds the found permutations... this information could be figured out after the function call just as well).

An option for disabling output would be nice.

Without the output it is all worthless for there is not way to verify... That is why this is not only based on speed. I have verified that some code that has been submitted is wrong... It's fast but wrong and without the output... well... you know...

Which code did you test?

My own.

I didn't say to remove output completely. I said make it an option. The slow output makes it pain to test the bigger files, not to mention doing multiple tests for one function in a row to see the general speed of that specific function.

I still don't see what is the reason for outputting the string array of a found permutation. Can anyone else explain this to me? I just can't get my head to understand for what it is needed for. If returned offset positions are correct, then they're correct. The additional string array doesn't tell anything, it doesn't make the offsets more correct or more wrong. They just slow the execution down a lot when done within the processing function.

Just because one thinks the offsets are correct does not mean that they are. This has been checked repeatedly in some of the code submitted. It is a VERY EASY way to check the process, yet many refuse to check this output and therefore their code is WRONG. A simple check of the output would verify this before they submit. But since they are concentrating on speed hey WHY SHOULD THE OUTPUT BE CORRECT IT'S FAST!!!

Without the output the whole search would be useless... as Reagan once said "Trust but Verify"

I will put an option in the skeleton to omit the output but only for the submissions that actually pass verification. I will add a verification routine to the skeleton to allow for testing this since many don't do this before they submit.

Yes yes, I know that, but that isn't my point.

My point is that checking the offset array is enough to verify. It gives you 100% correctness, there is no need for the string array.

If the offsets are the same with the known correct offsets, what do you do with the string array?

Nothing.

That is the self verification... and besides what do you check the offset array against???? Am I supposed to trust that what is there just because someone states it is?

Besides it not JUST about the known offsets there is the possibility that there are other permutations in the file also. The whole process needs to be self verifying... If everyone did this before submitting I would not even have to mention it. BOTH need to be correct.

You make one function that you know that works correctly, like the InStr version, run it, store the output and run other codes results against that.

You can even make verifying much more automated, easier and fast that way, while keeping everything valid. Without the string array.


The current way you've done this doesn't work, you can see the result: telling people their code doesn't work correctly. You haven't made the verification process easy enough. People don't need to even see the results, I don't need to know the output in string format, you can make the computer do it for everyone.

(And people can and ought to know how to debug if their code doesn't work as it should.)

The point of the string output is to verify that what one says is there is there. That is the contest, that is the way it needs to be done. I want the code to show that it did what I asked.

If I get the output that offset 0005 points to asdf and the verification shows that 0005 point to asfd then the code is WRONG!!! Just using the offset would suggest that the code is correct. That is what this is all about.

That only would tell that there is a bug in the constuctor of the string array, not a bug in the code that finds the correct offsets where permutations are found.

Then that is wrong then... If I find a nickel and say it's a dime. What did I actually find without verification????

We don't need to verify like you've verified. We shouln'd need to re-verify functions you have provided.

If you provide a function and tell us to compare our results against the results of that function because that function gives correct results, well, that would be easier.

Looking through thousands of lines of string output isn't something people do. Not how matter how much you tell them to do so.

I am putting in a verification routine but it will still need the string output to verify against. But since I haven't created the verification process yet...

The reason I have to create the verification is solely because the submitters did not verify their codes output themselves.

E-mail now featuring improved code. And that by a big margin as I finally optimized a bit more than little. (And included my own verification/validation in it for a sample.)

OK, you don't need to return the permutation string, the offsets will do just fine. I will check the string at the offset for you in the Verification procedure.

I will post another skeleton soon...

BTW: I can't easily test your module if it does not have the same calling parameters as in the skeleton... I can't go thru 100 different calling and testing techniques. That is the purpose of the skeleton to create one user interface between all the submitted modules.

Example of a module using the Contestant Class. Start with mFindUsing the append your Method then underscore and your VBForums name. Please use the definitions in the class for the parameters that your subroutine needs. Modify lngOffset with your offset where you find the permutations.

Code:

---

Public Sub mFindUsingBruteForceInstr_randem(Contestant As Object, lngOffset() As Long)

    With Contestant
...
        ' If nothing found
        ReDim lngOffset(0) 
        lngOffset(0) = -1&
        .Count = 0

    End With

End Sub

---

The contestant class is as follows:

Code:

---

Option Explicit

Public Name As String
Public FunctName As String
Public Time As Long
Public OutputFile As String
Public Key As String
Public index As Long
Public Position As Long
Public SourceFile As String
Public FindStr As String
Public Chunksize As Long
Public CaseSensitive As Boolean
Public ReturnOffset As Boolean
Public Count As Long
Public OmitOutput As Boolean

---

The only item in the class your subroutine may modify is the Count variable All the rest are input for your module.

In clsContestantFunctions you add the call to your subroutine such as in:

Code:

---

Public Sub FindUsingBruteForceInstr_randem(Contestant As clsContestant, lngOffset() As Long)
    mFindUsingBruteForceInstr_randem Contestant, lngOffset  ' This is the call to your module
End Sub

---

In frmFuncBench add an enum to the ContestantEntries for your module and your VBForums name to EntrantNames along with your function name in FunctionNames (This name is the call to the sub in clsContestantFunctions).

After testing your module with the skeleton all you need to submit is the module.

Thanks.

Attachment removed see later posts for updated version.

Your project uses a reference called "RS General Routines" which is not included in the project. It also seems to have replacement procedures to basic functions such as String and Format.

Quote:

---

Originally Posted by randem

BTW: I can't easily test your module if it does not have the same calling parameters as in the skeleton... I can't go thru 100 different calling and testing techniques.

---

Why is that? You are using an extra wrapper there. My earlier submitted functions work with it like this:

Code:

---

Public Sub FindUsingInStr_Merri(Contestant As clsContestant, lngOffset() As Long)
    With Contestant
        lngOffset = mFindUsingInStr_Merri(.SourceFile, .FindStr)
    End With
End Sub

---

Also, this makes the functions much more general purpose, because when you force to pass a certain class in order to make things work, you effectively prevent the functions from working as standalone functions. Ie. you can't easily paste them to anywhere except into your skeleton program.

That's why I did my functions the way I did.

That very well may be. I will look into that.

Quote:

---

Originally Posted by Merri

Your project uses a reference called "RS General Routines" which is not included in the project. It also seems to have replacement procedures to basic functions such as String and Format.

---

Yes, I forgot about that dll. The whole thing was just meant for reference. I can post that dll so that everyone can test with it.

What replacements for String and Format are you referring too?

It seems the DLL includes those, because I got errors on those until I removed the DLL. I don't see any need for the DLL in the project.

Although there seems to be problems with the project, none of the functions I added to the constant strings in the form didn't show up, always seeing only four items in the combobox.

Show me what you added...

It does work..

I will change the calls to the way you suggested.

OK, here is the new skeleton with the changes...
clsContestantFunctions contains:

Code:

---

Option Explicit


Public Sub FindUsingBruteForceInstr_randem(Contestant As clsContestant, lngOffset() As Long)
    With Contestant
        lngOffset = mFindUsingBruteForceInstr_randem(.Sourcefile, .FindStr, .ChunkSize, False)
    End With
End Sub

Public Sub FindUsingBruteForceInstrRev_randem(Contestant As clsContestant, lngOffset() As Long)
    With Contestant
        lngOffset = mFindUsingBruteForceInstr_randem(.Sourcefile, .FindStr, .ChunkSize, True)
    End With
End Sub

Public Sub FindUsingBruteForceReplace_randem(Contestant As clsContestant, lngOffset() As Long)
    With Contestant
        lngOffset = mFindUsingBruteForceReplace_randem(.Sourcefile, .FindStr, .ChunkSize)
    End With
End Sub

---

So the submitted module never has to be changed.

In frmFuncBench change:

Code:

---

Public Enum ContestantEntries
    All
    RandemInstr
    RandemInstrRev
    RandemReplace
    EndOfEntries  ' Do not add after this entry insert before
End Enum

' These constants must match ContestantEntries coorespondingly

Private Const EntrantNames = "All,randem,randem,randem"  ' Add your name here for the number of cooresponding routines
Private Const FunctionNames = "All,FindUsingBruteForceInstr_randem,FindUsingBruteForceInstrRev_randem," & _
                                "FindUsingBruteForceReplace_randem"  ' add your routine names here

---

Attachment removed see later posts for updated version.

I added my module to the skeleton, and didn't have any problems running the first test. There are some bugs here, though.

First off, in cmdBenchmark_Click event, you need a Case -1 to avoid an error if no item is selected.

Next up, in the SetupContestants subroutine, you need to clear cmbContestant. Otherwise, you get duplicate items and run into trouble if you try to run All.

Finally, txtPerm doesn't function dynamically. I was scratching my head for a bit before I figured out that you have set the perm string before selecting a new file.

Another curiosity, when I tested on a file with embedded permutations of "aabc", I got these results, along with a lot of annoying 'permutations missing' message boxes.

Code:

---

Verified - FindUsingBruteForceInstr_randem finished in # ms, found 40569 permutations
Verified - FindUsingByteRange_Logophobic finished in # ms, found 40577 permutations

---

Do you remember the settings for creating the aabc file you used?

Ok, modifications made for those errors.

It also create a log file in the app folder named LogFile.txt from the contents of the main listbox (lstLog).

@Merri: It was a 5MB file with 500 permutations per buffer. I must have changed the seed, though, so I ran the test on a new file with the default 9756 seed.

Code:

---

Verified - FindUsingBruteForceInstr_randem finished in # ms, found 40581 permutations
Verified - FindUsingByteRange_Logophobic finished in # ms, found 40593 permutations

---

My InStr and MatchCount functions both return 40593.
My Replace function gives the same 40581 permutations as randem's InStr.

Yes, The replace functions cannot take into account overlapping permutations. Once you replace the data it's gone and the overlapping item is lost.

BTW, I've given up...this project's had too many changes to be enjoyable to me any more (which is the main reason why I took part originally)...Feel free to salvage my code and do as you wish with it

Results pending?