Identyfikator zbioru

[WaldekZ]

Dla skończonego zbioru złożonego z liczb pierwszych można utworzyć jednoznaczny identyfikator tego zbioru, będący iloczynem jego elementów. A jak skonstruować jednoznaczny identyfikator dla zbioru złożonego z różnych dodatnich liczb naturalnych? Czy ID w postaci pary liczb: iloczynu i sumy elementów spełni zadanie? Jeśli nie, to proszę o jakieś sugestie.

[a4karo]

Jeżeli potrafisz identyfikować zbiory liczb pierwszych, to najprościej napisać funkcję ustalającą równoliczność między liczbami naturalnymi i pierwszymi, co da naturalną odpowiedniość 1-1 między skończonymi podzbiorami `\NN` i \(\displaystyle{ \mathbb{P}}\). I sprawa załatwiona

[arek1357]

Najładniejszy identyfikator:

niech:

\(\displaystyle{ \NN=\left\{ 1, 2, 3,...,n\right\} }\)

\(\displaystyle{ id\left( \NN\right) =n!}\)

choć może mieć wadę i pokryć się z jakimś innym identyfikatorem innego zbioru , no ale...

[Borneq]

Gdy ograniczymy liczby naturalne do pewnego \(\displaystyle{ n}\) wtedy zbiór liczb daje się odwzorować na bity liczby wielkości \(\displaystyle{ 2^n}\) w każdym razie identyfikator musi być wielkości wykładniczej w porównaniu z liczbami.

[WaldekZ]

Dziękuję za dotychczasowe odpowiedzi, ale to ma robić program na 64 bitach od którego oczekuję znacząco krótszego czasu obliczeń, niż przy metodzie siłowej. W grę wchodzą miliony zbiorów, z których trzeba usunąć powtórzenia, a jest ich dużo. Propozycja a4karo jest sensowna, ale tylko do 14 elementów - powyżej iloczyn przekracza 64 bity. Pozostałe propozycje jeszcze szybciej.

Ten problem można ująć geometrycznie:
Czy istnieją dwa znacząco różne prostopadłościany, które mają identyczną objętość i identyczną sumę długości krawędzi?
Przez "prostopadłościan" należy rozumieć figurę n-wymiarową, a przez "objętość" to, co jest właściwe dla wymiaru n.

Dla n=2 jest to prostokąt i odpowiedź jest negatywna - nie ma takich dwóch prostokątów (o identycznych powierzchniach i obwodzie). Odpowiedź negatywna jest pożądana, gdyż oznacza, że identyfikator złożony z iloczynu i sumy długości krawędzi jest unikalny.
Dla n=3 trochę namęczyłem się z obliczeniami, ale wyszło mi, że nie ma też dwóch różnych prostopadłościanów spełniających warunki (nie mam pewności, czy nie nagiąłem gdzieś założeń).
Ale dla n>3 nic nie znalazłem i nic nie wyliczyłem.

Gdyby ktoś znał odpowiedź dla \(\displaystyle{ n \ge 3}\) i byłaby ona negatywna, to by oznaczało, że trójka liczb:
\(\displaystyle{ n - liczba~elementów }\) (geometrycznie: wymiar przestrzeni)
\(\displaystyle{ M - iloczyn~elementów }\) (geometrycznie: objętość)
\(\displaystyle{ S - suma~elementów }\) (geometrycznie: suma długości w każdym z wymiarów)
jest unikalnym identyfikatorem dla zbioru (i prostopadłościanu), o który mi chodzi.

Poza tym jest to interesujący problem sam w sobie

[Borneq]

Czyli to nie problem matematyczny ale informatyczny. Owszem silnia 64 bitowych liczb byłaby bardzo wielka. W C++ są standardowe biblioteki do zbiorów oparte o drzewa czerwono-czarne czy tablice hasz, a identyfikator to hasz liczb ze zbioru np. xxhash, zawsze możliwe kolizje, ale zamiast 32 bitów można dać 64 bity.
Albo w ogóle sha , teoretycznie kolizja możliwa, ale nie powinna wystąpić, tak jak nie daje się praktycznie zgadnąć adresu bitcoinowego.

[matmatmm]

Ten identyfikator to tak naprawdę funkcja wzajemnie jednoznaczna między \(\displaystyle{ \NN}\) oraz rodziną skończonych podzbiorów \(\displaystyle{ \NN}\). Proponuję ponumerować w takiej kolejności

\(\displaystyle{ \{1\}, \{2\}, \{1,2\}, \{3\}, \{1,3\}, \{2,3\}, \{1,2,3\}, \{4\}, \{1,4\}, \{2,4\}, \{1,2,4\}, \{3,4\}, \{1,3,4\}, \{2,3,4\}, \{1,2,3,4\},\ldots}\)

