PHP: Permutations of 26 letters in X characters

I have an alphabet array with 26 characters A..Z .

I am searching for a performant algorithm that list开发者_运维技巧s all permutations that fill an array of length X without any repeating characters.

Examples:

X=3 . Target array: _ _ _

Permutations are A B C until Z Y X .

X=4 . Target array: _ _ _ _

Permutations are A B C D until Z Y X W

X=5 . Target array: _ _ _ _ _

Permutations are A B C D E until Z Y X W V

(Sorry, I don't know how this kind of algorithm is named)

Thanks in advance.

Code in C, Delphi or Java is also OK, since it can be easy translated.

---

A simple solution is a recursive one

char current_combination[27];
int char_used[26];

void enumerate(int i, int n)
{
    for (int j=0; j<26; j++)
    {
        if (!char_used[j])
        {
            char_used[j] = 1;
            current_combination[i] = 'A' + j;
            if (i+1 == n)
            {
                puts(current_combination);
            }
            else
            {
                enumerate(i+1, n);
            }
            char_used[j] = 0;
        }
    }
}

The function above accepts the index i of the character to be computed and the total number n of characters in a combination (the code assumes i<n). It keeps the current combination and the array of flags for already used variables in globals to avoiding copying them around.

To generate for example all combinations of length 5 call enumerate(0, 5).

Note that the total number of combinations grows very fast. For example for n=6 there are 165,765,600 combinations, with more than 1Gb of output.

---

I'd take a simple brute force approach though do understand the number of permutations can get up there as the number is 26!/(26-x)! which can be rather large as for 3 there are 15,600 permutations and for 5 there are 7,893,600 permutations which isn't exactly small. Basically you could just loop through all the values with loops in loops that unfortunately would be O(n^x) where x is the number of characters since the nesting of loops causing the complexity jump.

---

Something to consider is how finely are you examining complexity here. For example, while you could consider ways to go about being clever in the first pair of loops to avoid duplication, the third loop in becomes a bit trickier though if you started with a List of 26 letters and removed the previous ones, this would make the last loop be a simply iterative as you know there isn't any duplicates though this can be expensive in terms of memory consumed in having to make copies of the list on each pass from the outer loop. Thus the first time, you'd go through AB_ and then AC_ and so forth, but the copying of the list may be where this gets expensive in terms of operations as there would be thousands of times that the list is copied that one could wonder if that is more efficient than doing comparisons.

---

Are you sure you want to see all permutations? If you have X=3, you will have 26*25*24 combinations = 15600. And if X=5 number of combinations is equal to 7893600.

You need to randomly select one letter(or array index) and store it somewhere and on each iteration you should check if this letter(or index) has been already selected on one of the previous iteration. After this you will get random sequence which length is X characters. You need to store it too. Then you need to reapeat all operation made on the previous step and also you have to check if there is random sequense with subsequence you have been generating now.

Or you could use direct enumeration.

Sorry for not satisfactory english. I tried to be clear.

I hope it will be usefull.