Удаление подмножеств в массиве наборов

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

Ключ гарантирующего наборы исходных сортируются в порядке убывания размера , Таким образом, все надмножества предшествуют их подмножествам.

Вот общая функция для этого. Вы можете адаптировать его взять любую последовательность последовательности hashable и преобразовывать их в массив множеств на пути в:

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.

EDIT: вот полностью общая версия:

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

Если массив не содержит дублированные значения 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({$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]]