523066680

所以楼主说的是排列还是组合？没有说明组合的字符个数，应该是排列吧？
通过进制转换原理获得排列的模板，参考自《Higher-Order Perl》

523066680

回复 4# minase


    所以你要深度搜索解元素排列的非递归版本。递归转非递归，用堆栈呗。
建议改一下标题：批处理如何求排列组合(非递归)

    非递归的两个算法其他链接里面已经有了，只不过不是深度搜索，是其他算法。

523066680

my @elements = qw/a b c d e f g/;
permute( [@elements], [] );

sub permute
{
    my ( $elements ) = @_;
    my @stk_ele = ( $elements );
    my @stk_tmp= ( [] );
    while ( $#stk_ele >= 0 )
    {
        my $ele = pop @stk_ele;
        my $tmp = pop @stk_tmp;
        printf "%s\n", join(",", @$tmp ) if $#$ele < 0;
        for my $id ( 0 .. $#$ele )
        {
            push @stk_ele, [ @{$ele}[0..$id-1, $id+1..$#$ele] ];
            push @stk_tmp, [ @$tmp, $ele->[$id] ];
        }
    }
}
复制代码

堆栈版的来了。
虽然花了些时间，不过做出来发现蛮有趣的
因为是先把状态 push 到栈中，通过循环逐层解出，所以得出的结果是反向的，d c b a -> d c a b -> .... -> a b c d。

本机测试对比：
10个元素排列，去掉输出，递归版 12.3秒，非递归版 14.2秒

递归代码

my @elements = qw/a b c d e f g h i j/;
permute( [@elements], [] );

sub permute {
    my ($ele, $tmp ) = @_;
    #printf "%s\n", join(",", @$tmp) unless ( @$ele );
    for my $i ( 0 .. $#$ele ) {
        permute( [@{$ele}[0..$i-1, $i+1..$#$ele]], [@$tmp, $ele->[$i]] );
    }
}
复制代码

也许换编译型语言耗时结果会不一样，懒得写了。