给定2个数组Array1 = {a,b,c...n},Array2 = {10,20,15....x}如何生成所有可能的组合作为字符串a(i)b(j)c(k)n(p)
其中
1 <= i <= 10, 1 <= j <= 20 , 1 <= k <= 15, .... 1 <= p <= x
如:
a1 b1 c1 .... n1
a1 b1 c1..... n2
......
......
a10 b20 c15 nx (last combination)
所以在所有组合的总数=元素的产品 array2 =
(10 X 20 X 15 X ..X x)
类似于笛卡尔积,其中第二个数组定义第一个数组中每个元素的上限.
固定数字的示例,
Array x = [a,b,c]
Array y = [3,2,4]
所以我们将有3*2*4 = 24种组合.结果应该是:
a1 b1 c1
a1 b1 …从这篇维基百科文章:
http://en.wikipedia.org/wiki/Hamiltonian_path_problem
在大多数图上快速的哈密顿路径的随机算法如下:从随机顶点开始,如果没有访问的邻居则继续.如果没有更多未访问的邻居,并且形成的路径不是哈密顿量,则随机均匀地选择邻居,并使用该邻居作为枢轴进行旋转.(即,向该邻居添加边缘,并从该邻居中移除一个现有边缘,以便不形成循环.)然后,在路径的新端继续算法.
我不太明白这个旋转过程应该如何工作.有人可以更详细地解释这个算法吗？也许我们最终可以用更清晰的描述更新Wiki文章.
编辑1:我认为我现在理解算法,但它似乎只适用于无向图.任何人都可以证实吗？
这就是为什么我认为它只适用于无向图:
alt text http://www.michaelfogleman.com/static/images/graph.png
假装顶点的编号如下:
123
456
789
让我们说我到目前为止的道路是:9, 5, 4, 7, 8.所有8个邻居都被访问过.假设我选择5来删除边缘.如果我删除(9,5),我最终创建一个循环:5, 4, 7, 8, 5所以我似乎必须删除(5,4)并创建(8,5).如果图是无向的,那很好,现在我的路径是9,5,8,7,4.但是如果你想象那些边被定向,那不一定是有效路径,因为(8,5)是边但是( 5,8)可能不是.
编辑2:我想对于一个有向图我可以创建(8,5)连接,然后让新路径正好4, 7, 8, 5,但这似乎适得其反,因为我必须砍掉以前导致顶点5的所有内容.