Garantir qu'une seule formule puisse s'appliquer à 4 éléments aléatoires

Question

Je dispose d'une liste de formules pour combiner des éléments :

A + B + C = X
D + E + F = Y
G + H + I = Z

Je veux m'assurer qu'à partir de 4 éléments pris au hasard, il n'y aura jamais plus d'une formule applicable. Par exemple, les formules ci-dessous ne devraient pas être autorisées car si j'obtiens les éléments A, B, C et D, les deux sont applicables :

A + B + C = X
B + C + D = Y

Chaque formule sera composée de 3 éléments sur la LHS et c'est sur la LHS que je veux appliquer la règle. Les éléments peuvent être triés, si cela peut aider.

---

Un problème alternatif et équivalent :

J'ai une liste d'un tableau de 3 éléments : List<Element[3]> Comment puis-je m'assurer qu'aucun élément n'apparaît dans plus d'un tableau ?

---

Quel serait un moyen raisonnablement efficace (vitesse d'exécution) d'effectuer cette opération pour un grand nombre d'éléments et un grand nombre de formules (au-delà de la force brute) ?

Answer 1

Il s'agit essentiellement d'un problème d'exclusion : à partir de votre exemple de données,

• la première formule fonctionne sur l'ensemble (A,B,C,X) ou peut-être (A,B,C) si X est une constante
• la deuxième formule fonctionne sur (D,E,F,Y) ou (D,E,F)
• etc.

et vous voulez vous assurer que toute nouvelle entrée dans la liste

• N'opère pas sur un ensemble déjà dans la liste (comme (A,B,C[,X]))
• N'opère pas sur un sous-ensemble d'une entrée déjà dans la liste (comme (A,B)), car dans ce cas le tuple d'entrée (A,B,C[,X]) fonctionnerait sur une formule déjà existante ET sur la nouvelle.

En fonction de la taille des tuples, la création d'une liste exhaustive de sous-ensembles peut être coûteuse ou non.

Cela devrait fonctionner pour les petits ensembles (liste de sous-ensembles bon marché).

Keep dictionary of formulas
On new formula
  Normalize variable list (e.g. (D,A,c)=>"ACD")
  Check if normalized variable list exists in dictionary
  If it exists, reject new formula and break
  For all subsets of variable list
    Check if normalized variable list of subset exists in dictionary
    If it exists, reject new formula and break
  End For
End On

Answer 2

Vous pouvez représenter les contraintes sur l'ensemble des équations sous la forme d'un graphique. Les sommets sont les éléments, avec n[i] éléments de l'équation i . Pour l'équation i il y a donc n[i]*(n[i]-1)/2 paires d'éléments, qui deviennent des arêtes. Il faut itérer à travers les équations, en ajoutant les arêtes au graphe. Chaque fois que vous souhaitez ajouter une arête déjà présente, vous avez trouvé un conflit.

Pour chaque arête, vous pouvez stocker un ensemble de numéros d'équation qui génèrent l'arête ; cela permet d'identifier les conflits spécifiques, plutôt que la simple présence de conflits.

Laisser N est le nombre d'équations et M le nombre d'éléments dans l'équation ayant le plus d'éléments. La complexité temporelle est O(M^2*N) et la complexité de l'espace. Si toutes les équations ont un nombre fixe d'éléments, l'utilisation du temps et de l'espace sera donc de O(N) .

Answer 3

Cette solution s'inspire de celle de Michael J. Barber.

1. Initialiser une table de hachage

2. Lorsque vous avez une équation avec M variables, ajoutez toutes les combinaisons de taille M-1 à la table de hachage. Par exemple : pour A+B+C+D=Z, ajoutez (A,B,C), (A,B,D), (A,C,D) et (B,C,D).

3. Lorsque vous voulez tester la possibilité d'une nouvelle équation avec M variables, vérifiez si tous les sous-ensembles M-1 ne sont PAS dans le hachage.

La complexité : O(mnlog(mn) ).

Answer 4

Vous pourriez définir ce problème d'un autre point de vue : Il n'existe aucune paire de formules dont l'union des éléments contient moins de 5 éléments. Ce qui renvoie à un algorithme qui compare chaque paire de formules si elles passent ce test. Je sais que c'est de la force brute mais je n'arrive pas à imaginer mieux pour l'instant.

Answer 5

Vous pourriez peut-être utiliser certaines des opérations LINQ sur les ensembles. Puisque vous avez décrit votre problème comme étant une liste de listes, vous voulez "veiller à ce qu'aucun élément n'apparaisse dans plus d'une liste". La question de savoir s'il existe une intersection entre les listes ne pourrait-elle pas également être décrite comme une vérification de l'existence d'une intersection entre l'une quelconque des listes ? Ou suis-je un peu à côté de la plaque ?

James Michael Hare a un bel article sur les différentes opérations de réglage disponibles dans LINQ. Vous pouvez commencer par y jeter un coup d'œil :-)