Trouver des paires parmi un tableau

Le 01-12-2015, Kevin Denis nous expliquait dans
fr.comp.lang.python
(<slrnn5rrei.3uk.kevin@slackwall.local.tux>) :

Bonjour,

j'ai un grand nombre d'enregistrements du genre:
['a', 'b', 'c']
['d', 'e', 'f']
etc...

Je cherche un moyen simple et rapide qui serait capable de me dire
si une paire d'éléments fait partie du même tableau ou pas.

Par exemple:
'a' and 'b' => True
'a' and 'd' => False
'f' and 'd' => True
etc...

J'ai du mal à voir comment m'y prendre mis à part parser à chaque fois
tous les tableaux pour le premier élément, puis voir si dans ce tableau
le second élément est présent.

Pourquoi ne pas faire les deux en une seule passe ?
Je n'ai peut-etre pas tout compris mais il ne me semble pas nécessaire
de parser le tableau autrement qu'avec l'opérateur 'in':

tableau = ['a', 'b', 'c']

'a' and 'b' in tableau
=> True

'a' and 'c' in tableau
=> True

'a' and 'd' in tableau
=> False

'd' and 'e' in tableau
=> False

Mais j'ai un paquet de requêtes à faire et le nombre de tableau est
grand...
J'hésitais aussi à faire un dictionnaire gigantesque:
{ 'a': ['b','c']; 'b':['a','c']; 'c':['a', 'b']; 'd':['e','f'] etc.. }
la recherche du premier élément est immédiate, et il suffit de regarder si le
second est dans le tableau correspondant à la clé..
L'ennuyeux, c'est que je vais avoir des grosses séries de tableaux et que je
ne voudrais pas consommer trop de mémoire: quelques milliers de lignes avec de
2 à 10 enregistrements.

En bonus, je cherche aussi à savoir si des valeurs peuvent être mises en
relation de manière indirecte:

['a', 'b', 'c']
['d', 'e', 'f']
['a', 'g']
['g', 'h', 'i']

'a' et 'i' sont proches, ils sont donc liées.
'b' et 'i' sont également liés (mais moins proches).
'e' et 'i' ne sont pas liés.

Peux-tu définir 'proche' ?

--
J'suis la môme kaléidoscope.
C'est moi qu'j'faisais l'trottoir d'en face
Du temps ou j'avais dans l'carosse
Une chatte qu'était pas radada
-- H.F. Thiéfaine, La môme kaléïdoscope

Doug713705 <doug.letough@free.fr> writes:

Le 01-12-2015, Kevin Denis nous expliquait dans
fr.comp.lang.python
(<slrnn5rrei.3uk.kevin@slackwall.local.tux>) :

j'ai un grand nombre d'enregistrements du genre:
['a', 'b', 'c']
['d', 'e', 'f']
etc...

Je cherche un moyen simple et rapide qui serait capable de me dire
si une paire d'éléments fait partie du même tableau ou pa s.

Par exemple:
'a' and 'b' => True
'a' and 'd' => False
'f' and 'd' => True
etc...

J'ai du mal à voir comment m'y prendre mis à part parser à   chaque fois
tous les tableaux pour le premier élément, puis voir si dans c e tableau
le second élément est présent.

Pourquoi ne pas faire les deux en une seule passe ?
Je n'ai peut-etre pas tout compris mais il ne me semble pas nécessai re
de parser le tableau autrement qu'avec l'opérateur 'in':

tableau = ['a', 'b', 'c']

[...]

'a' and 'd' in tableau
=> False

'd' and 'a' in tableau
=> True

Tu te trompes sur le sens de and, qui ici signifie (x) and (y in
tableau).

De toute façon, il a plein de tableaux, on ne va donc pas répà ©ter "(x in
t) and (y in t)" sur tous les tableaux.

Mais j'ai un paquet de requêtes à faire et le nombre de tablea ux est
grand...
J'hésitais aussi à faire un dictionnaire gigantesque:
{ 'a': ['b','c']; 'b':['a','c']; 'c':['a', 'b']; 'd':['e','f'] etc.. }
la recherche du premier élément est immédiate, et il suff it de regarder si le
second est dans le tableau correspondant à la clé..
L'ennuyeux, c'est que je vais avoir des grosses séries de tableaux et que je
ne voudrais pas consommer trop de mémoire: quelques milliers de lig nes avec de
2 à 10 enregistrements.

L'important n'est pas le nombre de tableaux, mais la taille de ton
dictionnaire, qui dépend directement du nombre de valeurs différe ntes
qui peuvent apparaitre. Si tu as quelques valeurs, pas de problèmes. Si
tu en as beaucoup, et si chaque valeur est associée à beaucoup d' autres,
ça va consommer pas mal de mémoire.

