Shuffle & next-permutation

Fisher-Yates shuffle Modern method.

https://en.wikipedia.org/wiki/Fisher-Yates_shuffle#Modern_method
易于理解，从最后一个开始loop，在他之前（包括他本身）随便找一个，跟他swap。

vector<int> shuffle(vector<int> a) {
    for (int i=a.size()-1; i>0; i--) {
        int p = rand()%(i+1);
        swap(a[p],a[i]);
    }
    return a;
}

Next Permutation

先来看全排列，n个数的全排列有n!个。

// Calling perm(0) to start.
int a[]={1,2,3,4}, n=4;
void perm(int p) {
    if (p==n-1) {
        for (int i=0; i<n; i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    for (int i=p; i<n; i++) {
        swap(a[p],a[i]);
        perm(p+1);
        swap(a[i],a[p]);
    }
}

原理就是第一次recursion，把第一位和他后面（包括他自己）的数换一下，然后进行下一位的recursion，然后再换回来。

https://en.wikipedia.org/wiki/Permutation
http://bangbingsyb.blogspot.com/2014/11/leetcode-next-permutation.html
这个next permutation就有点神奇了，还是STL里的，不如换个思路理解一下，参见上述链接。
所谓next permutation，就是现在已经有个排列了（假定刚开始是升序排列），用这几个数排列一下，找“比现在这个排列就大一点点的排列”。
e.g.: 4 3 2 1 => is the most largest permutation.

  4 2 3 1 => move 'number3' to the position of 'number2'.
  ==> 4 3 (2 1). and resort 

int a[]={1,2,3,4}, n=4;
void nextPerm () {
    int pos1, pos2;
    for (pos1=n-2; pos1>=0; pos1--)
        if (a[pos1]<a[pos1+1])
            break;
    if (pos1==-1) {// e.g. 4 3 2 1
        reverse(a,a+n);
        return ;
    }
    for (pos2=n-1; pos2>pos1; pos2--)
        if (a[pos2]>a[pos1])
            break;
    swap(a[pos1],a[pos2]);
    //after swap, a[pos1+1 -> n] must keep its order (non-increase),
    //so we just need to reverse it simply to get the minimum sequence.
    reverse(a+pos1+1,a+n);
}