anagram descrambler...

[Orion1]

I am attempting to solve an anagram game puzzle just for fun, however what is difficult is the number of possible combinations for a typical anagram.

For example, in DNA there are 4 bases 'A','C','G','T'.

The equation that I derive for the number of possible combinations is:
N_c = N_b^L
N_b - base unit number
L - base unit length

So, for one base of length L = 1, there are 4 combinations:
N_c = 4^1 = 4

Increasing the length to L = 4, there are 256 combinations:
N_c = 4^4 = 256

However, for English word anagram descrambling there are 26 base unit letters.

So, for one base of length L = 1, there are 26 combinations:
N_c = 26^1 = 26

Increasing the length to L = 4, there are 456976 combinations:
N_c = 26^4 = 456976

I am inquiring if any programmers here can write a simple program in Basic or in Visual Basic, with a better logistical code than I can write that does not require a lot of computational algorithmic cycles for descrambling an input anagram word and output all the possible combinations, for example:

input: edco
N_c = 4^4 = 256 - maximum combination number for input anagram word?

output 1: deco
...
output n: code
...

I am not certain that the number of possible combinations equation that I have stated is accurate for scrambled anagram words, since each anagram letter can only be used once in a sequence. So what would the equation be for a scrambled anagram word?

Reference:
Anagram - Wikipedia (http://en.wikipedia.org/wiki/Anagram)

[Mark44]

You should be thinking about permutations rather than combinations. An anagram is just a rearrangement of the letters in some word. For a given four-letter word, there are 4! (= 4 * 3 * 2 * 1 = 24) different permutations of the four letters. More generally, for a word with n letters, there are n! possible anagrams.

Going back to your example with four letters, for each permutation, there are four possible choices for the first letter. For the second letter, there are three unused letters, so three possible choices. For the third letter, there are only two possible choices. Finally, for the fourth letter, there is just one unused letter.

[Grep]

Don't know VB so I can't help you much there.

However, here's a version in C++ that I derived from code from "Practical Algorithms in C++" by Flamig, B. Do note that it's recursive. It's one of those things that are probably annoying to do iteratively. Also, I used a C style string for it, which I normally wouldn't do. I would normally comment it as well, but there ya go.

Anyways, if you can code in VB you should be able to convert it easily enough:


#include <iostream>
#include <cstring>

using namespace std;

void permute(char bytes[], const int start, const int len)
{
for (int i = 0; i < len; i++)
{
cout << bytes[i];
}
cout << endl;

if (start < len)
{
for (int i = len-2; i >= start; i--)
{
for (int j = i+1; j < len; j++)
{
char tmp = bytes[i];
bytes[i] = bytes[j];
bytes[j] = tmp;

permute(bytes, i+1, len);
}

char tmp = bytes[i];
for (int k = i; k < len-1; k++)
{
bytes[k] = bytes[k+1];
}
bytes[len-1] = tmp;
}
}
}

int main(int argc, char *argv[])
{
char word[] = "1234";

permute(word, 0, strlen(word));
}