是否有一种有效的方法来从集合中删除子集删除集合中的子集
E.g.数组的数组
[[2, 3, 4, 7, 8, 9, 10], [1, 5, 6], [3, 7, 10], [4, 8, 9], [5, 6], [7, 10], [8, 9], [6], [9]]
输出数组
[[2, 3, 4, 7, 8, 9, 10], [1, 5, 6]]
是否有一种有效的方法来从集合中删除子集删除集合中的子集
E.g.数组的数组
[[2, 3, 4, 7, 8, 9, 10], [1, 5, 6], [3, 7, 10], [4, 8, 9], [5, 6], [7, 10], [8, 9], [6], [9]]
输出数组
[[2, 3, 4, 7, 8, 9, 10], [1, 5, 6]]
的关键是保证源集大小的降序排序。这样所有的超集先于它们的子集。
这是一个通用的功能。你能适应它采取任何可哈希的序列的序列,并将它们转换成的套阵列上的方式:
func removeSubsets<T: Hashable>(source: [Set<T>]) -> [Set<T>] {
let sets = source.sorted { $0.count > $1.count }
var supersets: [Set<T>] = []
for set in sets {
if !contains(supersets, { set.isSubsetOf($0) }) {
supersets.append(set)
}
}
return supersets
}
removeSubsets([[2, 3, 4, 7, 8, 9, 10], [1, 5, 6], [3, 7, 10], [4, 8, 9], [5, 6], [7, 10], [8, 9], [6], [9]])
// returns [{10, 2, 9, 4, 7, 3, 8}, {5, 6, 1}]
它仍然立方遗憾的是,因为contains
是线性的,因此是isSubsetOf
。
编辑:这里是完全通用的版本:
func removeSubsets
<S0: SequenceType, S1: SequenceType
where S0.Generator.Element == S1,
S1.Generator.Element: Hashable>
(source: S0) -> [Set<S1.Generator.Element>]
{
let sets = map(source) { Set($0) }.sorted { $0.count > $1.count }
var supersets: [Set<S1.Generator.Element>] = []
for set in sets {
if !contains(supersets, { set.isSubsetOf($0) }) {
supersets.append(set)
}
}
return supersets
}
let a: [[Int]] = [
[2, 3, 4, 7, 8, 9, 10],
[1, 5, 6], [3, 7, 10],
[4, 8, 9], [5, 6],
[7, 10], [8, 9],
[6], [9]]
removeSubsets(a) // returns [{10, 2, 9, 4, 7, 3, 8}, {5, 6, 1}]
EDIT2:如果你想要的结果是原始数组的数组(因为它们转化为套失去他们的顺序),你可以做以下变化,这需要更多的空间,但也略有更有效,因为它只是转换超集来套,不子集:
func removeSubsets<T: Hashable>(source: [[T]]) -> [[T]] {
// note, this is quite efficient since arrays are copy-on-write,
// so it is only really creating a new array of pointers
let sets = source.sorted { $0.count > $1.count }
var supersets: [Set<T>] = []
var result: [[T]] = []
for set in sets {
if !contains(supersets, { $0.isSupersetOf(set) }) {
supersets.append(Set(set))
result.append(set)
}
}
return result
}
removeSubsets([[2, 3, 4, 7, 8, 9, 10], [1, 5, 6], [3, 7, 10], [4, 8, 9], [5, 6], [7, 10], [8, 9], [6], [9]])
// returns [[2, 3, 4, 7, 8, 9, 10], [1, 5, 6]]
EDIT3:如果你想保留的集(只是子集的原始顺序删除),您可以用数字标记它们在排序之前的路上,然后使用它重新排序并将其从结果中剥离:
func removeSubsets<T: Hashable>(source: [[T]]) -> [[T]] {
let sets = sorted(enumerate(source)) { $0.1.count > $1.1.count }
var supersets: [Set<T>] = []
var result: [(Int,[T])] = []
for (n,set) in sets {
if !contains(supersets, { $0.isSupersetOf(set) }) {
supersets.append(Set(set))
result.append(n,set)
}
}
return result.sorted { $0.0 < $1.0 }.map { $1 }
}
// note, input not sorted in order of length
removeSubsets([[1, 5, 6], [2, 3, 4, 7, 8, 9, 10], [3, 7, 10], [4, 8, 9], [5, 6], [7, 10], [8, 9], [6], [9]])
// returns [[1, 5, 6], [2, 3, 4, 7, 8, 9, 10]]
你可以这样做:
let arrayOfArray = [[2, 3, 4, 7, 8, 9, 10], [1, 5, 6], [3, 7, 10], [4, 8, 9], [5, 6], [7, 10], [8, 9], [6], [9]]
let output = arrayOfArray[0...1]
这是不正确的。在这个例子中,可能看到索引0和1是需要的,但我想动态地移除子集。 – jarryd
就像任何其他(非2D /集)数组,你可以使用像这样的阵列扩展...
extension Array
{
func slice(indices:Int...) -> Array
{
var s = indices[0];
var e = self.count - 1;
if (indices.count > 1)
{
e = indices[1];
}
if (e < 0)
{
e += self.count;
}
if (s < 0)
{
s += self.count;
}
let count = (s < e ? e - s : s - e) + 1;
let inc = s < e ? 1 : -1;
var result = Array();
var idx = s;
for i in 0 ..< count
{
result.append(self[idx]);
idx += inc;
}
return result;
}
}
用法:
let a = [[2, 3, 4, 7, 8, 9, 10], [1, 5, 6], [3, 7, 10], [4, 8, 9], [5, 6], [7, 10], [8, 9], [6], [9]];
let b = a.slice(0, 1);
let c = a.slice(3);
谢谢,但这是矫枉过正。我追求一套最佳的方法,而不是迭代每个集合,并在每个集合上调用isSubsetOf。我不想将它们作为数组处理,效率会降低。我应该有一套开始,而不是来回转换,但多数民众赞成在另一个问题 – jarryd
是不是你的'slice()'方法或多或少'a [from ... to]'已经做了什么? –
没错,基本上是一样的。唯一不同的是它允许负值环绕和/或返回颠倒的数组。 – BadmintonCat
如果阵列中不包含重复的国际价值,你可以转换到设置为使用来自雨燕的一些特点:
这里是我的代码来获得另一个不包含子集的数组。这种方法没有优化,但它的工作原理。
//let arrayOfArray = [[2, 3, 4, 7, 8, 9, 10], [1, 5, 6], [3, 7, 10], [4, 8, 9], [5, 6], [7, 10], [8, 9], [6], [9]]
//use set instead
var setArray : [Set<Int>] = [[2, 3, 4, 7, 8, 9, 10], [1, 5, 6], [3, 7, 10], [4, 8, 9], [5, 6], [7, 10], [8, 9], [6], [9]]
setArray.sort({$0.count > $1.count}) //sort to have ordered array (biggest set at first)
var result = [Set<Int>]() //you will get your result in this variable.
for _aSet in setArray {
var isSubSet = false
for _exitSet in result {
if _aSet.isSubsetOf(_exitSet) {
isSubSet = true
break;
}
}
if (!isSubSet) {
result.append(_aSet)
}
}
这是我能想到的最有效的方法:
let nArrays = [[2, 3, 4, 7, 8, 9, 10], [1, 5, 6], [3, 7, 10], [4, 8, 9], [5, 6], [7, 10], [8, 9], [6], [9]]
nArrays
.reduce([Set<Int>]()) {
accu, el in let setEl = Set(el)
return contains(accu) {setEl.isSubsetOf($0)} ? accu : accu + [setEl]
}
//[{10, 2, 9, 4, 7, 3, 8}, {5, 6, 1}]
而不是检查,如果每个阵列是每隔阵列的一个子集,你只需要检查,如果他们的一个子集已经检查过数组。当然,返回集合的数组,而不是数组的数组,但你可以映射()在它把它转换回来:
let nArrays = [[2, 3, 4, 7, 8, 9, 10], [1, 5, 6], [3, 7, 10], [4, 8, 9], [5, 6], [7, 10], [8, 9], [6], [9]]
nArrays
.reduce([Set<Int>]()) {
accu, el in let setEl = Set(el)
return contains(accu) {setEl.isSubsetOf($0)} ? accu : accu + [setEl]
}
.map{Array($0)}
//[[10, 2, 9, 4, 7, 3, 8], [5, 6, 1]]
是那些数组的集合或数组的数组?你想删除什么? –
数组的阵列,但我想删除所有的子集。例如。 [3,7,10]是[2,3,4,7,8,910]等的子集,只剩下两个超集。我想从除了最小集合开始的每个项目上运行isSubsetOf之外的其他方法。 – jarryd
如果您有关于如何删除它们的原则,可能...根据提供的信息,如果删除索引大于'1'的原始元素中的每个元素,都可以获得输出数组。 – holex