Definir operações (união, interseção) na matriz Swift?

100

Há alguma chamada de biblioteca padrão que eu possa usar para executar operações de conjunto em dois arrays ou implementar essa lógica sozinho (de preferência da maneira mais funcional e eficiente possível)?

functional-programming swift set-operations devios1
fonte
Um conjunto pode ser implementado em cima de um dicionário se você quiser fazer isso sozinho.
CodaFi
@CodaFi Você quer dizer usando as teclas para garantir a exclusividade?
devios1
Você poderia apenas usar `Dictionary <String, Void>?
David Berry

Respostas:

184

Sim, Swift tem a Setclasse.

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

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

O Swift 3.0+ pode fazer operações em conjuntos como:

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

O Swift 2.0 pode calcular em argumentos de matriz:

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

O Swift 1.2+ pode calcular em conjuntos:

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

Se você estiver usando structs personalizados, é necessário implementar Hashable.

Agradecimentos a Michael Stern nos comentários sobre a atualização do Swift 2.0.

Agradecimentos a Amjad Husseini nos comentários pela informação Hashable.

joelparkerhenderson
fonte
8
Observe que, pelo menos a partir do Swift 2.0, você pode passar um array como argumento para essas funções. Assim, set1.union(array2)e set1.exclusiveOr(array2)são ambos legítimos, além dos formulários acima.
Michael Stern,
E se você quiser cruzar 5 matrizes? Ou 6? E se o número de matrizes for desconhecido?
Nathan McKaskle
2
@Nathan Depende da operação definida. Por exemplo, conjunto de união e interseção de conjunto são comutativos e associativos, portanto, você pode processar muitos conjuntos usando iteração ou encadeamento. Ou você pode criar métodos personalizados que usam var args, como Set union_all (...) e intersect_all (...).
joelparkerhenderson
E se seus arrays contiverem valores duplicados, por exemplo, para determinar se $ 0 é um anagrama de $ 1 onde os caracteres de entrada podem ter letras duplicadas?
Dave Kliman
1
Se estiver usando structs personalizados, você deve conformar o Hashable, o que pode ser irritante se você tiver um struct complicado
Amjad Husseini
0

Não existem chamadas de biblioteca padrão, mas você pode querer dar uma olhada na biblioteca ExSwift . Inclui um monte de novas funções em Arrays, incluindo diferença, interseção e união.

Connor
fonte
1
Uma nota de advertência: eu estava usando o ExSwift sem problemas para o Swift 1.x, mas parece bastante danificado para o Swift 2.x, e até o momento em que este livro foi escrito não foi atualizado em alguns meses. Existem muitos garfos que podem receber mais atenção.
Robin Macharg
0

O método mais eficiente que conheço é o uso de números Godel. Google para codificação Godel.

A ideia é assim. Suponha que você tenha N números possíveis e precise fazer conjuntos deles. Por exemplo, N = 100.000 e deseja fazer conjuntos como {1,2,3}, {5, 88, 19000} etc.

A ideia é manter a lista de N números primos na memória e para um determinado conjunto {a, b, c, ...} você a codifica como

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

Portanto, você codifica um conjunto como um BigNumber. As operações com BigNumbers, apesar de serem mais lentas que as operações com Inteiros, ainda são muito rápidas.

Para unir 2 conjuntos A, B, você toma

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

menor-comum-múltiplo de A e B como A e B são conjuntos e ambos números.

Para fazer o cruzamento, você pega

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

maior divisor comum.

e assim por diante.

Essa codificação é chamada de godelização, você pode pesquisar mais no Google, toda a linguagem da aritmética escrita usando a lógica de Frege pode ser codificada usando números dessa forma.

Para obter a operação is-member? É muito simples --

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

Para obter o cardeal é um pouco mais complicado -

CARDINAL(S) = # of prime factors in s

você decompõe o número S que representa o conjunto em produto de fatores primos e adiciona seus expoentes. Caso o conjunto não permita duplicatas, você terá todos os expoentes 1.

alinsoar
fonte