Mais en fait tu as un graphe entre tes valeurs. Ta structure n'est pas
mauvaise, mais tu pourrais aussi utiliser un ensemble de couples.

En bonus, je cherche aussi à savoir si des valeurs peuvent êtr e mises en
relation de manière indirecte:

['a', 'b', 'c']
['d', 'e', 'f']
['a', 'g']
['g', 'h', 'i']

'a' et 'i' sont proches, ils sont donc liées.
'b' et 'i' sont également liés (mais moins proches).
'e' et 'i' ne sont pas liés.

Peux-tu définir 'proche' ?

Oui, là c'est incompréhensible, il faut plus de détails.

-- Alain.

Le 01-12-2015, Doug713705 <doug.letough@free.fr> a écrit :

Pourquoi ne pas faire les deux en une seule passe ?
Je n'ai peut-etre pas tout compris mais il ne me semble pas nécessaire
de parser le tableau autrement qu'avec l'opérateur 'in':

tableau = ['a', 'b', 'c']

'a' and 'b' in tableau
=> True

'a' and 'c' in tableau
=> True

'a' and 'd' in tableau
=> False

'd' and 'e' in tableau
=> False

J'ignorais complètement que cette syntaxe fonctionnait, mais ça me
va bien, merci

En bonus, je cherche aussi à savoir si des valeurs peuvent être mises en
relation de manière indirecte:

['a', 'b', 'c']
['d', 'e', 'f']
['a', 'g']
['g', 'h', 'i']

'a' et 'i' sont proches, ils sont donc liées.
'b' et 'i' sont également liés (mais moins proches).
'e' et 'i' ne sont pas liés.

Peux-tu définir 'proche' ?

a et i sont proches, car a et g sont dans le même tableau, et g et i sont
dans le même tableau, donc on a a -> g -> i, d'ou a -> i
par contre, pour e et i, on ne peut jamais trouver une relation
en passant par un ou plusieurs intermédiaires.
--
Kevin

Kevin Denis <kevin@nowhere.invalid> writes:

'd' and 'e' in tableau
=> False

J'ignorais complètement que cette syntaxe fonctionnait, mais ça me
va bien, merci

Elle ne fonctionne pas, ou plutot elle ne fait pas ce que tu veux.

['a', 'b', 'c']
['d', 'e', 'f']
['a', 'g']
['g', 'h', 'i']

'a' et 'i' sont proches, ils sont donc liées.
'b' et 'i' sont également liés (mais moins proches).
'e' et 'i' ne sont pas liés.

Peux-tu définir 'proche' ?

a et i sont proches, car a et g sont dans le même tableau, et g et i sont
dans le même tableau, donc on a a -> g -> i, d'ou a -> i
par contre, pour e et i, on ne peut jamais trouver une relation
en passant par un ou plusieurs intermédiaires.

Tu cherches les composantes connexes d'un graphe. Regarde

https://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29

et ensuite tu voudras peut-etre pondérer les associations, puis

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

(je mets les versions anglaises parce qu'elles me semblent plus
accessibles).

-- Alain.

Le 01-12-2015, Kevin Denis nous expliquait dans
fr.comp.lang.python
(<slrnn5s0rf.3uk.kevin@slackwall.local.tux>) :

Le 01-12-2015, Doug713705 <doug.letough@free.fr> a écrit :

Pourquoi ne pas faire les deux en une seule passe ?
Je n'ai peut-etre pas tout compris mais il ne me semble pas nécessaire
de parser le tableau autrement qu'avec l'opérateur 'in':

tableau = ['a', 'b', 'c']

'a' and 'b' in tableau
=> True

'a' and 'c' in tableau
=> True

'a' and 'd' in tableau
=> False

'd' and 'e' in tableau
=> False

J'ignorais complètement que cette syntaxe fonctionnait, mais ça me
va bien, merci

Oui mais je fais une gorssière erreur, voir la correction qu'apporte
Alain Ketterlin. Tant que le premier élément est non nul (not None),
qu'il n'est pas égal à False et que le deuxième élément est contenu dans
tableau l'expression retournera True.

Quitte à continuer sur cette voie il vaut donc mieux écrire:

'a' in tableau and 'b' in tableau

En bonus, je cherche aussi à savoir si des valeurs peuvent être mises en
relation de manière indirecte:

['a', 'b', 'c']
['d', 'e', 'f']
['a', 'g']
['g', 'h', 'i']

'a' et 'i' sont proches, ils sont donc liées.
'b' et 'i' sont également liés (mais moins proches).
'e' et 'i' ne sont pas liés.

