Permutations

[Nominal Animal]

As an answer to a combinatorics question elsewhere, I showed a simple C function, that prints all the permutations of the given string:

void print_permutations(char str[], size_t len)
{
    if (len-->1) {
        const char  o = str[len];
        size_t  i;
        for (i = 0; i <= len; i++) {
            const char  c = str[i];
            str[i] = o;
            str[len] = c;
            print_permutations(str, len);
            str[i] = c;
            str[len] = o;
        }
    } else
        puts(str);
}

It is recursive (recursion depth being the same as the string length), but otherwise reasonably efficient.

In practice, we need the ability to easily generate subsets of the permutations, instead of just all of them, so the above is not that useful. In fact, as I noted in that answer, I personally prefer a seed approach; using an unsigned integer value to enumerate each permutation, so that any desired permutation(s) are fast and easy to compute. Adapted:

int permute(char *dst, const char *const src, size_t len, size_t seed)
{
    if (!dst || !src || len < 1)
        return EINVAL;

    /* Copy original pattern to destination buffer. */
    memcpy(dst, src, len);

    while (len) {
        const size_t  i = seed % len;
        char  c;

        seed /= len--;

        c = dst[0];
        dst[0] = dst[i];
        dst[i] = c;

        dst++;
    }

    *dst = '\0';
    return 0;
}

This is good and all, but we could do still better. You see, we can obtain all possible permutations of a string by only swapping neighbouring pairs in a certain order.

This means that we could, given an already permutated string, and the number of permutations already done to the string, generate the next permutation with a single swap in constant time, regardless of the string length.

