查找阵列中的连接组件 [英] Find connected components in array
本文介绍了查找阵列中的连接组件的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我想使用Swift使用某种特殊的模式查找算法.
I'd like to apply some kind of special pattern find algorithm using Swift.
一些解释:
我得到一个简单的一维数组，看起来可能像这样:
I'm getting a simple 1-dimensional array that could look like this:
var array = [
"0000000000000000000",
"0000001110000000000",
"0000011111000000000",
"0000001110000000000",
"0000000000000000000",
"0001100000000000000",
"0001100000000011000",
"0011100000000011000",
"0000000000000000000"
]
我想提取"1"个字符的连接区域(连接的组件).
And I'd like to extract the connected areas of "1"-characters (connected components).
看看这个:
111
11111
111
11
11 11
111 11
我想得到一个多维数组，其中包含单个组件的所有x/y位置.
I'd like to get as result a multidimensional array that includes all x/y-positions of the single components.
var result = [
[ [6,1], [7,1], [8,1], [5,2], [6,2], [7,2], [8,2], [9,2], [6,3], [7,3], [8,2] ] // positions of the first area (the biggest one on top)
[ [3,5], [4,5], [3,6], [4,6], [2,7], [3,7], [4,7] ] // area bottom left
[ [14,6], [15,6], [14,7], [15,7] ] // area bottom right (smallest area)
]
我已经为javascript编写了函数.您可以在这里找到代码:
I've coded the function for javascript. You can find the code right here:
var matrix = [
"0000000000000000000",
"0000001110000000000",
"0000011111000000000",
"0000001110000000000",
"0000000000000000000",
"0001100000000000000",
"0001100000000011000",
"0011100000000011000",
"0000000000000000000"
]
Array.prototype.extract_components_positions = function(offset) {
var array = this.map(item => item.split('')).map(str => Array.from(str, Number)),
default_value = 0,
result_object = {}
function test_connection(array, i, j) {
if (array[i] && array[i][j] === -1) {
if (!result_object[default_value]) result_object[default_value] = [];
result_object[default_value].push([j, i]);
array[i][j] = 1;
for (var k = offset; k > 0; k--) {
test_connection(array, i + k, j); // left - right
test_connection(array, i, j + k); // top - bottom
test_connection(array, i - k, j); // right - left
test_connection(array, i, j - k); // bottom - top
}
return true
}
}
array.forEach(function(a) {
a.forEach(function(b, i, bb) {
bb[i] = -b
})
});
array.forEach(function(a, i, aa) {
a.forEach(function(b, j, bb) {
test_connection(aa, i, j) && default_value++
})
})
return [result_object];
}
var result = matrix.extract_components_positions(1);
console.log(JSON.stringify(result))
但是将这个Javascript代码转换为Swift时遇到了很大的麻烦！
but I have a big problems translating this Javascript code into Swift!
func extract_components_positions(matrix: [[String]],offset: Int) {
var array = [[]] // no idea how to use map to split the array from ["0011100"],... to ["0","0","1","1",...], ...
var default_value = 0,
result_object = [[Int]()]
func testconnection(matrix: [[String]], i: Int, j: Int) -> [[Int]] {
if (Int(array[i][j] as! Int) == -1) {
array[i][j] = 1
for var k in offset...0 {
testconnection(matrix: array, i: i+k, j: j) // error: "Cannot convert value of type '[[Any]]' to expected argument type '[[String]]'"
testconnection(matrix: array, i: i, j: j+k)
testconnection(matrix: array, i: i-k, j: j)
testconnection(matrix: array, i: i, j: j-k)
}
}
}
array.forEach { (a) in
a.forEach({ (b, i, bb) in // error: "Contextual closure type '(Any) -> Void' expects 1 argument, but 3 were used in closure body"
bb[i] = -b
})
}
array.forEach { (a, i, aa) in // error: "Contextual closure type '([Any]) -> Void' expects 1 argument, but 3 were used in closure body"
a.forEach({ (b, j, bb) in
testconnection(aa, i, j) && default_value++
})
}
return result_object
}
任何帮助修复我的代码的人将不胜感激.
Any help how to fix my code would be very appreciated.
推荐答案
好像在玩扫雷！这是我的解决方案(在Swift 4.0中，Xcode 9.2).请参阅内联注释以获取解释.
Look like you are playing Minesweeper! Here's my solution (in swift 4.0, Xcode 9.2). See inline comments for explanation.
let array = [
"0000000000000000000",
"0000001110000000000",
"0000011111000000000",
"0000001110000000000",
"0000000000000000000",
"0001100000000000000",
"0001100000000011000",
"0011100000000011000",
"0000000000000000000"
]
// A structure to hold the cell's coordinate as Int array
// can become confusing very quickly
struct Cell: Equatable {
var row: Int
var column: Int
var clusterIndex: Int?
static func == (lhs: Cell, rhs: Cell) -> Bool {
return lhs.row == rhs.row && lhs.column == rhs.column
}
}
// Get all the "1" cells
var cells = array.enumerated().flatMap { arg -> [Cell] in
let (rowIndex, str) = arg
// The flatMap below will become compactMap in Swift 4.1
return str.enumerated().flatMap { colIndex, char in
if char == "1" {
return Cell(row: rowIndex, column: colIndex, clusterIndex: nil)
} else {
return nil
}
}
}
// Assign each cell a clusterIndex
for (i, currentCell) in cells.enumerated() {
// A cell may not have all four neighbors, or not all its
// neighbors are "1" cells, hence the "potential"
let potentialNeighbors = [
Cell(row: currentCell.row - 1, column: currentCell.column, clusterIndex: nil), // above
Cell(row: currentCell.row + 1, column: currentCell.column, clusterIndex: nil), // below
Cell(row: currentCell.row, column: currentCell.column - 1, clusterIndex: nil), // left
Cell(row: currentCell.row, column: currentCell.column + 1, clusterIndex: nil) // right
]
// Get the actual neighboring cells and their indexes
let neighborsAndIndexes = cells.enumerated().filter { arg in
let (_, c) = arg
return potentialNeighbors.contains(c)
}
let neighborIndexes = neighborsAndIndexes.map { $0.0 }
let neighbors = neighborsAndIndexes.map { $0.1 }
// Determine what clusterIndex we should give the current cell and its neighbors
var clusterIndex = 0
if currentCell.clusterIndex != nil {
// If the current cell already has a clusteredIndex, reuse it
clusterIndex = currentCell.clusterIndex!
} else if let neighborClusterIndex = neighbors.first(where: { $0.clusterIndex != nil })?.clusterIndex {
// If the current cell has a neighbor whose clusterIndex is not nil, use that
clusterIndex = neighborClusterIndex
} else {
// Else increment from the max existing clusterIndex
clusterIndex = (cells.map({ $0.clusterIndex ?? 0 }).max() ?? 0) + 1
}
// Assign the same clusterIndex to the current cell and its neighbors
([i] + neighborIndexes).forEach {
cells[$0].clusterIndex = clusterIndex
}
}
// Group the cells by their clusterIndex
let clusters = Dictionary(grouping: cells, by: { $0.clusterIndex! })
.sorted(by: { $0.key < $1.key })
.map { $0.value }
// Print the result
// Visualize which cell belong to which cluster and how it appears on the board
for i in 0..<array.count {
for j in 0..<array[0].count {
if let clusterIndex = cells.first(where: { $0.row == i && $0.column == j })?.clusterIndex {
print(clusterIndex, terminator: "")
} else {
print("-", terminator: "")
}
}
print() // print a newline
}
结果:
-------------------
------111----------
-----11111---------
------111----------
-------------------
---22--------------
---22---------33---
--222---------33---
-------------------
请注意，在Swift 4.1(当前为Beta)中，我们在此处使用的flatMap已重命名为compactMap.这并不是说flatMap完全消失了. flatMap具有3个版本，其中只有1个已重命名为compactMap.有关更多信息，请参见 SE-0187 .
Note that in Swift 4.1 (currently in beta), the flatMap we use here has been renamed to compactMap. This is not to say that flatMap is going away completely. flatMap has 3 versions, only 1 of them has been renamed to compactMap. For more info, see SE-0187.
这篇关于查找阵列中的连接组件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