Peux-tu définir 'proche' ?

a et i sont proches, car a et g sont dans le même tableau, et g et i sont
dans le même tableau, donc on a a -> g -> i, d'ou a -> i
par contre, pour e et i, on ne peut jamais trouver une relation
en passant par un ou plusieurs intermédiaires.

D'après mes souvenirs ça ressemblerait bien à un problème de connexité
de graphe.

- L'ensemble des éléments de tous les tableaux sont les sommets du
graphe.
- Chaque tableau est une clique dans le graphe (connexe par définition).
- Si deux cliques ont au moins un élément commun alors le sous-graphe
qu'elles représentent est connexe (et donc tous ses sommets sont
'proches' entre eux dans ta définition de 'proche').
- Si tableau1 à un élément commun avec tableau2 et tableau2 en a un
avec tableau3, le graphe réprésenté par tableau1 union tableau3 est
connexe, etc.

https://fr.wikipedia.org/wiki/Graphe_connexe
https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_profondeur

--
Je ne connaîtrai rien de tes habitudes
Il se peut même que tu sois décédée
Mais j'demanderai ta main pour la couper
-- H.F. Thiéfaine, L'ascenceur de 22H43

En complément de tout ce qui a été dit, je te suggérerai d'utiliser le
type set (https://docs.python.org/2/library/stdtypes.html#set python 2.x
ou
https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset
pour Python 3.x), qui de mémoire doit être plus rapide et moins gourmand
en mémoire.
De plus ce type me semble dans l'esprit bien plus proche de ce que tu
souhaites faire que les listes, avec des méthodes built-in union(),
différence(), intersection(), ...
Par contre si le reste de ton code avec ces objets est très différent,
cela demande une réflexion plus approfondie.

My two cents,

LT

Le 01/12/2015 19:13, Doug713705 a écrit :

Le 01-12-2015, Kevin Denis nous expliquait dans
fr.comp.lang.python
(<slrnn5s0rf.3uk.kevin@slackwall.local.tux>) :

Le 01-12-2015, Doug713705 <doug.letough@free.fr> a écrit :

Pourquoi ne pas faire les deux en une seule passe ?
Je n'ai peut-etre pas tout compris mais il ne me semble pas nécessaire
de parser le tableau autrement qu'avec l'opérateur 'in':

tableau = ['a', 'b', 'c']

'a' and 'b' in tableau
=> True

'a' and 'c' in tableau
=> True

'a' and 'd' in tableau
=> False

'd' and 'e' in tableau
=> False

J'ignorais complètement que cette syntaxe fonctionnait, mais ça me
va bien, merci

Oui mais je fais une gorssière erreur, voir la correction qu'apporte
Alain Ketterlin. Tant que le premier élément est non nul (not None),
qu'il n'est pas égal à False et que le deuxième élément est contenu dans
tableau l'expression retournera True.

Quitte à continuer sur cette voie il vaut donc mieux écrire:

'a' in tableau and 'b' in tableau

En bonus, je cherche aussi à savoir si des valeurs peuvent être mises en
relation de manière indirecte:

['a', 'b', 'c']
['d', 'e', 'f']
['a', 'g']
['g', 'h', 'i']

'a' et 'i' sont proches, ils sont donc liées.
'b' et 'i' sont également liés (mais moins proches).
'e' et 'i' ne sont pas liés.

Peux-tu définir 'proche' ?

a et i sont proches, car a et g sont dans le même tableau, et g et i sont
dans le même tableau, donc on a a -> g -> i, d'ou a -> i
par contre, pour e et i, on ne peut jamais trouver une relation
en passant par un ou plusieurs intermédiaires.

D'après mes souvenirs ça ressemblerait bien à un problème de connexité
de graphe.

- L'ensemble des éléments de tous les tableaux sont les sommets du
graphe.
- Chaque tableau est une clique dans le graphe (connexe par définition).
- Si deux cliques ont au moins un élément commun alors le sous-graphe
qu'elles représentent est connexe (et donc tous ses sommets sont
'proches' entre eux dans ta définition de 'proche').
- Si tableau1 à un élément commun avec tableau2 et tableau2 en a un
avec tableau3, le graphe réprésenté par tableau1 union tableau3 est
connexe, etc.

https://fr.wikipedia.org/wiki/Graphe_connexe
https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_profondeur

Cémoi :

En complément de tout ce qui a été dit, je te suggérerai d'utiliser le
type set (https://docs.python.org/2/library/stdtypes.html#set python 2.x
ou
https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset
pour Python 3.x), qui de mémoire doit être plus rapide et moins gourmand
en mémoire.
De plus ce type me semble dans l'esprit bien plus proche de ce que tu
souhaites faire que les listes, avec des méthodes built-in union(),
différence(), intersection(), ...
Par contre si le reste de ton code avec ces objets est très différent,
cela demande une réflexion plus approfondie.