(Note that because the first permutation generates the second pattern, we'll need N!-1 (swap) operations to generate all N! permutations of a N-character string.)

Of course, we'd also generate that permutation directly, using something like the seed code above.

If we label swapping the leftmost pair as 0, second pair from left as 1, then

• There are two swap sequences for three-character strings:
  
  123 ⇨ 0 1 0 1 0 ⇨ 213
  and
  
  123 ⇨ 1 0 1 0 1 ⇨ 132
• There are 344 swap sequences for four-character strings. Of these, 18 begin with 0 1 0 1 0,
  
  1234 ⇨ 0 1 0 1 0 2 0 1 0 1 0 2 0 1 2 1 0 1 0 1 2 1 0 ⇨ 1243
  1234 ⇨ 0 1 0 1 0 2 0 1 0 1 0 2 1 0 1 2 1 0 1 0 1 2 1 ⇨ 4123
  1234 ⇨ 0 1 0 1 0 2 0 1 0 1 2 1 2 1 0 1 0 1 2 1 0 1 2 ⇨ 1432
  1234 ⇨ 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 ⇨ 1432
  1234 ⇨ 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 2 0 2 ⇨ 4123
  1234 ⇨ 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 1 2 0 2 1 0 1 ⇨ 2413
  1234 ⇨ 0 1 0 1 0 2 0 1 0 2 0 1 0 1 2 1 0 1 2 0 2 1 2 ⇨ 4231
  1234 ⇨ 0 1 0 1 0 2 0 1 0 2 1 2 1 2 0 2 1 0 1 2 1 0 1 ⇨ 3421
  1234 ⇨ 0 1 0 1 0 2 0 1 2 1 0 1 0 1 2 1 0 2 0 1 0 1 0 ⇨ 1243
  1234 ⇨ 0 1 0 1 0 2 0 1 2 1 0 1 0 1 2 1 0 2 1 0 1 0 1 ⇨ 4123
  1234 ⇨ 0 1 0 1 0 2 0 1 2 1 0 1 0 1 2 1 2 1 0 1 0 1 2 ⇨ 1432
  1234 ⇨ 0 1 0 1 0 2 0 1 2 1 0 1 2 1 0 1 0 1 2 1 2 1 0 ⇨ 1432
  1234 ⇨ 0 1 0 1 0 2 0 1 2 1 0 1 2 1 0 1 2 0 1 2 1 2 1 ⇨ 4123
  1234 ⇨ 0 1 0 1 0 2 0 1 2 1 0 1 2 1 0 1 2 0 2 1 2 1 2 ⇨ 4312
  1234 ⇨ 0 1 0 1 0 2 1 0 1 2 1 2 1 0 1 0 1 2 1 0 1 2 1 ⇨ 3142
  1234 ⇨ 0 1 0 1 0 2 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 ⇨ 3142
  1234 ⇨ 0 1 0 1 0 2 1 2 1 0 1 0 1 2 1 2 1 0 1 0 1 2 1 ⇨ 3142
  1234 ⇨ 0 1 0 1 0 2 1 2 1 0 1 2 1 0 1 0 1 2 1 2 1 0 1 ⇨ 3142
  and 18 with 1 0 1 0 1,
  
  1234 ⇨ 1 0 1 0 1 2 0 1 0 1 0 2 0 1 2 1 0 1 0 1 2 1 0 ⇨ 2341
  1234 ⇨ 1 0 1 0 1 2 0 1 0 1 0 2 1 0 1 2 1 0 1 0 1 2 1 ⇨ 4231
  1234 ⇨ 1 0 1 0 1 2 0 1 0 1 2 1 2 1 0 1 0 1 2 1 0 1 2 ⇨ 2413
  1234 ⇨ 1 0 1 0 1 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 ⇨ 2413
  1234 ⇨ 1 0 1 0 1 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 2 0 2 ⇨ 4231
  1234 ⇨ 1 0 1 0 1 2 0 1 0 2 0 1 0 1 0 2 1 2 0 2 1 0 1 ⇨ 3421
  1234 ⇨ 1 0 1 0 1 2 0 1 0 2 0 1 0 1 2 1 0 1 2 0 2 1 2 ⇨ 4312
  1234 ⇨ 1 0 1 0 1 2 0 1 0 2 1 2 1 2 0 2 1 0 1 2 1 0 1 ⇨ 1432
  1234 ⇨ 1 0 1 0 1 2 0 1 2 1 0 1 0 1 2 1 0 2 0 1 0 1 0 ⇨ 2341
  1234 ⇨ 1 0 1 0 1 2 0 1 2 1 0 1 0 1 2 1 0 2 1 0 1 0 1 ⇨ 4231
  1234 ⇨ 1 0 1 0 1 2 0 1 2 1 0 1 0 1 2 1 2 1 0 1 0 1 2 ⇨ 2413
  1234 ⇨ 1 0 1 0 1 2 0 1 2 1 0 1 2 1 0 1 0 1 2 1 2 1 0 ⇨ 2413
  1234 ⇨ 1 0 1 0 1 2 0 1 2 1 0 1 2 1 0 1 2 0 1 2 1 2 1 ⇨ 4231
  1234 ⇨ 1 0 1 0 1 2 0 1 2 1 0 1 2 1 0 1 2 0 2 1 2 1 2 ⇨ 4123
  1234 ⇨ 1 0 1 0 1 2 1 0 1 2 1 2 1 0 1 0 1 2 1 0 1 2 1 ⇨ 1243
  1234 ⇨ 1 0 1 0 1 2 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 ⇨ 1243
  1234 ⇨ 1 0 1 0 1 2 1 2 1 0 1 0 1 2 1 2 1 0 1 0 1 2 1 ⇨ 1243
  1234 ⇨ 1 0 1 0 1 2 1 2 1 0 1 2 1 0 1 0 1 2 1 2 1 0 1 ⇨ 1243
• One of the above,
  
  1234 ⇨ 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 ⇨ 1432
  not only contains the three-character one as its prefix, but every second swap is of the initial pair. (You might also notice how the rightmost item has moved to leftmost position, and the rest reversed in order.)
• Another one of the above,
  
  1234 ⇨ 1 0 1 0 1 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 ⇨ 2413
  also contains the prefix sequence, although a zero (an initial swap) is skipped in the middle. This one is not so interesting, though.

However, these sequences are not compatible with the permutation sequences generated by the two functions above, and I do not know of any function that would generate the term n in the sequence in constant time complexity. So, the swap approach looks perfect in theory, but pretty weak in practice.

There are so many sequences for the five-character string, that I haven't bothered to find them all, or even a particularly interesting one (with the above 1234 ⇨ 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 ⇨ 1432 as a prefix). Since 5!=720 (meaning there are 719 swaps in the sequence for five-character strings, generating 719 additional permutations of the original string for a total of 720), an exhaustive (tree-based) search is probably feasible, but annoyingly slow.

(If we were to consider the string as a number, plain swaps are not sufficient to generate the permutations in ascending or descending decimal value. It is possible with insertions, and there is an interesting pattern there that might make it easy to generate the next permutation, but generating the same permutations based on the seed looks too tricky to me.)

Iit might be possible to construct a swap sequence (swapping consecutive or nonconsecutive members in the string) that allows an easy seed-based construction similar to the first function shown in this message (or even a non-recursive one). I haven't found one, but I haven't looked that hard, either.

Question 1. Do you know of, or can you construct a function

permute(dst, src, len, seed)

and a corresponding swapping sequence

(a₁, b₁), (a₂, b₂), (a₃, b₃), ...

so that swapping characters a₁ and b₁ in a string produces the permutation corresponding to seed=1, also swapping a₂ and b₂ produces the permutation corresponding to seed=2, and so on?

Question 2. For generating sets of permutations (say, two separate sets where each permutation is unique within the set, but a specific number of permutations occur in both sets -- or something like that, as needed sometimes in scientific problems), I believe the permute(dst, src, len, seed) function (second code snippet from the top) is the most useful one, thus far; even though the swapping approach (in question 1) should/might be more efficient in theory. Could you help prove/disprove this? Well, I'm interested in your opinions and ideas here, really. My only basis for my belief is that permute() is O(N) time complexity, where N is the number of elements in the string, which is never too bad considering the total number of permutations is N!.

[rcgldr]

There's an iterative version of next_permutation that starts with a sorted array and ends up with a sorted array. It can be paused and continued at any time because the algorithm is driven off the out of order elements. I don't know if there's an optimized variation that can start with a sorted array and perform the equivalent of n cycles of permutations, given n (it could just perform n cycles).

[Nominal Animal]

There's an iterative version of next_permutation that starts with a sorted array and ends up with a sorted array. It can be paused and continued at any time because the algorithm is driven off the out of order elements. I don't know if there's an optimized variation that can start with a sorted array and perform the equivalent of n cycles of permutations, given n (it could just perform n cycles).

I'm well aware. To be honest, I consider it a bit silly.

The reason I showed the swap sequence, above, is to show that theoretically, a single-swap -based approach might be available. If found, it would be significantly more efficient.

My permute() function above is what I'd use instead of the next_permutation(). Mine does just a single pass over the string for each permutation (although it does do a modulus and division for each element). For an N-character string, each call does N-1 swaps, divisions and modulos. Instead of relying on the order of the members in the array, it relies on the separate seed variable. To generate the next permutation, just increment the seed by one. All seed values from 0 to N!-1, inclusive, generate the N! unique permutations of an N-element array. Assuming unique array members; otherwise nonunique permutations are generated.

(Actually, all seed values generate only valid permutations. It's just that only the first N! ones are unique.)

Furthermore, I wrote

(If we were to consider the string as a number, plain swaps are not sufficient to generate the permutations in ascending or descending decimal value. It is possible with insertions, and there is an interesting pattern there that might make it easy to generate the next permutation, but generating the same permutations based on the seed looks too tricky to me.)

It turns out that the next_permutation() referred to ends up doing the above, except with repeated swaps to perform the insertion, and relying on the contents of the string itself to get it right. Here are the actual operations done, in order:

(s[0], s[1]) ← (s[1], s[1])

(s[0], s[1], s[2]) ← (s[1], s[2], s[0])

(s[0], s[1]) ← (s[1], s[0])

(s[0], s[1], s[2]) ← (s[2], s[0], s[1])

(s[0], s[1]) ← (s[1], s[0])

(s[0], s[1], s[2], s[3]) ← (s[2], s[1], s[3], s[0])

(s[0], s[1]) ← (s[1], s[0])

(s[0], s[1], s[2]) ← (s[1], s[2], s[0])

(s[0], s[1]) ← (s[1], s[0])

(s[0], s[1], s[2]) ← (s[2], s[0], s[1])

(s[0], s[1]) ← (s[1], s[0])

(s[0], s[1], s[2], s[3]) ← (s[2], s[3], s[0], s[1])

(s[0], s[1]) ← (s[1], s[0])

(s[0], s[1], s[2]) ← (s[1], s[2], s[0])

(s[0], s[1]) ← (s[1], s[0])

(s[0], s[1], s[2]) ← (s[2], s[0], s[1])

(s[0], s[1]) ← (s[1], s[0])

(s[0], s[1], s[2], s[3]) ← (s[3], s[1], s[0], s[2])

(s[0], s[1]) ← (s[1], s[0])

(s[0], s[1], s[2]) ← (s[1], s[2], s[0])

(s[0], s[1]) ← (s[1], s[0])

(s[0], s[1], s[2]) ← (s[2], s[0], s[1])

(s[0], s[1]) ← (s[1], s[0])

where s[0] refers to least significant position, with increasing indexes indicating increasing significance (i.e. s[0] is the rightmost place).
If the string represents a decimal number with unique digits, initially digits in decreasing order from right (s[0]) to left (s[n]), say 1234, then each replacement step above creates the permutation with next larger value. The first five modifications apply to three-digit strings, and all twenty-three apply to four-digit strings.

(It is easy to generate more modifications, although I'm not exactly sure what the most efficient method to do so is. If nothing else, you can always use an order array, initialized to "digits", and perform the swaps on both the order array and the target string.)

Again, it's tricky to generate a specific permutation directly (e.g. nth from initial pattern), although I think I now have an approach that might work: the most significant digit of the string, in an N-digit string with seed 0≤seed<N!, is digit ⌊N seed / N!⌋ = ⌊seed/(N-1)!⌋ of the leftover digits (because they cover equal number of entries in the, uh, permutation space?), with 0 referring to the smallest digit left. To remove the digit from the seed, substract the value multiplied by (N-1)!. This should allow one to construct the permutation in reverse order.

(Consider an N-digit number that uses each digit only once. There are as many permutations that begin with digit N as they are those that begin with digit N-1, or any other digit, including 1. So, each possible highest digit "covers" equal number of permutations. Because there are N! permutations, there are exactly (N-1)! permutations that begin with digit N (or any particular digit). So, since the seed is 0≤seed<N!, we know that seeds 0≤seed<(N-1)! corresponds to permutations with the least significant digit available in the most significant position, and seeds (N-1)(N-1)!≤seed<N! correspond to permutation with the most significant digit available in the most significant position. Subtracting ⌊seed/(N-1)!⌋(N-1)! from seed "removes the most significant digit from the seed", so you can attack the next digit, if any are left, in the exact same way.)

[Nominal Animal]

Here's a function that generates the indexth permutation, in order, using the specified set of characters. This is "optimized" for readability, not for speed.

If you specify digits in increasing lexicographic order, then the generated permutation will be the indexth one in lexicographic order.

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>

typedef unsigned long  permutation_t;

static permutation_t factorial(const permutation_t n)
{
    permutation_t  i, result = 1;

    for (i = 2; i <= n; i++) {
        const permutation_t  newresult = result * i;
        if ((permutation_t)(newresult / i) != result)
            return 0;
        result = newresult;
    }
    return result;
}

int permutation(char *const        buffer,
                const char *const  digits,
                const size_t       length,
                permutation_t      index)
{
    permutation_t  scale;
    size_t         i, d;

    if (!buffer || !digits || length < 1)
        return errno = EINVAL;

    scale = factorial(length);
    if (!scale)
        return errno = EMSGSIZE;
    if (index >= scale)
        return errno = ENOENT;

    memmove(buffer, digits, length);
    buffer[length] = '\0';

    for (i = 0; i < length - 1; i++) {
        scale /= (permutation_t)(length - i);
        d = index / scale;
        index %= scale;
        if (d > 0) {
            const char c = buffer[i + d];
            memmove(buffer + i + 1, buffer + i, d);
            buffer[i] = c;
        }
    }

    return 0;
}

Some examples:

permutation(buffer, "1234", 4, 0): buffer == "1234"

permutation(buffer, "1234", 4, 1): buffer == "1243"

permutation(buffer, "1234", 4, 2): buffer == "1324"

permutation(buffer, "1234", 4, 6): buffer == "2134"

permutation(buffer, "1234", 4, 12): buffer == "3124"

permutation(buffer, "1234", 4, 22): buffer == "4312"

permutation(buffer, "1234", 4, 23): buffer == "4321"

The actual characters do not matter, as they are used in the order they are specified:

permutation(buffer, "DCBA", 4, 0): buffer == "DCBA"

permutation(buffer, "DCBA", 4, 1): buffer == "DCAB"

permutation(buffer, "DCBA", 4, 22): buffer == "ABDC"

permutation(buffer, "DCBA", 4, 23): buffer == "ABCD"

As to optimizations, a temporary array of permutation_t[length] would avoid having to calculate the factorial, and speed up the generation quite a bit, but it would make the logic quite a bit more complicated to follow. As it is, I've already outlined the logic at the end of my previous post #3 above. It turned out it was much simpler than I thought.

[anduril462]

What you're trying to do reminds me of Gray coding. Also, this comes to mind: https://en.wikipedia.org/wiki/Factorial_number_system.

Sorry, I haven't had time yet to read the thread in detail, so the above may not be all that applicable after all. Maybe I'll get to it later today though.

[Mario F.]

One question: Why are you concerned with ordering and returning a random indexed element, and is this decision impacting the performance of your code? Permutations are unordered sets by any mathematical definition. Any order you may give them is completely arbitrary. What's the requirement behind this code that has you decide for a specific ordering instead of any other that would be equally valid? Or even why should you care for an order?

PHRASE and SHAPER, result in equivalent permutation sets. However, it seems you will end up with different results by running either string.

EDIT (clarification):

What I mean is, if order is not important, perhaps a solution (for large permutation sets) can be found by performing some initial analysis on the supplied string and applying not one, but different sets of algorithms based on the string characteristics. You would be free to explore optimizations for particular cases, just as repeating elements; ANAGRAM could be a special case prone to a faster solution, where PARTING could not. These optimizations however result in arbitrary ordering for each algorithm. It's would be up to the caller to sort the resulting array as they saw fit. Not you.

I'm just eyeballing here. I haven't performed any testing or tried to come up with some working algorithms for special cases. But I think that often, when we wish to come up with optimized solutions, it pays to write an analytic function coupled with several algorithms, instead of one single algorithm. I'm guessing this could be one of those cases. Alternatively, you could consider branching inside your single permutation function.

[Nominal Animal]

Why are you concerned with ordering and returning a random indexed element

Imposing some arbitrary order to the set is useful, because it makes it much simpler to generate non-overlapping subsets of the permutation set, or even more complicated sets, with specific partial overlapping.

Instead of the patterns themselves, we only look at the index numbers, according to the arbitrary order.

What's the requirement behind this code that has you decide for a specific ordering instead of any other that would be equally valid?

Originally, I was just interested in any ordering that makes it easy and fast to generate any specific permutation. (Specific only in the sense that the same seed or index will always yield the same permutation given the same source data, and that all length! first values generate unique permutations.)

So, my initial ordering is completely arbitrary. It just emerges due to the way each permutation is generated based on the index or seed.

The second ordering (in permutation()) is not arbitrary, in the sense that if you provide the characters in the original string in ascending lexicographic order, say "1459", the permutations will also be in ascending lexicographic order.

I don't know of any particular use case for this myself; I only noted the interest others had for such ordering in the discussion elsewhere.

I suppose it might be useful in cases where each permutation is interpreted as a numeric value (in any basis, not just decimal), and there is a sufficient gain in performance if the permutations are generated in increasing order of numerical value. (Such gain may arise from things like cache locality.)

PHRASE and SHAPER, result in equivalent permutation sets.

Yes, 720 permutations in each set (6! = 720).

However, it seems you will end up with different results by running either string.

No, you get the same set of permutations, just in different order.

permute() and permutation() only yield one permutation per call, not a set. Again, this is because I don't see any real use in generating the entire set; I've only needed to generate subsets.

Note that the order is independent of the string contents; the ordering is enforced only on the positions. If you want permute() to provide ascending lexicographic ordering, then the input string characters must be in ascending lexicographic ordering.

Perhaps an example makes this clearer:

permutation(,"PHRASE",6,439) yields "ASHPER"
permutation(,"ASHPER",6,439) yields "PESARH"
permutation(,"SHAPER",6,439) yields "PEHSRA"
permutation(,"PEHSRA",6,439) yields "SREPAH"
permutation(,"123456",6,439) yields "452163"

In other words, permutation() uses an ordering where the 439th permutation (zero being the original string) of a six-character string moves the first character to fourth position, second character to third position, third character to sixth position, fourth character to first position, fifth character to second position, and sixth character to fifth position.

You would be free to explore optimizations for particular cases, just as repeating elements

True, but I've not encountered a problem where the original "string" contained repeated elements.

It's would be up to the caller to sort the resulting array as they saw fit. Not you.

Butbut, the entire idea is to avoid having to generate the entire permutation set, because you rarely want to do that anyway; it's too large. Only subsets. Which they themselves may be large, though. Which is why it matters to do it fast and efficiently.

But I think that often, when we wish to come up with optimized solutions, it pays to write an analytic function coupled with several algorithms, instead of one single algorithm.

I fully agree!

However, I don't see the sets as the problem to be solved. These functions, to me, are very simple, basic tools used for solving other problems.

My "Question 1" would provide an exceptionally fast method of generating any "consecutive" subset of the permutation set, while allowing direct generation of any particular permutation based on the index.

My "Question 2" is based on an intuitive feeling that my original permute() function is already maxing out both memory/cache bandwidth (as it is a single loop over the string), as well as the ALU (since it uses one division+modulus per element), and that the approach in "Question 1" is unlikely to succeed as the computation required to obtain the swap pair from the index would be too complex/slow and defeat the effort. As in, non-polynomial functions required to compute it.