W jakim sensie propozycja a4karo jest sensowniejsza od tej? Przykładowo zbiór \(\displaystyle{ \{1,2,3,4\}}\) ma kod \(\displaystyle{ 15}\) tutaj, a tam będzie \(\displaystyle{ 2\cdot 3\cdot 5\cdot 7=210}\).

[arek1357]

jak skonstruować jednoznaczny identyfikator dla zbioru złożonego z różnych dodatnich liczb naturalnych?

Z różnych niekoniecznie kolejnych więc iloczyny a tym bardziej potęgi odpadają bo na dwa zbiory równoliczne \(\displaystyle{ 2^{|A|}}\) będzie takie samo...

tzreba by najpierw wyliczyć ile zbiorów \(\displaystyle{ n}\) elementowych ma tę samą sumę...

a nawet w ogóle ile zbiorów ma sumę równą \(\displaystyle{ K}\) i wtedy zacząć numerować, czyli tak naprawdę prowadzać liniowy porządek w rodzinie skończonych podzbiorów liczb naturalnych...

[arek1357]

Problem nie jest ani głupi ani błahy , warto dobrze przeanalizować a pomysłów może być wiele...

[Brombal]

Prostopadłościan płaski ma po dwie krawędzie każdego wymiaru. Prostopadłościan w trzech wymiarach ma po cztery krawędzie każdego wymiaru. Ile krawędzi ma każdego wymiaru ma prostopadłościan n wymiarowy?

[arek1357]

Np dla zbioru \(\displaystyle{ P(3)}\)

\(\displaystyle{ \left\{ 1\right\} \le \left\{ 2\right\} \le \left\{ 3\right\} \le \left\{ 1 , 2\right\} \le \left\{ 1, 3\right\} \le \left\{ 2,3\right\} \le \left\{ 1 , 2 , 3\right\}}\)

Można etykietować teraz łatwo ale już, jeżeli weźmiemy jakiś zbiór , który nie zawiera się w \(\displaystyle{ P(3)}\) to niestety trza zacząć etykietowanie od początku od \(\displaystyle{ P(n)}\) , gdzie n byłby maksymalnym elementem w tym dodatkowym zbiorze, więc ma to swoje wady i zalety, chyba że zaczniemy od początku etykietować w: \(\displaystyle{ P( \infty )}\) ale same
skończone porządkować...

[a4karo]

Fakt, że zbiory \(\displaystyle{ \{1,2,3\} }\) oraz \(\displaystyle{ \{6\}}\) mają te same identyfikatory pokazuje, że iloczyn i suma to słaby identyfikator.

Inne przykłady
\(\displaystyle{ \{1,2,3\}\cup A}\) i \(\displaystyle{ \{6\}\cup A}\), gdzie \(\displaystyle{ A}\) jest dowolnym podzbiorem \(\displaystyle{ \{4,5,7,8,9,10,...\}}\)

Albo
\(\displaystyle{ \{1,2,3,4\}\cup A}\) i \(\displaystyle{ \{4,6\}\cup A}\), gdzie \(\displaystyle{ A}\) jest dowolnym podzbiorem \(\displaystyle{ \{5,7,8,9,10,...\}}\)

[WaldekZ]

@a4karo
Czy możesz podać podobne przykłady dla zbiorów równolicznych?

Dodano po 10 minutach 33 sekundach:

W jakim sensie propozycja a4karo jest sensowniejsza od tej? Przykładowo zbiór \(\displaystyle{ \{1,2,3,4\}}\) ma kod \(\displaystyle{ 15}\) tutaj, a tam będzie \(\displaystyle{ 2\cdot 3\cdot 5\cdot 7=210}\).

Liczby są wprawdzie w zbiorze, ale nie są uporządkowane rosnąco ( np. \(\displaystyle{ \left\{ 3, 1, 4, 2 \right\} }\) )

Przydzielenie kodu 15 wymaga sortowania i wyszukiwania. Iloczyn 210 to tylko... iloczyn.

[Brombal]

Ponieważ to zbiór to można go porządkować dowolnie i nadal będzie zbiorem.
Uporządkujmy zbiór rosnąco. (zakładam, że \(\displaystyle{ 0}\) moze być elementem zbioru)
Znajdźmy liczbę maksymalną \(\displaystyle{ a _{max} }\).
Przedstawmy jednoznacznie zbiór jako liczbę w systemie liczbowym \(\displaystyle{ a _{max}+1 }\) złożoną z kolejnych elementów zbioru.
Może być?

[arek1357]

Nie