[已解决]一个关于生成矩阵的问题

Liu_xy

要求：给定n,k两个值。生成一个k行n列的矩阵。每一行的元素都是从1到n的。
其中每一行中的元素不能有重复的数字，每一列中的元素也不能有重复的数字。
而且还有个要求：每一列不能出现所在列的那一个数字。比如第一列中就不能出现数字1  第二列就不能出现数字2等等。。

例如 一个k=2,n=5的矩阵 （2*5的矩阵
必须是 （1 2 3 4 5）（表示列的数字，不是矩阵里面的）
              2  3  4  5  1
              3  1  5  2  4
这样的形式。

结果可以用一个列表或多个列表表示都没关系。。。

题主写了一个不满足最后一个要求的（实在想不到，先简化了一下），但是效率实在低下啊。生成一个10*10的矩阵都要很久。。。

哪位大神有好一点的方法？？求指导啊！！

最佳答案

月排行榜 / 总排行榜

shuofxz

2016-3-13 20:55:12

想了挺久写了如下代码
但是还是有bug，在一定情况下会出现死循环，等我这两天再想想怎么解决
或者你有没有什么好的算法，我这个就是让计算机暴力破解

1. import random
   
2. k = int(input("请输入有多少行："))
   
3. n = int(input("请输入有多少列："))
   
4. 
   
5. def shuzu():
   
6.     sum = []
   
7. 
   
8.     for i in range(k):
   
9.         #print(sum)
   
10.         num = [x+1 for x in range(n)]
    
11. 
    
12.         num_copy = num[:]
    
13.         sum.append([])
    
14.         
    
15.         for j in range(n):
    
16.             num_copy = num[:]
    
17.             
    
18.             if j+1 in num_copy:
    
19.                 num_copy.remove(j+1)
    
20.             
    
21.             for each in range(i):
    
22.                 if sum[each][j] in num_copy:
    
23.                     num_copy.remove(sum[each][j])
    
24. 
    
25.             #print(num_copy)
    
26.             if num_copy == []:
    
27.                 shuzu()
    
28.             #choice = num_copy.pop()
    
29. 
    
30.             choice = random.choice(num_copy)
    
31.             #print(choice)
    
32. 
    
33.             sum[i].append(choice)
    
34.             num.remove(choice)
    
35. 
    
36.     for each_line in sum:
    
37.         print(each_line)
    
38.                
    
39. shuzu()

复制代码

跳转到最佳答案楼层

shuofxz

想了挺久写了如下代码
但是还是有bug，在一定情况下会出现死循环，等我这两天再想想怎么解决
或者你有没有什么好的算法，我这个就是让计算机暴力破解

1. import random
   
2. k = int(input("请输入有多少行："))
   
3. n = int(input("请输入有多少列："))
   
4. 
   
5. def shuzu():
   
6.     sum = []
   
7. 
   
8.     for i in range(k):
   
9.         #print(sum)
   
10.         num = [x+1 for x in range(n)]
    
11. 
    
12.         num_copy = num[:]
    
13.         sum.append([])
    
14.         
    
15.         for j in range(n):
    
16.             num_copy = num[:]
    
17.             
    
18.             if j+1 in num_copy:
    
19.                 num_copy.remove(j+1)
    
20.             
    
21.             for each in range(i):
    
22.                 if sum[each][j] in num_copy:
    
23.                     num_copy.remove(sum[each][j])
    
24. 
    
25.             #print(num_copy)
    
26.             if num_copy == []:
    
27.                 shuzu()
    
28.             #choice = num_copy.pop()
    
29. 
    
30.             choice = random.choice(num_copy)
    
31.             #print(choice)
    
32. 
    
33.             sum[i].append(choice)
    
34.             num.remove(choice)
    
35. 
    
36.     for each_line in sum:
    
37.         print(each_line)
    
38.                
    
39. shuzu()

复制代码

Liu_xy

shuofxz 发表于 2016-3-13 20:55
想了挺久写了如下代码
但是还是有bug，在一定情况下会出现死循环，等我这两天再想想怎么解决
或者你有没 ...

先谢谢大神的回答啊～我也是暴力运算的，所以才会导致我写的结果非常的慢。。。我是初学者，有些技巧还不是很熟练！我也正在思考好的办法，如果有想法会第一时间发上来的！！

Liu_xy

shuofxz 发表于 2016-3-13 20:55
想了挺久写了如下代码
但是还是有bug，在一定情况下会出现死循环，等我这两天再想想怎么解决
或者你有没 ...

当k>n的时候好像会出现死循环吧？

冬雪雪冬

Liu_xy 发表于 2016-3-13 21:14
当k>n的时候好像会出现死循环吧？

k≥n时不成立，比如n=k=2则
2 1
1 2
不符合每一列不能出现所在列的那一个数字。

Liu_xy

冬雪雪冬 发表于 2016-3-13 22:04
k≥n时不成立，比如n=k=2则
2 1
1 2

嗯，我也发现了。应该再加一个k<n的前提～～

冬雪雪冬

是给出一种答案，还是要所有可能的。

Liu_xy

冬雪雪冬 发表于 2016-3-13 22:25
是给出一种答案，还是要所有可能的。

给出一种答案就行，不需要所有可能～

冬雪雪冬

不知是否我理解有误，应该很简单的。

1. n = 5
   
2. k = 4
   
3. list1 = [[] for i in range(k)]
   
4. 
   
5. for k1 in range(k):
   
6.     for n1 in range(n):
   
7.         list1[k1].append((k1 + n1 + 1) % n + 1)
   
8. for i in list1:
   
9.     print(i)
   

复制代码

结果：

1. [2, 3, 4, 5, 1]
   
2. [3, 4, 5, 1, 2]
   
3. [4, 5, 1, 2, 3]
   
4. [5, 1, 2, 3, 4

复制代码

Liu_xy

冬雪雪冬 发表于 2016-3-14 12:12
不知是否我理解有误，应该很简单的。

额。。。要求随机吧。。。这种方法虽然也符合但是不随机呀～
必须每一次输出都是随机的～

shuofxz

冬雪雪冬 发表于 2016-3-14 12:12
不知是否我理解有误，应该很简单的。

这样确实是可以生成一组满足要求的数

shuofxz

冬雪雪冬 发表于 2016-3-14 12:12
不知是否我理解有误，应该很简单的。

这样确实是可以生成一组满足要求的数

Liu_xy

shuofxz 发表于 2016-3-13 20:55
想了挺久写了如下代码
但是还是有bug，在一定情况下会出现死循环，等我这两天再想想怎么解决
或者你有没 ...

请问有想到解决办法吗？？