如何在矩阵中打印除重复列以外的所有可能路径 [英] How do I print all possible path in matrix except duplicate column

问题描述

当我有以下矩阵

when I have the Matrix below

          X1	 X2	 X3	 X4
Y1	1.00	0.11	0.07	0.50
Y2	0.22	0.07	0.30	0.14
Y3	0.00	0.06	0.06	0.08

如何用java打印以下所有路径

how can I print all following path with java

X1Y1-> X2Y2-> X3Y3
            -> X4Y3
        X3Y2-> X2Y3
            -> X4Y3
        X4Y2-> X2Y3
            -> X3Y3
 X2Y1-> X1Y2-> X3Y3
            -> X4Y3
        X3Y2-> X1Y3
            -> X4Y3
        X4Y2-> X1Y3
            -> X3Y3
 X3Y1-> X1Y2-> X2Y3
            -> X4Y3
        X2Y2-> X1Y3
            -> X4Y3
        X4Y2-> X1Y3
            -> X2Y3

 X4Y1-> X1Y2-> X2Y3
            -> X3Y3
        X2Y2-> X1Y3
            -> X3Y3
        X1Y2-> X2Y3
            -> X3Y3

我尝试使用Dijkstra的算法，这可以给我最短的路径。

但是对于我的工作我需要查看除上面示例中显示的重复列之外的所有可能路径。我怎么能这样做???。请帮帮我!!!由于我的截止日期。

但我不知道：（

I try to do that by using Dijkstra's algorithm that can give me shortest path.
But for my work I need to look all possible path except duplicate column that show in above example. How can I do that???.Please help me!!! Due to my deadline.
But I have no idea :(

推荐答案

现在我实现了一个简单的源代码来查找所有可能的路径矩阵。然后选择了唯一的行和列。但由于时间的复杂性，我们怎样才能直接得到唯一的路径。这是我的源代码。

Now I implemented a easy source code to find all possible paths in matrix.Then selected the unique row and column.But due to time complexity how can we can get directly unique path.this is my source code.

import java.util.*;    public class MyAllPath {
    	public static ArrayList<String> allPaths;
    	public static void printpaths(double[][] matrix) {	
    		String[] path = new String[matrix.length];
 
		for (int i = 0; i < matrix[0].length; i++)
		{
			printpaths(matrix, path, 0, 0, i);
		}
	}
 
	private static void printpaths(double[][] matrix, String[] path, int index, int row, int column)
	{
		path[index++] = Integer.toString(column)+"|"+Double.toString(matrix[row][column])+"\t";
		row++;
		if (row == matrix.length)
			{
				print(path);
			}
		else if (row < matrix.length) 
		{
			int boundary = matrix[0].length-1;
			for (int i = column - boundary; i <= column + boundary; i++)
			{
				if (i > -1 && i < matrix[0].length)
				{
					printpaths(matrix, path, index, row, i);
				}
			}
		}
	}
 
	private static void print(String[] path) 
	{
		String myPath="";
		for (int i = 0; i < path.length; i++)
		{
			myPath+=path[i]+" ";
			System.out.print(path[i] + " ");
		}
		System.out.println();
		allPaths.add(myPath);
	}
 
 
	public static void main(String args[]) 
	{
		allPaths =new ArrayList<String>();
		double[][] matrix = {{1, 2, 3},
							{4, 5, 6}, 
						    {7, 8, 9}};
		printpaths(matrix);
		System.out.println("-------------------------------------------------------");
		for(int i=0;i<allPaths.size();i++)
		{
			String[] path= allPaths.get(i).split(" ");
			TreeSet<Integer> duplicateColumn = new TreeSet<Integer>();
			for(int j= 0;j<path.length;j++)
			{
				String[] word=path[j].split("\\|");
 
				for(int k=0;k<word.length;k++)
				{
					duplicateColumn.add(Integer.parseInt(word[0]));
				}
			}
			if(duplicateColumn.size()==path.length)
				System.out.println(allPaths.get(i));
 
		}
	}
    }

这篇关于如何在矩阵中打印除重复列以外的所有可能路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！