permutation.md

Permutation

全排列

Problem

Given a collection of distinct numbers, return all possible permutations.

For example, [1,2,3] have the following permutations:

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

分析

给定一个数组，返回其所有的排列方式，逆序和正序是不同的数组
一般用递归的算法实现

解决方案

回想我们全排列的方法，第一个数确定，排列剩余n-1个数，同理，依次如此
设定一个指针数组用于确定每行中固定的数,标志当前正在使用的数，使用完再解除

编程实现

/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
void function(int **result,int *nums,int numsSize,int *returnSize,bool* temp,int *array,int size)
{
    int i=0;
    if(size==numsSize)  //给每行的最后一个元素赋值后，遍历赋值给返回的数组result
    {
        result[*returnSize]=(int*)malloc(sizeof(int)*numsSize); //动态内存分配，每行元素个数都为numsSize
        for( i=0;i<numsSize;i++)
            result[*returnSize][i]=temp[i];
        size=0; 
        (*returnSize)++;  //将size重新赋值为0，*returnSize加一，写下一行数组
        return;
    }
    
    for(i=0;i<numsSize;i++)
    {
        if(!array[i])
        { //标志当前的数，使用后解除
            array[i]=true;
            temp[size]=nums[i];
            function(result,nums,numsSize,returnSize,temp,array,size+1);
            array[i]=false;
        }
    }
}
int** permute(int* nums, int numsSize, int* returnSize) {    
    int **result=(int **)malloc(sizeof(int*)*10000000);
    int* array[numsSize];
    bool* temp[numsSize]; //指针型数组
    if(nums==NULL||numsSize==0)
    {
        *returnSize=0;
        return result;
    }
    *returnSize=0;
    int size=0;
    memset(array,(bool)false,numsSize);
    function(result,nums,numsSize,returnSize,temp,array,size);
    return result;
}

总结

参考资料