请问这道“排列”的算法题的代码如何理解呢？

Question

请问这道“排列”的算法题的代码如何理解呢？希望给出每行代码的注释，非常感谢！

#include<cstdio>

int a[1025] = { 0 };

void NextPermutation(int size)
{
    int flag = size - 1;
    int tmp;
    int i;
    while (a[flag - 1] > a[flag] && flag != 0)
    {
        flag--;
    }
    if (flag == 0)
    ｛
        for (i = 0; i < size; i++)
            a[i] = i + 1;
        return;
    ｝
    for (i = size - 1; i >= flag; i--)
    {
            if (a[i] > a[flag - 1])
            {
                temp = a[flag - 1];
                a[flag - 1] = a[i];
                a[i] = temp;
                break;
            }
     }
     while (size - 1 > flag)
     {
            temp = a[size - 1];
            a[size - 1] = a[flag];
            a[flag] = temp;
            flag++;
            size--;
     }
}

int main(void)
{ 
    int m, n, k;
    int i;
    scanf("%d", &m);
    while (m)
    {
        scanf("%d%d", &n, &k);
        for(i = 0; i < n; i++)
            scanf("%d", &a[i]);
        for(i = 0; i < k; i++)
            NextPermutation(n);
        for (i = 0;i < n; i++)
            printf("%d", a[i]);
        printf("\n");
        m--;
    }
    return 0;
}

Answer 1

#include <cstdio>
int a[1025] = {0};
void NextPermutation(int size)
{
    int flag = size - 1; // size为给出的n的值,代表数字位数
    int temp;
    int i;
    while (a[flag - 1] > a[flag] && flag != 0) //从a[n-1]向左寻找,如果a[flag - 1] > a[flag],就将flag自减,这一步对应算法描述中的(2)
    {
        flag--;
    }

    if (flag == 0) //如果这个序列已经是递减的,则这个序列的下一个序列是严格递增的,对应算法的(5)
    {
        for (i = 0; i < size; i++)
            a[i] = i + 1;
        return;
    }

    for (i = size - 1; i >= flag; i--) //找到a[flag]到a[size-1]中大于a[flag-1]的最小数字,并将其与a[flag-1]互换,对应算法的(3)
    //由于步骤(2),flag之后的元素都能保证为有序,所以找到的第一个符合要求的数字恰好是大于a[flag-1]的最小数字
    {
        if (a[i] > a[flag - 1])
        {
            temp = a[flag - 1];
            a[flag - 1] = a[i];
            a[i] = temp;
            break;
        }
    }
    while (size - 1 > flag)//对剩余部分重新排序,对应算法的(4)
    {
        temp = a[size - 1];
        a[size - 1] = a[flag];
        a[flag] = temp;
        flag++;
        size--;
    }
}
int main(void)
{
    int m, n, k;
    int i;
    scanf("%d", &m);
    while (m)
    {
        scanf("%d%d", &n, &k);
        for (i = 0; i < n; i++)
            scanf("%d", &a[i]); //给定排列中的n个数字,对应算法描述的(1)
        for (i = 0; i < k; i++)
            NextPermutation(n); //通过此函数修改全局数组a
        for (i = 0; i < n; i++)
            printf("%d", a[i]);
        printf("\n");
        m--;
    }
    return 0;
}