y = ['a', 'e', 'f']

sets_y = set(map(frozenset, itertools.combinations(y, 2)))

print({'a', 'e'} in sets_y)
print({'e', 'a'} in sets_y)
print({'d', 'm'} in sets_y)

--
Pierre Maurette

Le 02/12/2015 21:15, Pierre Maurette a écrit :

Cémoi :

En complément de tout ce qui a été dit, je te suggérerai d'utiliser le
type set (https://docs.python.org/2/library/stdtypes.html#set python 2.x
ou
https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset
pour Python 3.x), qui de mémoire doit être plus rapide et moins gourmand
en mémoire.
De plus ce type me semble dans l'esprit bien plus proche de ce que tu
souhaites faire que les listes, avec des méthodes built-in union(),
différence(), intersection(), ...
Par contre si le reste de ton code avec ces objets est très différent,
cela demande une réflexion plus approfondie.

y = ['a', 'e', 'f']

sets_y = set(map(frozenset, itertools.combinations(y, 2)))

print({'a', 'e'} in sets_y)
print({'e', 'a'} in sets_y)
print({'d', 'm'} in sets_y)

Oui, ou sans utiliser les itertools mais avec des méthodes built-in des
sets ou frozensets:


y = ['a', 'e', 'f']

print(frozenset(['a', 'e']).issubset(frozenset(y)))
print(frozenset(['e', 'a']).issubset(frozenset(y)))
print(frozenset(['d', 'm']).issubset(frozenset(y)))


LT

Cémoi <laurent.thioudellet@nospam.free.fr> writes:

Le 02/12/2015 21:15, Pierre Maurette a écrit :

Cémoi :

En complément de tout ce qui a été dit, je te suggé rerai d'utiliser le
type set (https://docs.python.org/2/library/stdtypes.html#set python 2.x
ou
https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset
pour Python 3.x), qui de mémoire doit être plus rapide et moi ns gourmand
en mémoire.
De plus ce type me semble dans l'esprit bien plus proche de ce que tu
souhaites faire que les listes, avec des méthodes built-in union(),
différence(), intersection(), ...
Par contre si le reste de ton code avec ces objets est très diff érent,
cela demande une réflexion plus approfondie.

y = ['a', 'e', 'f']

sets_y = set(map(frozenset, itertools.combinations(y, 2)))

print({'a', 'e'} in sets_y)
print({'e', 'a'} in sets_y)
print({'d', 'm'} in sets_y)

Oui, ou sans utiliser les itertools mais avec des méthodes built-in des
sets ou frozensets:


y = ['a', 'e', 'f']

print(frozenset(['a', 'e']).issubset(frozenset(y)))
print(frozenset(['e', 'a']).issubset(frozenset(y)))
print(frozenset(['d', 'm']).issubset(frozenset(y)))

Hmmm, n'oublions pas que dans le problème initial, il y avait plein de
listes y1 y2 etc. et que le but était de ne pas forcément toutes les
conserver.

D'autre part, utiliser un set (frozen ou pas) pour des couples confine à  
l'excès de zèle, un tuple devrait bien suffire. Voici une version qui
fait ça. D'abord les combinaisons :

def normtuple(x,y):
return (x,y) if x<y else (y,x)

def combinaisons(l):
return set([ normtuple(l[i],l[j])
for i in range(len(l))
for j in range(i+1,len(l)) ])

records = [
['a', 'b', 'c'],
['d', 'e', 'f'],
['a', 'g'],
['g', 'h', 'i']
]

sets_y0 = combinaisons(records[0])
print sets_y0

Oui, pour éviter les doublons on ordonne les éléments des tu ples. Si
l'ordre dans les listes initiales avait une importance, on pourrait se
passer de cet ordre, mais on aurait plus de tuples.

Ensuite, pour former l'ensemble des couples apparaissant dans toutes les
listes initiales, on calcule les couples sur chaque liste, puis on
fusionne tous les ensembles obtenus :

def graph(ll):
return reduce(set.union,map(combinaisons,ll))

g = graph(records)
print g
print type(g), type(set(g).pop()) # pour voir

Bien sur pour tester l'appartenance, il faut s'asurer que le tuple est
"dans le bon sens" :

print(normtuple('a', 'b') in g)
print(normtuple('b', 'a') in g)
print(('b', 'a') in g) # 'tention !
print(normtuple('d', 'm') in g)
print(normtuple('d', 'f') in g)
print(normtuple('a', 'g') in g)

-- Alain.