Vsi enolični pari seznama/polja


Kar pogost problem je, da je potrebno poiskati vse možne pare nekega seznama (npr. v pythonu) ali pa polja (npr. v c-ju). Najbolj hitra rešitev z vidika razmišljanja je ta, da ustvariš dvojno for zanko, kateri se obe sprehodita čez seznam/polje in v nek ciljni seznam/polje unikatnih parov dodaja pare, ki še niso v v tem polju/seznamov in ki nista istoležna ((((V tem primeru izključujem pare, kjer se isti element pojavi dvakrat)). Spodaj je v Pythonu prikazana rešitev na ta način, ki pa ni učinkovita, saj ima preverjanje vsebovanosti elementa v seznamu/polju časovno zahtevnost O(n), skupaj pa program z dvojno for zanko časovno zavzame O(n4).

[python]
strings = ["ATATCCG","TCCG","ATGTACTG","ATGTCTG"]
unique_pairs = []

for i, s1 in enumerate(strings):
for j, s2 in enumerate(strings):
if i!=j and (s2, s1) not in unique_pairs:
unique_pairs.append((s1, s2))
[/python]

Zato sem se medtem, ko sem se ukvarjal s podobnim problemom pri večih nalogah, domislil načina, ki časovno zahtevnost zmanjša na polovico in kjer ni potrebe po preverjanje vsebovanosti elementa v seznamu/polju.

Predstavljajte si dvodimenzionalno polje, kjer na vsako dimenzijo postavimo zbirko nizov. Tako bi na primer vrednost celice na preseku prve vrstice in drugega stolpca predstavljala par iz prvega in drugega niza iz zbirke nizov. Če to naredimo za vsako vrstico in vsak stolpec, vidimo da na koncu dobimo nekakšno simetrično matriko (ai,j = aj,i). Da iz matrike dobimo le enolične pare brez parov z istoležnima elementoma, rabimo iz nje vzeti le elemente v spodnjem trikotniku (na diagonali so namreč pari z istoležnimi elementoma, torej istim). Dobimo ga s sprehodom po vseh elementih matrike, kjer je indeks stolpca manjši od indeksa vrstice.

Implementacija opisanega postopka v Pythonu:

[python]
strings = ["ATATCCG","TCCG","ATGTACTG","ATGTCTG"]
unique_pairs = []

for i, s1 in enumerate(strings):
for j, s2 in enumerate(strings):
if j<i:
unique_pairs.append((s1, s2))
[/python]