删除集合中的子集

Question

是否有一种有效的方法来从集合中删除子集

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]] 

Answer 1

的关键是保证源集大小的降序排序。这样所有的超集先于它们的子集。

这是一个通用的功能。你能适应它采取任何可哈希的序列的序列，并将它们转换成的套阵列上的方式：

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]] 

Answer 2

你可以这样做：

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] 

Answer 3

就像任何其他（非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); 

Answer 4

如果阵列中不包含重复的国际价值，你可以转换到设置为使用来自雨燕的一些特点：

（看看执行集合运算） https://developer.apple.com/library/prerelease/ios/documentation/Swift/Conceptual/Swift_Programming_Language/CollectionTypes.html

这里是我的代码来获得另一个不包含子集的数组。这种方法没有优化，但它的工作原理。

//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) 
    } 
} 

Answer 5

这是我能想到的最有效的方法：

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]]