Définir les opérations (union, intersection) sur le tableau Swift?

100

Existe-t-il des appels de bibliothèque standard que je peux utiliser pour effectuer des opérations d'ensemble sur deux tableaux ou implémenter moi-même une telle logique (idéalement aussi fonctionnellement et aussi efficacement que possible)?

functional-programming swift set-operations devios1
la source
Un ensemble peut être implémenté au-dessus d'un dictionnaire si vous souhaitez le faire vous-même.
CodaFi
@CodaFi Voulez-vous dire en utilisant les touches pour assurer l'unicité?
devios1
Pourriez-vous simplement utiliser `Dictionary <String, Void>?
David Berry

Réponses:

184

Oui, Swift a la Setclasse.

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+ peut effectuer des opérations sur des ensembles comme:

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

Swift 2.0 peut calculer sur les arguments de tableau:

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

Swift 1.2+ peut calculer sur des ensembles:

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

Si vous utilisez des structures personnalisées, vous devez implémenter Hashable.

Merci à Michael Stern dans les commentaires pour la mise à jour Swift 2.0.

Merci à Amjad Husseini dans les commentaires pour l'info Hashable.

joelparkerhenderson
la source
8
Notez qu'à partir de Swift 2.0 au moins, vous pouvez passer un tableau comme argument à ces fonctions. Ainsi, set1.union(array2)et set1.exclusiveOr(array2)sont tous deux légitimes, en plus des formulaires présentés ci-dessus.
Michael Stern
Et si vous souhaitez croiser 5 tableaux? Ou 6? Que faire si le nombre de tableaux est inconnu?
Nathan McKaskle
2
@Nathan Dépend de l'opération définie. Par exemple, set union et set intersection sont commutatifs et associatifs, vous pouvez donc traiter de nombreux ensembles en utilisant l'itération ou le chaînage. Ou vous pouvez créer des méthodes personnalisées qui utilisent var args, telles que Set union_all (...) et intersect_all (...).
joelparkerhenderson
Et si vos tableaux contiennent des valeurs en double, par exemple pour déterminer si $ 0 est un anagramme de $ 1 où les caractères d'entrée pourraient avoir des lettres en double?
Dave Kliman
1
Si vous utilisez des structures personnalisées, vous devez vous conformer à Hashable, ce qui peut être ennuyeux si vous avez une structure compliquée
Amjad Husseini
0

Il n'y a pas d'appels de bibliothèque standard, mais vous voudrez peut-être consulter la bibliothèque ExSwift . Il comprend un tas de nouvelles fonctions sur les tableaux, y compris la différence, l'intersection et l'union.

Connor
la source
1
Une mise en garde: j'avais utilisé ExSwift sans problème pour Swift 1.x mais cela semble assez cassé pour Swift 2.x, et à ce jour, il n'a pas été mis à jour depuis quelques mois. Il y a une tonne de fourches qui peuvent recevoir plus d'attention.
Robin Macharg
0

La méthode la plus efficace que je connaisse est d'utiliser des nombres de godel. Google pour l'encodage godel.

L'idée est ainsi. Supposons que vous ayez N nombres possibles et que vous deviez en faire des ensembles. Par exemple, N = 100 000 et souhaitez créer des ensembles tels que {1,2,3}, {5, 88, 19000}, etc.

L'idée est de garder la liste des N nombres premiers en mémoire et pour un ensemble donné {a, b, c, ...} vous l'encodez comme

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

Vous encodez donc un ensemble en tant que BigNumber. Les opérations avec BigNumbers, malgré le fait qu'elles soient plus lentes que les opérations avec des nombres entiers, sont toujours très rapides.

Pour réunir 2 ensembles A, B, vous prenez

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

le plus petit commun multiple de A et B car A et B sont des ensembles et les deux nombres.

Pour faire l'intersection que vous prenez

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

plus grand diviseur commun.

etc.

Cet encodage s'appelle godelization, vous pouvez google pour plus, tout le langage d'arithmétique écrit en utilisant la logique de Frege peut être encodé en utilisant des nombres de cette manière.

Pour obtenir l'opération est-membre? c'est très simple --

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

Pour obtenir le cardinal, c'est un peu plus compliqué -

CARDINAL(S) = # of prime factors in s

vous décomposez le nombre S représentant l'ensemble en produit des facteurs premiers et ajoutez leurs exposants. Dans le cas où l'ensemble n'autorise pas les doublons, vous aurez tous les exposants 1.

Alinsoar
la source