Next different permutation in C

Question

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 :)

next_different_permutation.c:

#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].
                --k;
            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;
}

Usage:

#define ARRAY_SIZE 3
int A[ARRAY_SIZE]

void next_different_permutation_test_distinct() {
    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));
    // the order will back to A[l]<A[l+1]<...<A[r]
}

void next_different_permutation_test_some_identical() {
    for (int i = 0; i < ARRAY_SIZE; ++i)
        A[i] = rand()%RAND_MOD;
    do {
        print_array(A, ARRAY_SIZE, PRINT_WIDTH);
    } while (next_different_permutation(A, 0, ARRAY_SIZE-1));
}

Is the behaviour intended to be the same as C++ std::next_permutation()? — Toby Speight
– Toby Speight, Commented Feb 21, 2021 at 11:45
@TobySpeight: No, but the only difference is std used [l ,size) but I personally prefer [l, r] when the range size will not vary. Good question btw, this is important to me also :) — RainningTW
– RainningTW, Commented Feb 21, 2021 at 12:10

RainningTW · Accepted Answer · 2021-02-22 05:56:31Z

size and i in reverse look superficial. Consider

void reverse(int A[], int l, int r) {
    while (l < r) {
        pswap(&A[l++], &A[r--]);
    }
}

The outer loop looks very strange. Its body is executed exactly once, when the longest decreasing interval is detected. Consider lifting the body out of the loop.

As a side point, I don't see the point of struct {int i; int j}. It is initialized to {r-1, r}, and at each iteration both members are decremented. z.i is always equal to z.j - 1. Keeping just one int is enough. Consider

  int j = r; // j will point to the highest peak of the interval [i,r].
  // this loop will find the first increasing [i,j] from r to l.
  while (j > l) {
      if (A[j-1] < A[j]) {
          break;
      }
      --j;
  }

  if (j > l) {
      int k = r;
      // find the first A[k] where A[k] > A[j-1].
      while (!(A[j-1] < A[k])) {
          --k;
      }
      pswap(&A[j-1], &A[k]);
      reverse(A, j, r);
      return true;
  }

  reverse(A, j, r);
  return false;

It already looks cleaner, but let's get going. An obvious next step is to get rid of the duplicate calls to reverse:

  if (j > l) {
      ....
      pswap(....);
  }
  reverse (A, j, r);
  return j > l;

No naked loops please. If you felt compelled to put comments like

      // find the maximal decreasing interval [j,r]
      // find the first A[k] where A[k] > A[z.i].

you admit that you failed to express the intentions in the code. Consider refactoring these loops into functions. Consider

  int j = find_decreasing_interval(A, l, r);
  if (l < j) {
      int k = lower_bound(A, j, r, A[j-1]);
      pswap(&A[j-1], &A[k]);
  }
  reverse((A, j, r);
  return j > l;

Toby Speight · Accepted Answer · 2021-02-22 08:36:32Z

1

pswap() and reverse() aren't part of the public interface, so ought to be declared with static linkage.

If we passed pairs of pointers, rather than indices, we wouldn't need to also pass the start of array. Even with indices, we don't need to pass l - we can supply the subarray beginning at l.

The C++ function std::next_permutation() has a more useful behaviour here:

if (r-l+1 <= 1)
    return false;                           // return false when [l,r] is(or back to) an increasing interval.

As well as returning false, it wraps around to the first permutation again.

Some of the choices for line-wrapping are questionable. Consider this:

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)

Breaking the line (with an intruding comment!) between the type of z and z itself makes that much harder to read, compared with putting the newlines after each ;:

// find the first increasing [i,j] from r to l.
for (struct{int i, j;} z = {r-1, r};
     z.j != l;
     --z.i, j=--z.j)

That said, I'd avoid declaring a new type within the for construct, and simply use something more like

for (int i = r-1, j = r;  j != l;  --i, --j)

answered Feb 22, 2021 at 8:36

Toby Speight

88.4k14 gold badges104 silver badges327 bronze badges

\$\begingroup\$ By if (r-l+1 <= 1) return false; I meant if the array is [1] its next permutation is trivially wrapped back to [1] without doing anything. You could run the test and print out the A[] after the while loop, it actually does the same as std::next_permutation. (If anything is wrong in this comment pls let me know!) \$\endgroup\$

RainningTW
– RainningTW

2021-02-22 17:53:54 +00:00
Commented Feb 22, 2021 at 17:53
\$\begingroup\$ As for the struct{...} in for loop, that's indeed a bad idea..., I read a post mentioned it and thought it was good :p \$\endgroup\$

RainningTW
– RainningTW

2021-02-22 17:57:23 +00:00
Commented Feb 22, 2021 at 17:57
\$\begingroup\$ Ah, I see it's the other return false that's the wrapping behaviour. My mistake! \$\endgroup\$

Toby Speight
– Toby Speight

2021-02-22 20:30:39 +00:00
Commented Feb 22, 2021 at 20:30

Add a comment |

Stack Exchange Network

Next different permutation in C

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Next different permutation in C

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions