Combinations and Permutations

[NotLKH]

Has anybody built a Combinations and Permutations Generator?
I'd like to see your code, perhaps pick up a better way of doing it.

Attached you'll find my version.

-Lou

[sql_lall]

Do you mind if it is in C++? Or does it have to be VB?
I guess i can transfer it, it would just be easier if i could give u the C++ version

[TheAlchemist]

hey NotLkH,
i have a pretty simple one(to calculate _nP_r) and the same for combinations but i have a feeling this is not what ur after.
if it is just give a shout and i'll post it.

[NotLKH]

Originally posted by sql_lall
Do you mind if it is in C++? Or does it have to be VB?
I guess i can transfer it, it would just be easier if i could give u the C++ version

I wouldn't mind C++, but since I don't "know" C++, I might get a little lost. But, Hey! Lets see the C!

Originally posted by TheAlchemist
i have a pretty simple one(to calculate nPr) and the same for combinations but i have a feeling this is not what ur after.
if it is just give a shout and i'll post it

Go ahead and Post it. Lets see how you handle factorial Multiplication/Factorial Division.

-Lou

[TheAlchemist]

NotLKH

i dont have that code right now, will get it to you by tomorrow. Here is something i did this afternoon. It gives all the possible combinations of 1s and 0s for a given string length.
for example, if the string length is 3, it will return
000,001,010,......

[NotLKH]

Hmm, I Like It!

-Lou

[transcendental]

This VB program finds combinations, using recursive.

It came from the article I wrote some months ago.

[NotLKH]

Originally posted by transcendental
This VB program finds combinations, using recursive.

It came from the article I wrote some months ago.

Not Bad!
Although, you do limit yourself do to the dimming of your array to 10. However, I limit Myself by useing a listbox, whose ULimit is 65000 +/-.

I don't even error check!

But, still, Good Code!

[NotLKH]

Now, if anyone's done this, please show us how!

Lets say you needed to do calculations on every combination {Or Permutation} of all sets of 3, 4, 5, ... n Long of a set of distinct numbers ranging from 3 to 63.

Now, you don't want to wait for all the sets to be returned before you start processing them.

What you want is to call the function, return an array of N numbers, process them, then requery, with your last return, to get the next.

In other words, Call a functuion and return 1 sequential combination per call.

I've worked this out already, {Its at work}. Have you?

-Lou

[Guv]

NotLKH: Here is a .zip file. When you unzip it, you will see three Readme files. All contain the same information. The .rtf (MS Word or Wordpad) and .wpd (WordPerfect) files are recommended. They have color coding and bolding to make them more readable. The VB files are also there. The Readme files refer to a self extracting file rather than a .zip file because that is how I usually send data.

I have coded a permutation generator which uses the best algorithm possible. Due to the huge number of possible permutations, you want the fastest possible algorithm.

This algorithm uses half exchanges to generate each successive permuation by an exchange of two elements. You cannot generate with less processing. The algorithm is illustrated in the Readme files.

For debugging, I coded a Kwiksort and an insert sort, which might be of interest. Kwiksort also uses half exchanges and is a very fast sorting algorithm.

I have not coded a combination generator and do not know the best algorithm.

BTW: I prefer an interface which allows the user to pick the characters to be permuted, but this is not a critical issue.

[Guv]

BTW: My permutation generator application has a one-at-a time option, which could be used to process each permuation as you generate them.

[transcendental]

Originally posted by NotLKH
Not Bad!
Although, you do limit yourself do to the dimming of your array to 10. However, I limit Myself by useing a listbox, whose ULimit is 65000 +/-.

I don't even error check!

But, still, Good Code!

Thank you!

FYI, the 2 permutation articles(VB) on Codeguru are here Maybe you want to consider writing an article like me (since VBWorld and CodeGuru are both owned by Jupitermedia Corp); I had not looked at the code posted here yet, I'm sick today.

I'm a C++ guy; I suxs too badly in VB. I wrote the VB version because quite a number of people emailed me to request for the VB version.

[NotLKH]

Hmmm,

So far, Trans has provided code to build String Combinations of n string characters taken M at a time, and Guv has provided code to build permutations of 5 string characters taken 5 at a time.

TheAlchemist has provided code to build Binary Strings,

and I've provided code to both build Integer Combinations and Permutations of n Integers {0 thru n-1} taken M at a time.

I would like to do some speed tests between your code, Guv, and Mine. Commenting out the Outputing code sections, and just time the pure permutations builder, over 1001 iterations, but it seems that you have a slight bug on your cmdAllAtOnce button, whereby you have to click it twice before it actually works.

Also you seem to have quite a few txt outputing going on, and I'm not sure whats safe to comment out.

But FYI, With Mine {See attachement}, when compiled to exe, on my system, it processes 1001 passes of complete generations of the purmutations of 5 integers taken 5 at a time in around .5 seconds.

