场景描述:
我所遇到的问题是 类似于我要抽取矩阵 并标记
大概看到的效果就是这样的函数
func findchildmatrixposition(_ childrow:Int , _ childline: Int ,_ parentmatrix:[[T]])
当然二维数组的矩阵 每个维度的个数是固定的
//从一个MN的矩阵寻找ab的抽取矩阵，其中a<M,b<N, 返回矩阵的匹配的位置和个数。
//举例推导 貌似公式是巴拉巴拉 一大堆(偷偷去搜索了下貌似靠数学手算是能搞出来的，但是程序这个 怎么会这么难呢。。。。) 我们先解决一个简单的问题 按照排列组合 我们是知道 个数的
//以 33举证
// MN 最多包含 ab 子矩阵个数 3 * 3 22 c 32 * c 32 9种
// 生成 需要标记的模板数组
[ [ _ , _ ,_ ],
[_ , _ , _ ],
[_ , _ , _]] 类似这样的模板矩阵 用于标记
// 思路 先算出 有多少种 无序排列组合 如 2*2的矩阵 对吧 先考虑一维的行无序筛选 很容易 [0,1] [0,2] [1,2] 好的 3种 列同理 [0,1] [0,2] [1,2]
//如何实现 组合 如 给一个 5 要选择 2 返回所有的组合无序列表 看现成的方案多为全排列 即 类似这样的 [[1,2],[3,4]] 12 21 是同一种组合
func getcombies(_ n:Int,_ k:Int) -> [[Int]]
// 抽取矩阵 我们将 行筛选和列筛选 继续组合 [[0,1],[0,1]] 这个看起来像什么 不就是我们要的子矩阵么[[0,1],[0,2]] [[0,1],[1,2]] 这样的组合我们可以得到 九组
// 如何标记 这里行列都列举出来了 根本不怕找不到标记对吧 类似的我们就需要写出这样的函数实现这样的效果 如 [[0,1],[0,1]]
[ [ * , * ,_ ],
[*, * , _ ],
[_ , _ , _]]
func chooseMatrix<T>(_ rowarea:[Int] , _ linearea:[Int] ,_ parentmatrix:[[T]] , _ marktemmarix:inout [[String]])
完整的实现方案
import UIKit
import Foundation
//列 1*4 位的 1 * 3 c 4 选3 4 种
//从一个M*N的矩阵中查找是否有a*b的子矩阵，其中a<M,b<N, 返回矩阵的匹配的位置和个数。
//举例推导 貌似公式是
// M*N 最多包含 a*b 子矩阵个数 3 * 3 2*2 c 32 * c 32 9种
// 思路 先算出 有多少种 无序排列组合
// 抽取矩阵
let c_placeholder = "*"
struct MatrixElem{
var ele:Int!
var pos:IndexPath!
func judgeelmentinline(_ nextelment:MatrixElem) -> Bool {
return nextelment.pos.section == self.pos.section
}
}
var testparentmatrix = [[1,3,4],[2,4,6],[3,5,6],[2,5,7]]
func judgeleaglematrix<T>(_ matrix:[[T]]) -> Bool {
if matrix.count == 0 {
return false
}
var linecount = matrix[0].count
if linecount == 0 {
return false
}
var curlinecount = linecount
for i in 1 ..< matrix.count{
curlinecount = matrix[i].count
if curlinecount != linecount {
return false
}
linecount = curlinecount
}
return curlinecount == linecount
}
func displaymatrix<T>(_ matrix:[[T]] ){
if !judgeleaglematrix(matrix){
print("构造M*N矩阵不合法")
return
}
for i in 0 ..< matrix.count {
for j in 0 ..< matrix[i].count{
print("\(matrix[i][j])", terminator: "")
if i <= matrix.count - 1 && j != matrix[i].count - 1 {
print(",", terminator: "")
}
else {
print()
}
}
}
}
extension Array where Element: Equatable {
func contains(array: [Element]) -> Bool {
for item in array {
if !self.contains(item) { return false }
}
return true
}
}
//displaymatrix(testparentmatrix)
//2*2
func findchildmatrixposition(_ childrow:Int , _ childline: Int ,_ parentmatrix:[[Int]]) {
if childrow <= 0 || childrow > parentmatrix.count || childline <= 0 || childline > parentmatrix[0].count {
print("参数不合法，或者不存在 该子矩阵")
return
}
displaymatrix(parentmatrix)
let parentrow = parentmatrix.count
let parentline = parentmatrix[0].count
let subcount = (fac(parentline)/(fac(parentline-childline)*fac(childline))) * (fac(parentrow)/(fac(parentrow-childrow)*fac(childrow)))
print("M*N \(parentrow):\(parentline)包含子矩阵a*b \(childrow):\(childline)的个数是 :\(subcount)个")
//子模板标记 数组
let rowchoose = getcombies(parentrow, childrow)
let linechoose = getcombies(parentline, childline)
var allmatrix = [[[String]]]()
for _ in 0..<subcount{
var displayposition = [[String]]()
for _ in 0 ..< parentrow {
var itempic = [String]()
for _ in 0 ..< parentline{
itempic.append(c_placeholder)
}
displayposition.append(itempic)
}
allmatrix.append(displayposition)
}
print(subcount)
//下面可以不写了 只要返回 行列的筛选 就可以标记了
print("子矩阵如下:")
print("行筛选:\(rowchoose)","列筛选\(linechoose)")
var allposition = [[[Int]]]()
for rowitem in rowchoose {
var curposiotion = [[Int]]()
curposiotion.append(rowitem)
for lineitem in linechoose {
curposiotion.append(lineitem)
}
allposition.append(curposiotion)
}
var combiesPositionValue = [[[Int]]]()
print("行列抽取位置索引如下------------")
for i in 0 ..< allposition.count {
//表示行列的组合
let indexmatrix = allposition[i]
let rowindex = indexmatrix.first!
for j in 1..<indexmatrix.count {
var positoncobies = [[Int]]()
positoncobies.append(rowindex)
positoncobies.append(indexmatrix[j])
print(positoncobies)
chooseMatrix(rowindex, indexmatrix[j], parentmatrix,&allmatrix[i],c_placeholder)
displaymatrix(allmatrix[i])
combiesPositionValue.append(positoncobies)
}
print()
}
}
func comparewithstr<T>(_ matrix:[[T]] ) -> String {
var res = ""
for i in 0..<matrix.count {
for j in 0..<matrix[i].count {
let t = "\(matrix[i][j])"
if t != c_placeholder {
res.append("\(matrix[i][j])")
}
}
}
return res
}
func slicematrix(_ abmatrix:[[Int]] , _ markmatrix:[[String]] ) -> Bool{
let tempslice1 = comparewithstr(abmatrix)
let tempslice2 = comparewithstr(markmatrix)
return tempslice1 == tempslice2
}
// 传的 选取的行 数组 列数组
func chooseMatrix<T>(_ rowarea:[Int] , _ linearea:[Int] ,_ parentmatrix:[[T]] , _ marktemmarix:inout [[String]] ,_ placeholder: String) {
var res:Bool = false
for i in 0..<parentmatrix.count {
for j in 0..<parentmatrix[i].count {
res = rowarea.contains(i) && linearea.contains(j)
if res {
let indexrow = rowarea.firstIndex(of: i)
let indexline = linearea.firstIndex(of: j)
marktemmarix[i][j] = "\( parentmatrix[rowarea[indexrow!]][linearea[indexline!]])"
}
else{
marktemmarix[i][j] = placeholder
}
}
}
}
func fac(_ value:Int) -> Int{
if value == 0 {return 1}
return value * fac(value-1)
}
func combine(_ lists:inout [[Int]], _ list:inout [Int] ,_ start:Int,_ n:Int,_ k: Int) {
if k == 0 {
lists.append(list)
return
}
for i in start ..< n {
list.append(i)
combine(&lists, &list, i+1, n, k-1)
list.remove(at: list.count - 1)
}
}
func getcombies(_ n:Int,_ k:Int) -> [[Int]]{
var result = [[Int]]()
var newvalue = [Int]()
combine(&result, &newvalue, 0, n, k)
return result
}
func findJudgematrix(_ abmatrix:[[Int]] , _ parentmatrix:[[Int]]) {
if !judgeleaglematrix(abmatrix) {
print("子矩阵 不合法 ")
return
}
displaymatrix(parentmatrix)
print()
print("查找矩阵")
displaymatrix(abmatrix)
let firstindex = abmatrix[0][0]
let positionindex = markpostionElment(firstindex, parentmatrix)
if positionindex.count == 0 {
print("无此子矩阵")
return
}
let parentrow = parentmatrix.count
let parentline = parentmatrix[0].count
let childrow = abmatrix.count
let childline = abmatrix[0].count
let subcount = (fac(parentline)/(fac(parentline-childline)*fac(childline))) * (fac(parentrow)/(fac(parentrow-childrow)*fac(childrow)))
// print("M*N \(parentrow):\(parentline)包含子矩阵a*b \(childrow):\(childline)的个数是 :\(subcount)个")
//子模板标记 数组
let rowchoose = getcombies(parentrow, childrow)
let linechoose = getcombies(parentline, childline)
var allmatrix = [[[String]]]()
for _ in 0..<subcount{
var displayposition = [[String]]()
for _ in 0 ..< parentrow {
var itempic = [String]()
for _ in 0 ..< parentline{
itempic.append(c_placeholder)
}
displayposition.append(itempic)
}
allmatrix.append(displayposition)
}
// print(subcount)
// //下面可以不写了 只要返回 行列的筛选 就可以标记了
// print("子矩阵如下:")
// print("行筛选:\(rowchoose)","列筛选\(linechoose)")
var allposition = [[[Int]]]()
for rowitem in rowchoose {
var curposiotion = [[Int]]()
curposiotion.append(rowitem)
for lineitem in linechoose {
curposiotion.append(lineitem)
}
allposition.append(curposiotion)
}
var combiesPositionValue = [[[Int]]]()
var result = 0
// print("行列抽取位置索引如下------------")
for i in 0 ..< allposition.count {
//表示行列的组合
let indexmatrix = allposition[i]
let rowindex = indexmatrix.first!
for j in 1..<indexmatrix.count {
var positoncobies = [[Int]]()
positoncobies.append(rowindex)
positoncobies.append(indexmatrix[j])
// print(positoncobies)
chooseMatrix(rowindex, indexmatrix[j], parentmatrix,&allmatrix[i],c_placeholder)
if slicematrix(abmatrix, allmatrix[i]) {
result = result + 1
combiesPositionValue.append(positoncobies)
print("在原矩阵的位置标记如下:")
displaymatrix(allmatrix[i])
print("行筛选:\(positoncobies.first!)")
print("列筛选:\(positoncobies.last!)")
}
}
}
if result == 0 {
print("没有相关子矩阵")
}else{
print("这样的矩阵存在 \(result)个")
}
}
func flatmap(_ abmatrix:[[Int]] ,_ parentmarkmatrix:[[Int]]) -> Bool {
return parentmarkmatrix.contains(array: abmatrix)
}
//先查找行
func findnextvaluesbyrow(_ index:IndexPath , _ subrows:[Int] ,_ subline:Int,_ parentmatrix:[[Int]] ) ->Bool{
var rowcount = [Int]()
//每一行的查找个数
for ele in subrows {
var elementexusit = 0
for j in 0..<parentmatrix[index.row].count{
if ele == parentmatrix[index.row][j] {
elementexusit = elementexusit + 1
}
}
rowcount.append(elementexusit)
}
return rowcount.count == subrows.count
}
func markpostionElment(_ elment:Int,_ parentmatrix:[[Int]]) -> [IndexPath]{
var indexpathvalue = [IndexPath]()
for i in 0..<parentmatrix.count{
for j in 0..<parentmatrix[i].count{
if elment == parentmatrix[i][j]{
let index = IndexPath.init(row: j, section: i)
indexpathvalue.append(index)
}
}
}
return indexpathvalue
}
//findchildmatrixposition(4, 3, testparentmatrix)
var matrixtest1 = [[2],[3],[5],[2],[6]]
var matrixtest2 = [[2,3,5,2,6]]
var matrixtest3 = [[2,3,1],[5,7,3],[9,6,1]]
var matrixtest4 = [[2,3,5,8],[5,2,4,7],[6,1,3,9],[3,5,8,7],[11,9,8,4],[4,9,8,6]]
//findchildmatrixposition(2, 3, matrixtest3)
findJudgematrix([[3,5],[2,4]], matrixtest4)
