282842712474 发表于 2014-11-5 17:16:17

n个自然数

两道小问题：

1、向量$(a_1,a_2,...,a_n)$，其中$a_n \in \{1,2,3,...,n\}$，如何判断$\{a_i\}$是否遍历1到n？（也就是说1到n在这个向量中都只出现一次）

2、A是一个$n\times n$矩阵，要求每行、每列都包含1,2,3,...,n这n个数字。如何高效地输出所有可能的A？

wayne 发表于 2014-11-5 17:29:52

1) 先Union，再求Length
2) 似曾相识，好像是陈题

wayne 发表于 2014-11-5 18:12:00

第二题 让我想到了数独。Sudoku ， 但比数独约束弱多了，而数独本身就有很多组合（9*9有5472730538种不同构的解），所以第二题的不同构的解估计会更多。
http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html

282842712474 发表于 2014-11-5 22:11:12

顺便加上第三问题：如何判断第二个问题中这样的矩阵是否同构？

wayne 发表于 2014-11-8 12:23:53

282842712474 发表于 2014-11-5 22:11
顺便加上第三问题：如何判断第二个问题中这样的矩阵是否同构？

根据4楼的提示，不同构的解，搜到http://oeis.org/A000315
1                1
2                1
3                1
4                4
5                56
6                9408
7                16942080
8                535281401856
9                377597570964258816
10                7580721483160132811489280
11                5363937773277371298119673540771840

wayne 发表于 2014-11-8 12:40:59

math_humanbeing 发表于 2014-11-5 20:22
第2题，拉丁方问题，可能和拟群有关。
很短很精悍。
拟群？
我连 群 都不会~

====
搜了下拟群的wikipedia 解释： 一个有限拟群的乘法构成的乘法表是一个拉丁方
页: [1]
查看完整版本: n个自然数