[46] Permutations

排列組合...
不知道為什麼完全沒有sense 囧
各種寫不出來 囧
還有就是
用C寫的人真的那麼少嗎嗎嗎嗎嗎(抱頭)

假會的N階function 好像反而慢XD
用一個for其實也才兩行Orz
是怎樣～我就是沒天份啦（奔入雨中)

結束的地方總覺得哪裡怪怪的 (是哪裡)
原來終止的時候就是整個array複製下來輸出的時候 @__@
光是把pointer array弄去遞迴再傳回來就覺得快使惹
為什麼我不開開心心的去喝咖啡吃蛋糕,
再隨便找個不需要考演算法的工作就好了呢?!
（話雖這麼說, 我這麼自虐寫leetCode,
讓我面上好嗎讓我面上好嗎請發我offer啊啊啊啊啊啊啊啊~~~~（各種鬼叫))

Permutations

/**

 * Return an array of arrays of size *returnSize.

 * Note: The returned array must be malloced, assume caller calls free().

 */

int factorial(int input)

{

    if (input ==1)

        return 1;

    return input * factorial(input-1) ;

}

void swap(int *a,int *b)

{

    int tmp;

    tmp = *a;

    *a = *b;

    *b = tmp;

    return;

}

void mypermute(int* nums,int index,int** ret, int numsSize, int *retIndex)

{

    int k;

    if(index == numsSize-1)

    {

#if 0   //mine

        for (int j=0; j<numsSize; j++)

        {

            ret[*retIndex][j] = nums[j];

        }

        *retIndex= *retIndex+1;      

#else

        memcpy(ret[(*retIndex)++], nums, (numsSize) * sizeof(int));

#endif

        return;

    }

    

    for(k=index;k<numsSize;k++)

    {

        swap(&nums[index], &nums[k]);

        mypermute(nums,index+1, ret, numsSize, retIndex);

        swap(&nums[index], &nums[k]);

    }

    return;

}

int** permute(int* nums, int numsSize, int* returnSize) {

    int i;

#if 0   //mine

    *returnSize = factorial(numsSize);

#else

    *returnSize =1;

    for(i = numsSize; i > 1; i--)  

    {  

        (*returnSize) *= i;  

    }  

#endif

    

    int **ret = malloc(sizeof(int*)*(*returnSize));

    for (i=0;i<(*returnSize);i++)

    {

        ret[i] = malloc(sizeof(int)*(numsSize));

    }

    int retIndex = 0;

    mypermute(nums, 0, ret, numsSize,&retIndex);

    return ret;

}

20230714 更新

多年以後，input 不知道為什麼多了一個感覺沒什麼用的 returnColumnSizes?! (thinking 圖)

可能是為了統一用在一些回傳的 int**會有不同size的情況吧？！（thinking圖again）

覺得已經腦死，我已經不會寫code了，我連階乘都寫不出來了........

/**

* Return an array of arrays of size *returnSize.

* The sizes of the arrays are returned as *returnColumnSizes array.

* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().

*/

int factorial(int size)

{

if (size==1)

return 1;

return size * factorial(size-1);

}

void swap(int *a, int *b)

{

int tmp;

tmp=*a;

*a=*b;

*b=tmp;

return;

}

void myPermute(int* nums,int numsSize, int *curr, int start, int end, int **ret)

{

if (start == end)

{

memcpy(ret[(*curr)++],nums,sizeof(int)*numsSize);

return;

}

for (int j=start;j<=end;j++)

{

swap(&nums[start],&nums[j]);

myPermute(nums,numsSize,curr,start+1,end,ret);

swap(&nums[start],&nums[j]);

}

return;

}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){

int count= factorial(numsSize);

*returnSize = count;

int **ret = malloc(sizeof(int*)* (count));

*returnColumnSizes= malloc (sizeof(int)*(count));

for (int i=0;i<(count);i++)

{

ret[i]=malloc(sizeof(int)*numsSize);

(*returnColumnSizes)[i]= numsSize;

}

count=0;

myPermute(nums, numsSize,&count,0,numsSize-1,ret);

return ret;

}

#if 0

=> 1,2,3,4

1,(2,3,4)

2,(1,3,4)

3,(1,2,4)

4,(2,3,4)

=> 1,2,3

1,(2,3)

2,(1,3)

3,(1,2)

=> 1,2

1,(2)

2,(1)

=>

1

#endif