当前位置:首页 > 开发 > Web前端 > Ext > 正文

next_permutation

发表于: 2015-11-13   作者:互联网   来源:转载   浏览:
ext
摘要: How to systematically generate all the permutations of a given sequence? see http://en.wikipedia.org/wiki/Next_permutation 1, Find the largest index k such that a[k] < a[k + 1]. If no such i

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

see http://en.wikipedia.org/wiki/Next_permutation

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].

第一步以后,a[k]以后的是一个递减序列,已经是最大的了,再折腾也没用;

第二步,如果带上a[k],那么lexicographical order的下一个一定是以比a[k]大的一个数打头的,从后面找到刚好比a[k]大的那一个,假设是a[l];

第三步,将a[l]提到前面,与a[k]互换,这时候,a[k]后面的仍然是降序的。

第四步,把a[k]后面的逆转一下,从降序到升序,这样就得到了恰好比之前序列大一号的序列(打头的是刚好更大的那个,后面的是升序)。

#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

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号