next_permutation

How to systematically generate all the permutations of a given sequence?

1, Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.

2, Find the largest index l such that a[k] < a[l]. Since k+1 is such an index, l is well defined and satisfies k < l.

3, Swap a[k] with a[l].

4, Reverse the sequence from a[k+1] up to and including the last element a[n].

```#include <stdio.h>

#include <stdlib.h>

int arr[] = {1, 3, 2, 4};

#define NR_ELEM(arr) (sizeof(arr) / sizeof(arr[0]))

int comp(const void *lhs, const void *rhs)

{

return *(const int *)lhs - *(const int *)rhs;

}

inline void print_arr()

{

int i;

for (i = 0; i < NR_ELEM(arr); i++)

printf("%d, ", arr[i]);

printf("\n");

}

// return 1 if there's another (lexicographically larger) permutation, 0 otherwise.

int next_permutation()

{

int i, j, k, l;

// Step 1, find the largest k s.t. arr[k] < arr[k+1]

for (k = NR_ELEM(arr) - 2; k >= 0; k--)

if (arr[k] < arr[k + 1])

break;

if (k < 0)

return 0;

// Step 2, find the largest l(el) s.t. arr[k] < arr[l]

for (l = NR_ELEM(arr) - 1; l > k; l--)

if (arr[k] < arr[l])

break;

// Step 3, swap arr[k] & arr[l]

int temp = arr[k];

arr[k] = arr[l];

arr[l] = temp;

// Step 4, reverse arr[k+1, ]

for (i = k + 1, j = NR_ELEM(arr) - 1; i < j; i++, j--) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

return 1;

}

int main(int argc, char *argv[])

{

qsort(arr, NR_ELEM(arr), sizeof(arr[0]), comp);

print_arr();

while (next_permutation())

print_arr();

return 0;

}

```

next_permutation

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