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].

Nie wiem czy to istotne, ale zbiór e[i] jest już zanurzony w
liniowy porządkek, tzn. jeżeli zachodzi e[i1] < e[i2], to
i1<i2.

Czy istnieje jakieś rozwiązanie o złożonościach
- przygotowanie danych: O(sum #e[i])
- pojedyńcze pytanie O(#e[i])

Czekam na pomysły, literaturę, ...

Pozdrawiam, Mirek.

do góry

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.

do góry

On wto, 03 mar 2009 00:23:34 in article news:<gohppp$efr$1@news.onet.pl>
bartekLTG wrote:
> Mirek wrote:
>> 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?

Napewno nie - ale chodziło o to, że w zadanym zbiorze tak.

Ale pomińmy szczegóły dotyczące tej relacji. Sformułuję ten
problem inaczej.

Dane są:

- Poset P={p}
- Uporządkowany zbiór kluczy K={k}
- Moce P i K spełniają warunek: #P > #K
- Istnieje pewne przyporządkowanie P na K: f(p)=k takie, że:
- jeżeli f(pa)=f(pb) to pa i pb nie są porównywalne
- jeżeli f(pa)<f(pb) to pa i pb nie są porównywalne lub pa<pb

Pytanie brzmi, jak dla danego kj efektywnie wyznaczyć moc
zbioru {ki<kj}, spełniając dodatkowo warunek:

istnieją pa i pb: f(pa)=ki & f(pb)=kj & pa<pb

Pozdrawiam

PS
Ten problem jak nocna zmora wraca do mnie co kilka tygodni ;)

do góry

TYPE "Mirek":
> Dane są:
>
> - Poset P={p}
> - Uporządkowany zbiór kluczy K={k}
> - Moce P i K spełniają warunek: #P > #K - Istnieje pewne
> przyporządkowanie P na K: f(p)=k takie, że:
> - jeżeli f(pa)=f(pb) to pa i pb nie są porównywalne - jeżeli
> f(pa)<f(pb) to pa i pb nie są porównywalne lub pa<pb
>
> Pytanie brzmi, jak dla danego kj efektywnie wyznaczyć moc zbioru
> {ki<kj}, spełniając dodatkowo warunek:
>
> istnieją pa i pb: f(pa)=ki & f(pb)=kj & pa<pb
>
> Pozdrawiam
>
> PS
> Ten problem jak nocna zmora wraca do mnie co kilka tygodni ;)
a nie prościej było napisać:
,,mam funkcję różnowartościową o takim a takim wzorze i chcę sobie ją scałkować."
?
--
/ qo |) :@=N%_g=v=a=g_eD_e=c()=d=8! =%!gN@8'Re. w8in/ad
\ _x/ , ;h-%-a'hA'H4,X0'Xo~xo~xO,R`-%EXp01ITed: *-7/+eh
/ | ng `-%__%--'__%--'__%--~__%--^%B`/$qV3r[o; &GooMee
L _ ._o_O http://groups.yahoo.com/group/oprwtng-dev .L"EnOF"

do góry

On pon, 16 mar 2009 02:18:19 in article news:<gpk9cr$4p4$1@news.mixmin.net>
czas dOSa wrote:
>> PS
>> Ten problem jak nocna zmora wraca do mnie co kilka tygodni ;)
> a nie prościej było napisać:
> ,,mam funkcję różnowartościową o takim a takim wzorze i chcę sobie ją scałkować."

Nie widzę związku :(

do góry