C实现多个数组选元素的组合迭代回溯的问题

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个数的组合

















五、回溯法   

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






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

bruceteen

每行有5个元素，共有5行，所以一共有5^5=3125种组合方式
所以代码简单，如下

1. for( size_t i=0; i<3125; ++i )
   
2. {
   
3.     int r0 = i/625%5;
   
4.     int r1 = i/125%5;
   
5.     int r2 = i/25%5;
   
6.     int r3 = i/5%5;
   
7.     int r4 = i/1%5;
   
8.     // 以上代码当然可以用一个for循环来做
   
9. 
   
10.     printf( "%d %d %d %d %d\n", buf[0][r0], buf[0][r1], buf[0][r2], buf[0][r3], buf[0][r4] );
    
11. }

复制代码

pp1984829

回复 2# bruceteen

非常感谢您的答复，但是实际场景中二维数组的元素数是不确定的，所有就没有办法知道到底用几个for循环，所以需要迭代回溯，动态规划的那种。


   

bruceteen

pp1984829 发表于 2013-06-03 08:59
回复 2# bruceteen
非常感谢您的答复，但是实际场景中二维数组的元素数是不确定的，所有就没有办法知道到底用几个for循环，所以需要迭代回溯，动态规划的那种。

你到底看了我的代码没有？ 哪来的“几个for循环”？

pp1984829

回复 4# bruceteen

好吧，我看错了，但是我还是想要迭代回溯的代码，不过还是谢谢你。


   

linux_c_py_php

递归本来就慢, 没办法的.

你可以手写解开1-2层递归, 可以缩减递归的次数.