¿Establecer operaciones (unión, intersección) en la matriz Swift?

100

¿Hay alguna llamada de biblioteca estándar que pueda usar para realizar operaciones de conjunto en dos matrices o implementar dicha lógica yo mismo (idealmente, de la manera más funcional y eficiente posible)?

functional-programming swift set-operations devios1
fuente
Se puede implementar un conjunto encima de un diccionario si desea hacerlo usted mismo.
CodaFi
@CodaFi ¿Te refieres a usar las claves para garantizar la singularidad?
devios1
¿Podrías usar `Dictionary <String, Void>?
David Berry

Respuestas:

184

Sí, Swift tiene la Setclase.

let array1 = ["a", "b", "c"]
let array2 = ["a", "b", "d"]

let set1:Set<String> = Set(array1)
let set2:Set<String> = Set(array2)

Swift 3.0+ puede realizar operaciones en conjuntos como:

firstSet.union(secondSet)// Union of two sets
firstSet.intersection(secondSet)// Intersection of two sets
firstSet.symmetricDifference(secondSet)// exclusiveOr

Swift 2.0 puede calcular sobre argumentos de matriz:

set1.union(array2)       // {"a", "b", "c", "d"} 
set1.intersect(array2)   // {"a", "b"}
set1.subtract(array2)    // {"c"}
set1.exclusiveOr(array2) // {"c", "d"}

Swift 1.2+ puede calcular en conjuntos:

set1.union(set2)        // {"a", "b", "c", "d"}
set1.intersect(set2)    // {"a", "b"}
set1.subtract(set2)     // {"c"}
set1.exclusiveOr(set2)  // {"c", "d"}

Si está utilizando estructuras personalizadas, debe implementar Hashable.

Gracias a Michael Stern en los comentarios por la actualización de Swift 2.0.

Gracias a Amjad Husseini en los comentarios por la información de Hashable.

joelparkerhenderson
fuente
8
Tenga en cuenta que, a partir de Swift 2.0 al menos, puede pasar una matriz como argumento a estas funciones. Por tanto, set1.union(array2)y set1.exclusiveOr(array2)ambos son legítimos, además de los formularios mostrados anteriormente.
Michael Stern
¿Qué pasa si desea intersecar 5 matrices? ¿O 6? ¿Qué pasa si se desconoce el número de matrices?
Nathan McKaskle
2
@Nathan Depende de la operación establecida. Por ejemplo, la unión de conjuntos y la intersección de conjuntos son conmutativas y asociativas, por lo que puede procesar muchos conjuntos mediante iteración o encadenamiento. O puede crear métodos personalizados que usen var args, como Set union_all (...) e intersect_all (...).
joelparkerhenderson
¿Qué pasa si sus matrices contienen valores duplicados, por ejemplo, para determinar si $ 0 es un anagrama de $ 1 donde los caracteres de entrada podrían tener letras duplicadas?
Dave Kliman
1
Si está utilizando estructuras personalizados que tiene que conformar Hashable, lo que podría ser molesto si usted tiene una estructura complicada
Amjad Husseini
0

No hay llamadas de biblioteca estándar, pero es posible que desee consultar la biblioteca ExSwift . Incluye un montón de funciones nuevas en Arrays que incluyen diferencia, intersección y unión.

Connor
fuente
1
Una nota de advertencia: había estado usando ExSwift sin problemas para Swift 1.x, pero parece bastante roto para Swift 2.x, y hasta el momento de escribir este artículo no se ha actualizado en unos meses. Hay un montón de horquillas que pueden recibir más atención.
Robin Macharg
0

El método más eficiente que conozco es el uso de números godel. Google para codificación godel.

La idea es así. Suponga que tiene N números posibles y necesita hacer conjuntos de ellos. Por ejemplo, N = 100.000 y desea crear conjuntos como {1,2,3}, {5, 88, 19000}, etc.

La idea es mantener la lista de N números primos en la memoria y para un conjunto dado {a, b, c, ...} se codifica como

 prime[a]*prime[b]*prime[c]*...

Así que codificas un conjunto como BigNumber. Las operaciones con BigNumbers, a pesar de que son más lentas que las operaciones con Integers, siguen siendo muy rápidas.

Para unir 2 conjuntos A, B, toma

  UNITE(A, B) = lcm(a, b)

mínimo común múltiplo de A y B, ya que A y B son conjuntos y ambos números.

Para hacer la intersección que tomas

 INTERSECT(A, B) = gcd (a, b)

máximo común divisor.

y así.

Esta codificación se llama godelización, puedes buscar más en Google, todo el lenguaje de la aritmética escrito usando la lógica de Frege se puede codificar usando números de esta manera.

Para conseguir la operación is-member? Es muy simple --

ISMEMBER(x, S) = remainder(s,x)==0

Conseguir el cardenal es un poco más complicado.

CARDINAL(S) = # of prime factors in s

descompone el número S que representa el conjunto en producto de factores primos y suma sus exponentes. En caso de que el conjunto no permita duplicados, todos los exponentes serán 1.

alinsoar
fuente