perl关于迭代回溯和递归回溯的代码实现

pp1984829

如图二维数组
@a = {
(a,b,c,d,e)
(f,g,h,i,j,k)
(l,m,n,o,p)
(q,r,s,t,u)
(v,w,x,y,z)
}

题目是从二维数组的每一行的数组中选出一个元素，列举出所有的组合方式.
例如可行组合（a，f，l，q，v），（b，h，o，s，z）等。
现在我用递归回溯的算法解出了答案，遇到很比较大的数组时效率很低，想求一迭代回溯的实现方法提高效率。@a二维数组是我列举的例子，实际场景中二维数组的元素个数未知为n.

类似于这个C的题目：从m个数里面选择n个数的组合
















五、回溯法   

    回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。






希望高手能出手，给出迭代回溯的代码,非常感谢！

pp1984829

题目类似于经典的8皇后问题，只不过没有剪纸，而是列举出所有组合。

rubyish

大牛 bruceteen NO 递归 一个for循环来做的算法
http://bbs.chinaunix.net/thread-4084329-1-1.html

1. my @A = ( [ 1 .. 4 ], [ 'A' .. 'C' ], [ 'a', 'b' ], [ 10 .. 13 ] );
   
2. 
   
3. sub Combine {
   
4.     my ( $all, $t ) = ( 1, 1 );
   
5.     my @E = map { scalar @$_ } @_;
   
6.     $all *= $_ for @E;
   
7.     my @M = reverse( 1, map { $t = $t * $E[ -$_ ] } 1 .. $#E );
   
8.     for my $i ( 0 .. $all - 1 ) {
   
9.         my @I = map $i / $M[$_] % $E[$_], 0 .. $#M;
   
10.         say join $", map $_[$_][ $I[$_] ], 0 .. $#I;
    
11.     }
    
12. }
    
13. Combine @A;

复制代码

rubyish

del~

rubyish

大牛 Perlvim NO 递归 for循环来做的算法:
http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=3747978

1. my @A = ( [ 1 .. 4 ], [ 'A' .. 'C' ], [ 'a', 'b' ], [ 10 .. 13 ] );
   
2. sub Combine {
   
3.     my @R = @{ +shift };
   
4.     for my $e (@_) {
   
5.         @R = map { my $r = $_; map "$r $_", @$e } @R;
   
6.     }
   
7.     return @R;
   
8. }
   
9. my @w = Combine @A;
   
10. say for @w;

复制代码