Archived

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

Sort Algortithm

This topic is 6802 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I need to write an algorithm that will give me every possible combination of a 4 letter word. Is there a way to do this?

Share on other sites
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.

---- --- -- -

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

Share on other sites
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
DABC <- end first loop
DACB <- start second loop
DCAB
CDAB <- end second loop
CDBA <- start third loop
CBDA
BCDA <- end third loop
BACD
ABCD <- end fourth loop -- You''ve reached the
original string!

There it is!

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.

---- --- -- -

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

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--;
}
}

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

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 14
• 14
• Forum Statistics

• Total Topics
633387
• Total Posts
3011609
• Who's Online (See full list)

There are no registered users currently online

×