Archived

This topic is now archived and is closed to further replies.

dj9781

Sort Algortithm

Recommended Posts

Did you want every 4-letter combo of any letters or of some particular letters?

If the latter, here's an STL approach that might work. (This is off the top of my head, so watch your back.)


#include <algorithm>
#include <string>

using namespace std;

void foo(const char* s)
{
string word = s;

sort(word.begin(), word.end());

do {
cout << word << endl;
}
while (next_permutation(word.begin(), word.end()));
}


Of course, this is permutations which is mathematically different from combinations, so I apologize if this isn't what you were asking for.

---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!


Edited by - mossmoss on 4/5/00 2:35:44 PM

Share this post


Link to post
Share on other sites
Your post got me thinking...
Do you have a four letter word where you want to find every other combination of the original letters possible? If so, here''s the algorithm:

Loop along the length of the string, starting with the LAST two characters (rightmost). Swap these characters with eachother. Then, save the string, and move your pointer into the string LEFT (back) 1 byte. Swap the next pair, and save this string. When you reach the end of the string, go back and do it again until you get your original string again!

Here''s how the letters ABCD would be manipulated:

ABCD <- original
ABDC <- start first loop
ADBC
DABC <- end first loop
DACB <- start second loop
DCAB
CDAB <- end second loop
CDBA <- start third loop
CBDA
BCDA <- end third loop
BCAD <- start fourth loop
BACD
ABCD <- end fourth loop -- You''ve reached the
original string!

There it is!

Share this post


Link to post
Share on other sites
quote:
Original post by VGASteve

Loop along the length of the string, starting with the LAST two characters (rightmost). Swap these characters with eachother. Then, save the string, and move your pointer into the string LEFT (back) 1 byte. Swap the next pair, and save this string. When you reach the end of the string, go back and do it again until you get your original string again!



This isn't quite a complete solution. You're missing some permutations, such as ACDB, ACBD, and others. Actually, it is very easy to determine how many permutations there should be. For four letters, there are 4! (factorial) permutations, which is 4*3*2*1 = 24. Your algorithm finds half of those, but not the other half.

---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

Edited by - mossmoss on 4/5/00 2:43:21 PM

Share this post


Link to post
Share on other sites
Hey guys thanks for the feedback. I think I've come up with a solution. I sorta did what VGASteve said but I only moved the last letter over 2 places instead of 3.

for(z=0; z<3; z++)
{
y=2;
for(x=3; x>1; x--)
{
temp = word[y];
word[y] = word[x];
word[x] = temp;
y--;
}
}

temp = word[0];
word[0] = word[1];
word[1] = temp;

for(z=0; z<3; z++)
{
y=2;
for(x=3; x>1; x--)
{
temp = word[y];
word[y] = word[x];
word[x] = temp;
y--;
}
}

temp = word[0];
word[0] = word[2];
word[2] = temp;

for(z=0; z<3; z++)
{
y=2;
for(x=3; x>1; x--)
{
temp = word[y];
word[y] = word[x];
word[x] = temp;
y--;
}
}

temp = word[0];
word[0] = word[3];
word[3] = temp;

for(z=0; z<3; z++)
{
y=2;
for(x=3; x>1; x--)
{
temp = word[y];
word[y] = word[x];
word[x] = temp;
y--;
}
}

Thanks for all your help.

Edited by - dj9781 on 4/5/00 8:12:27 PM

Share this post


Link to post
Share on other sites