删除集合数组中的子集

Question

有没有一种从集合数组中删除子集的有效方法

例如数组的数组

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

你可以这样做：

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 2

就像任何其他 (non-2D/set) 数组一样，您可以使用这样的数组扩展...

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 3

如果您的数组不包含重复的 int 值，您可以转换为 Set 以使用 Swift:

中的某些功能

（查看执行集合操作） 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({[=10=].count > .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 4

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

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([=10=])} ? accu : accu + [setEl]
  }


//[{10, 2, 9, 4, 7, 3, 8}, {5, 6, 1}]

您无需检查每个数组是否是所有其他数组的子集，而只需检查它们是否是已检查数组的子集。当然，returns 是一个 Set 数组，而不是一个数组数组，但是你可以在它上面使用 map() 将它转换回来：

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([=11=])} ? accu : accu + [setEl]
  }
  .map{Array([=11=])}


//[[10, 2, 9, 4, 7, 3, 8], [5, 6, 1]]

Answer 5

关键是保证源集按大小降序排列。这样所有的超集都在它们的子集之前。

这是一个通用函数。您可以调整它以采用任何类型的可哈希序列序列，并将它们转换为一组数组：

func removeSubsets<T: Hashable>(source: [Set<T>]) -> [Set<T>] {    
    let sets = source.sorted { [=10=].count > .count }
    var supersets: [Set<T>] = []
    for set in sets {
        if !contains(supersets, { set.isSubsetOf([=10=]) }) {
            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([=11=]) }.sorted { [=11=].count > .count }
    var supersets: [Set<S1.Generator.Element>] = []
    for set in sets {
        if !contains(supersets, { set.isSubsetOf([=11=]) }) {
            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：如果您希望结果是原始数组的数组（因为将它们转换为集合会丢失它们的顺序），您可以进行以下更改，这需要更多 space 但也略微效率更高，因为它只将超集转换为集合，而不是子集：

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 { [=12=].count > .count }
    var supersets: [Set<T>] = []
    var result: [[T]] = []

    for set in sets {
        if !contains(supersets, { [=12=].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)) { [=13=].1.count > .1.count }
    var supersets: [Set<T>] = []
    var result: [(Int,[T])] = []

    for (n,set) in sets {
        if !contains(supersets, { [=13=].isSupersetOf(set) }) {
            supersets.append(Set(set))
            result.append(n,set)
        }
    }

    return result.sorted { [=13=].0 < .0 }.map {  }
}


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

删除集合数组中的子集

Removing subsets in array of Sets

arrays

set

swift