[Matlab] 递归回溯求排列数

回溯算法是以深度优先搜索解的方法，以前还不是很熟悉递归，不过今天仔细想了想递归回溯搜索解确实是个简单快速的求解方法，就是有时候想的有点烧脑...

题目：给出abcd...这些字母求他们的全部排列组合

这个实际上用matlab自带的perms函数一下就能求解一个全排列矩阵，然后把1,2,3...这些数用a,b,c...字母代替就行，不过那样复杂度就大了，毕竟没有原生为字母排列的函数，那么用回溯法递归求解该问题matlab可编写如下：

function result = abcPerms(n)
    result.count = 0;
    result.cell = {};
    result = traceback(result, \'\', 0:n-1);
    function result = traceback(result, cur, arr)
        base = abs(\'a\');
        if isempty(arr)
            result.count = result.count + 1;
            result.cell{result.count} = cur;
            disp(cur);
            return;
        end
        for i = 0:length(arr)-1
            result = traceback(result, [cur,char(base+arr(i+1))], arr(~(arr==arr(i+1))));
        end
    end
end

　　如执行abcPerms(3)即可得到结果：

>> abcPerms(3)

abc

acb

bac

bca

cab

cba

ans =

包含以下字段的 struct:

count: 6

cell: {\'abc\' \'acb\' \'bac\' \'bca\' \'cab\' \'cba\'}