Mirek wrote:
> Witam,
>
> od pewnego czasu nurtuje mnie tytułowe pytanie: "Ile elementów
> w zadanym zbiorze jest mniejszych od wybranego elementu?"
>
> Dla dość specyficznej relacji częsciowego porządku szukam
> efektywnej struktury/algorytmu, która ułatwi mi odpowiedź na to
> pytanie.
>
> O to charakterystyka zbioru:
>
> - Zbiór unikalnych elementów E={e[i],i=1...N} o liczności rzędu 10^6
>
> - Każdy element posiada pewną liczbę cech (obiekty mają rożne
> ilości cech), oznaczmy to e[i]={e[i,j],j=1...n_i}, średnia
> liczność cech w zbior E wynosi około 30-50, tzn.:
> sum_i #e[i] ~= 50*#E
>
> - Każda cecha e[i,j] jest uporządkowawaną parą liczb dodatnich:
> e[i,j] = ( e[i,j,1], e[i,j,2] ), gdzie e[i,j,1] <= e[i,j,2].
> (równość zachodzi co najwyżej dla jednej cechy w elemencie)
>
> - Relacja częściowego porządku cech:
>
> e[i1,j1] < e[i2,j2] <==>
> (e[i1,j1,1] < e[i2,j2,1]) & (e[i1,j1,2] < e[i2,j2,2])
>
> Każda cecha (czyli para liczbowa) jest unikalna w całym
> zbiorze E, więc relacja e[i1,j1] = e[i2,j2] zachodzi tylko
> gdy i1=i2 i j1=j2. Nie wszystkie cechy są porównywalne wg
> powyższej definicji. W dodatku *żadne* dwie cechy danego
> elementu nie są porównywalne.
>
> - Na koniec właściwa relacja porządkująca elementy e[i]:
>
> e[i1] < e[i2] <==>
> istnieje choć jedna para j1,j2: e[i1,j1] < e[i2,j2]
>
> Definicja jest jednoznaczna/niesprzeczna, tzn. jeżeli
> dla danych i1,i2 istnieją powyższe j1,j2, to nie istnieją
> k1, k2 takie, że zachodzi relacja odwrotna e[i1,k1] > e[i2,k2].

Napewno?

e[1,1,1] = 50
e[1,1,2] = 51

e[1,2,1] = 2
e[1,2,2] = 3

e[2,1,1] = 48
e[2,1,2] = 49

e[2,2,1] = 4
e[2,2,2] = 5

z tego

e[1,1]>e[2,2]
e[1,2]<e[2,1]

wiec e1>e2 e2>e2 ;]


pozdr

--
bartekltg
...aby UseNet rósł w siłę a trolle żyły dostatnio.