批处理之家 - Powered by Discuz! Board

标题: [数值计算] 批处理如何计算数字的排列组合 [打印本页]

作者: minase 时间: 2021-5-5 07:42 标题: 批处理如何计算数字的排列组合

有一组数字1,2,3,4，如何打印出这组
数字所有组合？批处理论坛的大侠能
否用批处理描述一下。我想得到的代
码是不要用4重循环来写，也不要用
递归。我想看的代码是深度搜索的算
法。

思路是这样的，初始化的时候flag标志
为1，表示数值没有被访问，当数值大于
4的时候就回溯。

作者: 523066680 时间: 2021-5-5 17:20

本帖最后由 523066680 于 2021-5-5 17:22 编辑

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

作者: minase 时间: 2021-5-5 17:49

回复 3# 523066680

我是想学习深度搜索的算法来实现排列组合，这个检索的方法要比多重循环效率高。
可惜我搜索到的代码是python写的，用的是递归的方法。我现在不知道怎么把代码
转换成非递归的描述。

如果perl有深度搜索的的排列的算法，版主能贴出来吗？其它语言C#,C++也是可以的。
我遇到的问题是非递归的写法不会。
网络的关键字是bsf深度搜索。

作者: minase 时间: 2021-5-5 17:52

回复 3# 523066680

它是思想方法是
回溯的条件cur=4,flag=1,1,1,1同时成立。

初值的情况，

cur = 1
flag = 0,0,0,0

1===>0,2===>0,3===>0,4===>0
1===>0,2===>0,3===>0,4===>0
1===>0,2===>0,3===>0,4===>0
1===>0,2===>0,3===>0,4===>0

1 2 3 4
此时cur=4，
flag = 1,1,1,1
数据1,2,3,4

1===>1,2===>0,3===>0,4===>0
1===>0,2===>1,3===>0,4===>0
1===>0,2===>0,3===>1,4===>0
1===>0,2===>0,3===>0,4===>1

因为此时cur=4,所以减去2进行回溯
flag = 1,1,0,0
1===>1,2===>0,3===>0,4===>0
1===>0,2===>1,3===>0,4===>0
1===>0,2===>0,3===>1,4===>0
1===>0,2===>0,3===>0,4===>1

这样会得到1,2,3,4和1,2,4,3两组值,
我怎么知道1,2,3,4这个路径已经被
访问过了？

刚才我的思路还是没有整理出来？基础算法我没有学会啊，编程好难。

作者: 523066680 时间: 2021-5-5 22:37

本帖最后由 523066680 于 2021-5-6 09:58 编辑

回复 4# minase

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

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

作者: 523066680 时间: 2021-5-6 09:39 标题: 非递归版

本帖最后由 523066680 于 2021-5-6 10:18 编辑

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]] );
    }
}
复制代码

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

欢迎光临批处理之家 (http://www.bathome.net/)