C How to generate an arbitrary permutation within range [i,j]? [closed]

Question

Does C standard library provide any function that generate a random permutation of consecutive numbers within a range?

How to make a function that efficiently does it? I'm thinking of making a random number generator that generates in a without-replacement way, but I could not figure out how to achieve minimum cost.

Note that, unlike most similar questions I found on web where all possible permutations are needed, here I just need ONE valid permutation, as long as the generation is not costly, and the permutation must be done in a random way, i.e., no tricks, say, simply return the ordered sequence or reversed sequence, etc.

Answer 1

Does C standard library provide any function that generate a random permutation of consecutive numbers within a range?

No. The C standard library is intentionally small and utilitarian.^* It does not contain such a function. You can undoubtedly find a third-party library that does this, though.

How to make a function that efficiently does it? I'm thinking of making a random number generator that generates in a without-replacement way, but I could not figure out how to achieve minimum cost.

The Fisher-Yates shuffle is a conventional way of doing this. It is exactly a sequence of (pseudo-)random selections without replacement, continuing until all the items have been selected. This costs O(n) in the number of items to shuffle / permute, and it can be done in-place. The linked Wikipedia article provides pseudocode for several variations. Yours could either receive (a pointer to) an array of the items to shuffle, or it could start by dynamically allocating an array of the right size, then populate deterministically, then shuffle.

---

^* Compared to many other high-level languages' standard libraries, such as C++'s, Python's, or Java's.

Answer 2

You can uniquely select a permutation based on a number in the range 0 .. n!-1 by considering the number used to select the permutation a variable base number in which the least significant digit is the base n digit. The next being in base n-1 (obviously the most significant is just 0 allowing you to select only the last number) As each digit is selected, you exchange it with the first, building the permutation in the array, and moving the one ocuppying the place to the changed side. This will allow you to say a number between 0 and n! - 1 and build the permutation in that order. This is very similar to the algorithm described in the Fisher-Yates shuffle, but it only generates the permutation you are intereste in.

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

/* calculate permutation from position id */
char *permut(char *str, size_t len, size_t id)
{
    char *saved = str;

    for (;len; len--, str++) {

        int mod = id % len;

        if (mod) {  /* exchange */
            char temp = str[0];
            str[0]    = str[mod];
            str[mod]  = temp;
        }
    }
    return saved;
} /* permut */

/* calculate factorial to get top limit in main */
size_t fact(int n)
{
    int ret_val  = 1;

    for (int  i  = 2; i <= n; i++)
        ret_val *= i;

    return ret_val;
} /* fact */

int main()
{

#define STRING "123"

    int    len = strlen(STRING);
    size_t lim = fact(len);

    for (size_t pos = 0; pos < lim; pos++) {

        char cad[] = STRING;

        printf("(%s; %zd) -> ", cad, pos);
        printf("(%s)\n", permut(cad, len, pos));
    }
} /* main */