Question

java超难的一道算法题：交错操作，请教

有一个二维Vector，每个元都是字符串（或者其他对象），
如下面这个三行，每行元素不固定的二维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
等等
一定要注意，是要求出所有可能的情况。

我想了十几天了，都没有找到好方法，求教大家！！求教高手

Answer 1

用递归
大概说一哈算法：
从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){ //该行位置是否超过长度
com[idx] = vec[i][arr[i]];//取出该行元素
arr[i]++;//位置+1
func(arr, vec, com, lim, idx + 1);//递归
arr[i]--;//递归结束后恢复本行的位置值，取下一行
}

//调用：func(arr, vec, com, lim, 0);
//刚接触JAVA，代码比较糙，凑合看吧

//下面的代码已经调试，还没学VECTOR，用二维数组代替了，并加了计数器

public class Combo {
static private void func(char[][] vec) {
int lim = 0;
int nvec = vec.length;
for(char[] vel : vec)
lim += vel.length;
int[] arr = new int[nvec];
for(int el : arr)
el = 0;

char[] com = new char[lim];

func(vec, nvec, lim, arr, com, 0);
}

static private void func(char[][] vec, int nvec, int lim, int[] arr, char[] com, int idx){
if(idx == lim){
System.out.print("(" + ++combo_cnt + ")");//发现组合，计数器+1并输出
for(char el : com)
System.out.print(el + " ");
System.out.println();
return;
}

for(int i = 0; i < nvec; ++i)
if(arr[i] < vec[i].length){
com[idx] = vec[i][arr[i]++];
func(vec, nvec, lim, arr, com, idx + 1);
--arr[i];
}
}

public static void main(String[] arg) {
char[][] vec = { {'A', 'B', 'C', 'D'},
{'H', 'I', 'J', 'K', 'M'},
{'X', 'Y', 'Z'}
};
func(vec);
}

private static int combo_cnt = 0;//计数器；
}

//部分输出结果：
(9858)H A B I J X Y K C Z M D
(9859)H A B I J X Y K M C D Z
(9860)H A B I J X Y K M C Z D
(9861)H A B I J X Y K M Z C D
(9862)H A B I J X Y K Z C D M
(9863)H A B I J X Y K Z C M D
(9864)H A B I J X Y K Z M C D
(9865)H A B I J X Y Z C D K M
(9866)H A B I J X Y Z C K D M
(9867)H A B I J X Y Z C K M D
(9868)H A B I J X Y Z K C D M
(9869)H A B I J X Y Z K C M D
(9870)H A B I J X Y Z K M C D
(9871)H A B I X C D J K M Y Z
(9872)H A B I X C D J K Y M Z
(9873)H A B I X C D J K Y Z M
(9874)H A B I X C D J Y K M Z
(9875)H A B I X C D J Y K Z M
(9876)H A B I X C D J Y Z K M
(9877)H A B I X C D Y J K M Z
(9878)H A B I X C D Y J K Z M
(9879)H A B I X C D Y J Z K M
(9880)H A B I X C D Y Z J K M

Answer 2

如果出现：
A、B、C、D
C、B、A、K、M
X、Y、Z 这种情况，那么 就不能满足 条件2.此Vector D中包含在V【1】中的元素之间的顺序不能发生改变，即A、B、C、D之间的顺序不发生改变，同理，V【2】、V【3】。。。。都不发生改变。

那么假设 没有上面的非法情况发生， 我给你以下的解决这种列出所有组合的通用方法：
把问题转换成 图的遍历问题，并把所有遍历结果列出来就是所有排列，你把上面的那些必须满足的条件作为 图的遍历过程的遍历约束。并把遍历的起点和终点都用空字符！！

举例说明，给10个城市，列出，把10个城市走一圈个各种方案。（如果加上把各种方案中最短路程的方案排序出来，那么就是经典的TSP问题的穷举法了）
如果加上限制条件，就是和你的问题一样了。

Answer 3

class Test
{
private static int sum=1;
private static final int SIZE=12;
public static void main(String[] args)
{
String[][] arrThree={{"A","B","C","D"},{"H","I","J","K","M"},{"X","Y","Z"}};
ArrayList str=new ArrayList();
int count=0;
int one=0;
int two=0;
int three=0;
fn1(arrThree,str,count,one,two,three);
}

public static void fn1(String[][] arr,ArrayList str,int count,int one,int two,int three){
for(int i=0;i<3;i++){
if(one<4&&i==0){
str.add(arr[i][one++]);
count++;
if(count!=SIZE){
fn1(arr,(ArrayList)str.clone(),count--,one,two,three);
str.remove(count);
one--;
}
}else if(two<5&&i==1){
str.add(arr[i][two++]);
count++;
if(count!=SIZE){
fn1(arr,(ArrayList)str.clone(),count--,one,two,three);
str.remove(count);
two--;
}
}else if(three<3&&i==2){
str.add(arr[i][three++]);
count++;
if(count!=SIZE){
fn1(arr,(ArrayList)str.clone(),count--,one,two,three);
str.remove(count);
three--;
}
}else{
continue;
}

if(count==SIZE){
System.out.println("第"+sum+++"种:");
for(int j=0;j<SIZE;j++){
System.out.print(str.get(j)+",");
}
//count=0;
System.out.println();
return;
}
}
}
}

Answer 4

我忘了 对不起了！！

Answer 5

无聊