Board logo

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

作者: 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 编辑
  1. my @elements = qw/a b c d e f g/;
  2. permute( [@elements], [] );
  3. sub permute
  4. {
  5.     my ( $elements ) = @_;
  6.     my @stk_ele = ( $elements );
  7.     my @stk_tmp= ( [] );
  8.     while ( $#stk_ele >= 0 )
  9.     {
  10.         my $ele = pop @stk_ele;
  11.         my $tmp = pop @stk_tmp;
  12.         printf "%s\n", join(",", @$tmp ) if $#$ele < 0;
  13.         for my $id ( 0 .. $#$ele )
  14.         {
  15.             push @stk_ele, [ @{$ele}[0..$id-1, $id+1..$#$ele] ];
  16.             push @stk_tmp, [ @$tmp, $ele->[$id] ];
  17.         }
  18.     }
  19. }
复制代码
堆栈版的来了。
虽然花了些时间,不过做出来发现蛮有趣的
因为是先把状态 push 到栈中,通过循环逐层解出,所以得出的结果是反向的,d c b a -> d c a b -> .... -> a b c d。

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

递归代码
  1. my @elements = qw/a b c d e f g h i j/;
  2. permute( [@elements], [] );
  3. sub permute {
  4.     my ($ele, $tmp ) = @_;
  5.     #printf "%s\n", join(",", @$tmp) unless ( @$ele );
  6.     for my $i ( 0 .. $#$ele ) {
  7.         permute( [@{$ele}[0..$i-1, $i+1..$#$ele]], [@$tmp, $ele->[$i]] );
  8.     }
  9. }
复制代码
也许换编译型语言耗时结果会不一样,懒得写了。




欢迎光临 批处理之家 (http://www.bathome.net/) Powered by Discuz! 7.2