I was able to time Transcendentals easily, and his produces ten thousand and 1 passes of all the combinations of 6 items taken 4 at a time in about 1.011 seconds, compiled.

Mine does the same in about .881 seconds.

Now, the Question:

You all are generating Combinations and Permutations on Strings.
How would you go about and do it on Integers or Longs?

-Lou


BTW, Attached is My attempt at altering My Code and Transcendentals to perform comparative speed tests.
Obviously, the fastest speeds are acheived after compilation.




-Lou

[TheAlchemist]

hey guys,
NotLKH
im having a bit of trouble reading and understanding your code. could you please post a commented version? i would appreciate it.
im glad you asked this questions, i have been thinking about this for a long time and didn't have a clue where to start. now with Guvs algorithm i do!!!!!! I havent found any bug with Guvs code, i just have to click once.

Guv
very interesting way of doing things!!!!

i found some ways to make my own code better: change all the inetger declarations in the click event of the command button to long. this way it can process longer strings. Is it advisable to add a doevents in the for loops? how would it affect performance?

hmmmm very interesting question NotLKH, how about just converting to the proper type after creating the strings? not very efficient.(this wouldnt work with very well with my code. Cint(001) = 1)

[NotLKH]

Originally posted by TheAlchemist
hmmmm very interesting question NotLKH, how about just converting to the proper type after creating the strings? not very efficient.(this wouldnt work with very well with my code. Cint(001) = 1)

True, I also believe it wouldn't be very efficient.
Besides, if you were building all the combinations of a group of numbers containing > 256 integers, useing Character representation, then you'd run out of chars!

If you look at my code, The only strings I'm building is for display purposes only. I'm not Building Combinations and Permutations on strings, but rather on arrays of integers directly, useing a form of ShiftMemory. Basically, as a Number is used in the Array, the array's elements to its right are copied to the left by 1, thus eliminating the numbers as they are used, and also shortening the range of elements left to draw from.

And, once used, when you back out, the number that was used is placed back into the source array at its original position by copying the array elements from its original postion thru the effective length of the array at that time to the right by 1, and then that number is put back in its spot.

I'll see about commenting my code, [propably by tomorrow].

[FYI: Since Mine uses Integers, I've always envisioned that I'm building Combinations and Permutations on Numbers that ultimately would be indexes of another array, which could contain any data type.]

-Lou

[Guv]

NotLKH: My application will handle more than permutations of 5 characters. Just type in a longer string.

I said my application was sloppy. I did it in a hurry to illustrate the algorithm to some friends of mine. I intended to clean it up and use a disk file to accommodate larger strings.

There is some condition which requires an annoying extra click. I have not used it for a while and forget some of the details.

TheAlchemist: I guess you read one of the Readme files for a description of the algorithm. 20 years or so ago, I wrote a PL/1 program to generate both permutations and combinations using a mainframe. I forgot the algorithm I used for combinations, but the permutation algorithm was too cute to forget.

I use Do Events when developing applications that loop. It makes it easy to stop them if they get into an infinite loop. For my own purposes, I usually do not include Do Events in the final product unless I intend to distribute it to friends or sell it commercially. You never know when an application will be used on some system with real time requirements. I think Do Events allows the OS to pay attention to other programs, but I am not sure of this.

I do not think that Do Events uses a noticeable amount of time. Of course it allows the user to interfere with the program, which is more likely to stop the program than slow it down. If you have a program which is checking for some external event (EG: an incoming FAX), Do Events is necessary and will slow your program if an external event is detected. I am assuming that Do Events allows the OS to switch attention to a FAX processing program, which might not be correct. The OS on mainframes I used to use would always allow certain high priority programs to seize control when an external event required servicing.

All: The algorithm will work for arrays of longs or integers or doubles. Instead of exchanging characters in a string using the Mid Function, exchange items in an array. I think the integer variables used in the Mid Function could be used as array subscripts when permuting items in an array. I think code for exchanging items in an array would seem quite similar to the code for exchanging characters in a string.

Displaying the results is more difficult for arrays of integers or longs than for strings.

When dealing with permutations, note the following.

8! = 40, 320
10! = 3, 628,800
12! = 479, 001,600
15! = 1.307E12 or 1.307*10¹²
20! = 2.43E18
25! = 1.55E25

It gets fierce damn fast. You must start storing the results in a disk file instead of in memory or a List Box.

Even if you did not have to store the results, just generating permutations of 25 objects is beyond the capabilities of any current CPU. @ one billion permutations per second it would take almost 500 million years.

That is why my application only goes up to 8 character strings (40,320 permutations), about the limit for a list Box.

The One-at-a-Time option will handle much longer strings. The user gets tired of pushing the Command Button before the List Box overflows. I do not allow more than a 28 character string, but this limit is artificial if you only want to examine a few thousand permutations.