表示矩阵的有效数据结构
表示矩阵的有效数据结构
提问于 2013-10-30 16:56:08
我目前正在为一所大学的考试时间表制定一个解决方案。我在考虑使用遗传算法。
现在，我从一个简单的例子开始，这样我就能了解到正在发生的事情，因为我对这一切都很陌生。在这个例子中，我有10个考试，6个学生和6个可用的时段。我代表一个染色体，在一个位串中有10个位置，值从1到6不等，代表时隙，例如：[3 1 4 1 3 5 5 6 4 2]意味着考试1发生在第三个时隙，考试2发生在第一个时隙，等等……
现在，如果我有一个数组来表示每个学生参加的是哪些考试：
int[][] students_exams =
{
{3, 1, 2, 5, 8}, // student 1
{10, 4, 5, 7}, // student 2
{1, 2, 3, 6}, // student 3
{2, 7, 4, 5}, // student 4
{1, 6, 2, 10}, // student 5
{8, 9, 1, 3} // student 6
};如何有效地将此信息表示为n×n矩阵，其中n为考试次数(在本例中为10)，其中Mi等于参加考试一和考试j的学生人数？
是否有我可以使用的数据结构，或者我是否必须将每一次考试与彼此的考试进行比较，并有一个递增计数器？因为考虑到这一点，我认为这对我在现实中的学生数量和考试都是没有效率的。
如果你能给我参考任何论文或参考资料，你将对我有很大的帮助。
谢谢
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-10-30 19:06:36
以下是您可能试图避免的蛮力方法：
class testMatrixSO{
public static void main(String[] args){
int[][] students_exams =
{
{3, 1, 2, 5, 8}, // student 1
{10, 4, 5, 7}, // student 2
{1, 2, 3, 6}, // student 3
{2, 7, 4, 5}, // student 4
{1, 6, 2, 10}, // student 5
{8, 9, 1, 3} // student 6
};
int[][] finalMatrix = new int[10][10];
//here is the part that creates your matrix
for(int i=0; i<students_exams.length; i++)
for(int j=0; j<students_exams[i].length; j++)
for(int k=0; k<students_exams[i].length; k++)
if(j != k) finalMatrix[students_exams[i][j]-1][students_exams[i][k]-1]++;
//print results
for(int i=0; i < finalMatrix.length; i++){
for(int j=0; j < finalMatrix[i].length; j++)
System.out.print(finalMatrix[i][j] + " ");
System.out.println();
}
}
}在积极的方面，如果你假设每个学生会有6次或更少的考试，那么我们可以自信地说，更新矩阵的循环执行的次数少于(学生数)*(6*6)次。即算法是线性的，O(n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19689136
复制相关文章
相似问题
腾讯云开发者
