UC知道java超难的一道算法题：交错操作，请教
来源：百度知道 编辑：UC知道 时间：2024/05/23 23:06:11
如下面这个三行，每行元素不固定的二维Vector V
A、B、C、D
H、I、J、K、M
X、Y、Z
求出满足以下条件的所有Vector D：
1.此Vector D的元素包含V的所有元素，且每个元素仅出现一次
2.此Vector D中包含在V【1】中的元素之间的顺序不能发生改变，即A、B、C、D之间的顺序不发生改变，同理，V【2】、V【3】。。。。都不发生改变。
对于本例，也就是说，在结果D中，A、B、C、D的先后顺序不变，H、I、J、K、M的先后顺序不变，X、Y、Z的先后顺序不变。
结果D的几种可能的情况是：
1：A、B、C、D、H、I、J、K、M、X、Y、Z
2：H、I、A、B、C、X、D、J、K、Y、Z、M
3：A、H、I、X、Y、Z、B、C、J、K、M、D
等等
一定要注意，是要求出所有可能的情况。
我想了十几天了，都没有找到好方法，求教大家！！求教高手
用递归
大概说一哈算法：
从A出发，有三个方向可走，B,H 或 X
如果选B，则从B出发也是三个方向，C , H, 或X
如果选H，则从H出发也是三个方向，B， I，或X
如果选X，则从X出发也是三个方向，B， H, 或Y
也就是说在任何一个点上都是N条路可走，N为二维VECTOR的行数，有3行就有3条路可走，有100行就有100条路可走。
建立一个含N个元素数组arr用来存放各行VECTOR目前所处位置。例如如果选择路径：ABHXYZ，则数组arr[0]=2; arr[1]=1; arr[2]=3;
如果对应行的位置超过该行长度，则该行跳过。
建立一个数组用来存放组合，递归从零开始增加，等于二维向量元素总数时打印并返回。
粗略代码：
string[][] vec = new string[N][];//N行向量
for(int i = 0; i < N; ++i)
vec[i] = new string[M];//每行M个元素，也可设为不同的值
int lim = N * M;//元素总数
int[] arr = new int[N]//存放向量位置的数组，初始化为零
string[] com = new string[lim]//存放组合的数组
//递归函数:idx表示当前com所处的位置，其他参数和上面的变量对应
void func(int[] arr, string[][] vec, string[] com, int lim, int idx) {
if(idx == lim)
for(int j = 0; j < lim; ++j)
System.out.pringln(com[j]);//打印组合
return;
for(int i = 0; i < N; ++i)//从一个点开始，遍历所有可能路径
if(arr[i] < vec[i].length){ /