algorithm – Next different permutation in C

This is a program which you can get the next “different”, i.e. elements in A() can be identical, permutation at each call. I’ve written a C++ program for the same purpose in 2018, but I found it unreadable, readability = NULL, so here is a new one.

Any critical comment and answer will be welcomed 🙂


#include <stdbool.h>

void pswap(int *l, int *r) {
    int temp = *l;
    *l = *r;
    *r = temp;

void reverse(int A(), int l, int r) {
    int size = (r-l+1);
    for (int i = 0; i < size/2; ++i)
        pswap(&A(l+i), &A(r-i))

bool next_different_permutation(int A(), int l, int r) {
    if (r-l+1 <= 1)
        return false // return false when (l,r) is(or back to) an increasing interval.
    int j = -1; // j will point to the highest peak of the interval (i,r).
    for (struct{int i, j;} // this for will find the first increasing (i,j) from r to l.
        z = {r-1, r}; z.j != l; --z.i, j=--z.j)
        if (A(z.i) < A(z.j)) { // find the maximal decreasing interval (j,r).
            int k = r; // after swap (i, k), interval (j,r) remains decreasing.
            while (!(A(z.i) < A(k))) // find the first A(k) where A(k) > A(z.i).
            pswap(&A(z.i), &A(k));
            reverse(A, z.j, r);
            return true; // when success we go, the z.i, z.j will be initialized in next call.
    reverse(A, j, r); // Recover the A(l)>=A(l+1)>=...A(r)-array back to the increasing order.
    return false;


#define ARRAY_SIZE 3

void next_different_permutation_test() {
    for (int i = 0; i < ARRAY_SIZE; i++)
        A(i) = i+1
    do {
        print_array(A, ARRAY_SIZE, PRINT_WIDTH);
    } while (next_different_permutation(A, 0, ARRAY_SIZE-1));