Pole a indexy

[Rambous]

Ahoj všichni, potřebuju nakopnout k řešení. Mám takovéhle pole polí s dvouprvky:

[[(0, 0), (100, 0), (100, 44), (62, 44), (0, 38)],
  [(94, 100), (28, 50), (62, 44), (100, 44), (100, 100)],
  [(0, 44), (28, 50), (94, 100), (0, 100)],
  [(28, 50), (0, 44), (0, 38), (62, 44)]]

a potřeboval bych indexy polí, které mají společný alepoň jeden dvouprvek, něco jako:

1 : 2, 4
2 : 1, 3, 4
3 : 2, 4
4 : 1, 2, 3

Jak to udělat jinak, než naivním prohledávání v cyklu?

[Reklama]

[Milfaus]

Začala škola a pohovory o práci 

[Jerry]

co to zkusit tady ?
http://programujte.com/forum/

metod máš hromadu ale na naprogramování školní ulohy je cyklus for nejjednodušší

[jpu]

pouzi cyklus a hotovo.

PS: ci to nie je pokus o vyvolanie flame a opat sa tu budu vyskytovat riesenia a dohady, ktore je lepsie, ako v predchadzajucom vlakne

[colo]

Nerozumím zadání, zkouším si ho domyslet podle "příkladu"  "něco jako" a zdá se mi, že tam jsou dokonce neexistující indexy (řádek "3" má index 4, ale v zadání má jen 4 prvky, takže je to chyba , nebo se čísluje od jedničky místo nuly)?


Porovnává se vůči čemu? Jsou dvouprvky zaměnitelné (v tomto případě 2!=2)? Porovnává se tedy každý dvouprvkvek s každým v celém zadání nebo jen v rámci řádku?

Použil bych ruby a metody each,each_index,each_with_index,map,select,filter

[Reklama]

[jpu]

ja to chapem tak, ze zoberies prvy prvok a porovnavas voci inym prvkom. cize na pozicii 1 je napr. (0,100), a tento prvok porovnavas voci inym prvkom na inych poziciach, ak najdes zhodu vypises poziciu. ale mozem sa mylit. takze cyklus v cykle by mohlo byt jedno z rieseni.

[Kate]

V pythonu se na tohle dá hezky použít metoda sady intersection

Kód: [Vybrat]

>>> arr = [[(0, 0), (100, 0), (100, 44), (62, 44), (0, 38)],
...   [(94, 100), (28, 50), (62, 44), (100, 44), (100, 100)],
...   [(0, 44), (28, 50), (94, 100), (0, 100)],
...   [(28, 50), (0, 44), (0, 38), (62, 44)]]
>>>
>>> set(arr[0]).intersection(arr[1])

{(62, 44), (100, 44)}


V podstatě ti vyplyvne průnik dvou sad. Pokud je průnik neprázdný, máš jistotu že ty dvě sady obsahují aspoň jeden společný tuple

[jpu]

otazka:
ako je implementovana metoda intersection?

[m]

ve standardni knihovne ... datovy typ 'set' od verze pythonu 2.4

[Kate]

otazka:
ako je implementovana metoda intersection?

V podstatě naivní loop Ale aspoň to dovede zpřehlednit kód

[jpu]

a nie loop v loope? sa len pytam, lebo mne napada take riesenie.

[Kate]

a nie loop v loope? sa len pytam, lebo mne napada take riesenie.

Mělo by to fungovat tak že pro každý prvek z prvního (pokud je nějaký menší, tak z něj) setu se zjistí jestli je obsažen v druhém setu (a in b, pro sady je to rychlá operace)) a pokud obsažen je, přidá ho do výstupu.

[Kate]

Ale pochopitelně je to jen část řešení - prostě elegantní a čitelný způsob jak zjistit jestli mají dvě sady aspoň jeden společný prvek.

[BoneFlute]

PS: ci to nie je pokus o vyvolanie flame a opat sa tu budu vyskytovat riesenia a dohady, ktore je lepsie, ako v predchadzajucom vlakne

Po dlouhé době něco, co stálo za to číst a tobě se to nepozdává?!

[gll]

a nie loop v loope? sa len pytam, lebo mne napada take riesenie.

ne. Množiny jsou implementované hashtabulkou. Průnik má časovou složitost závisející na počtu prvků kratší z množin. Bez for cyklu, imperativně třeba takto:

Kód: [Vybrat]

from itertools import *

ll = map(set, [[(0, 0), (100, 0), (100, 44), (62, 44), (0, 38)],
               [(94, 100), (28, 50), (62, 44), (100, 44), (100, 100)],
               [(0, 44), (28, 50), (94, 100), (0, 100)],
               [(28, 50), (0, 44), (0, 38), (62, 44)]])
d = {}

def check(t):
    (i1, s1), (i2, s2) = t
    if s1 & s2 and i1 != i2:
        d.setdefault(i1, []).append(i2)

list(map(check, product(enumerate(ll, start=1), repeat=2)))
print(d)