首页 > 代码库 > 下一次最近排列

下一次最近排列

对序列 {a, b, c},每一个元素都比后面的小,按照字典序列,固定a之后,a比bc都小,c比b大,它的下一个序列即为{a, c, b},而{a, c, b}的上一个序列即为{a, b, c},同理可以推出所有的六个序列为:{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a},其中{a, b, c}没有上一个元素,{c, b, a}没有下一个元素。

代码如下:

 

void swap(int *a, int *b){    int c = *a;    *a = *b;    *b = c;}void reverse(int *array, int begin, int end){    int i, j;    for (i = begin, j = end; i < j; i++, j--)    {        swap(&array[i], &array[j]);    }}int next_permutation(int *array, int begin, int end){    if (array == NULL || begin >= end)    {        return 0;    }    int i, j, k;    for (j = end, i = end - 1; i >= begin && j > begin; j--, i--)    {        if (array[i] < array[j])        {            break;        }    }    if (j == 0 && i == -1)    {        return 0;    }    for (k = end; k >= j; k--)    {        if (array[k] > array[i])        {            break;        }    }    swap(&array[i], &array[k]);    reverse(array, i + 1, end);        return 1;}int main(void){    int array[4] = {1, 2, 3, 4};    int begin = 0, end = 3;    do    {        int i;        for (i = 0; i <= end; i++)        {            cout << array[i] << ", ";        }        cout << endl;    }while (next_permutation(array, begin, end));    getchar();    return 0;}

 

运行结果: