Matematyka.pl

arek1357 pisze: 21 sty 2025, o 10:50Nie

Treściwie
A w czym problem?

Maksymalny element taki sam mogą mieć zbiory różne między sobą...

arek1357 pisze: 21 sty 2025, o 12:03 Maksymalny element taki sam mogą mieć zbiory różne między sobą...

weźmy dwa zbiory uporządkowane
\(\displaystyle{ \left\{ 1, 2, 3, 4, 11\right\} }\) oraz \(\displaystyle{ \left\{ 1, 2, 3, 5, 11\right\} }\)
Identyfikator pierwszego zbioru to \(\displaystyle{ 235465}\) a drugiego \(\displaystyle{ 237193}\)
Mają ten sam maksymalny element
Faktem jest, że trzeba znać wartość maksymalnego elementu
Ale tylko do odczytu
Chodziło o jednoznaczny zapis

WaldekZ pisze: 19 sty 2025, o 22:25
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.

Istnieją
\(\displaystyle{ \left\{ 1, 2, 7, 12\right\} }\) albo \(\displaystyle{ \left\{ 1, 3, 4, 14\right\} }\)

Albo weźmy dwa zbiory
\(\displaystyle{ \left\{ 1, 7, 18\right\} }\) oraz \(\displaystyle{ \left\{ 2, 3, 21\right\} }\)

Jeśli chodzi o matematyczny a nie informatyczny sposób, nieefektywny ? (może jest efektywniejszy), za to pewny to:
- porządkuwujemy zbiór od najmniejszej do największej (choć odwrotny sposób nie gorszy)
- ciąg {1,5,16,26} zapisujemy jako 1A5A16A26 gdzie jest to zapis w systemie 11-owym , a A to cyfra 10

======

Dziękuję za wszystkie pomysły.

Szczerze mówiąc myślałem, że taki problem jest znany i rozwiązany przynajmniej 2000 lat temu (dla prostopadłościanu) lub nieco później dla większych zbiorów, a moja niewiedza wynika z nieuważania w szkole lub też niewielkiego znaczenia tego zagadnienia powodującego jego niebyt w Internecie.

W międzyczasie, widząc, że państwa propozycje podążają, podobnie jak moje wcześniejsze przemyślenia, w kierunkach albo naprawdę wielkich liczb, albo pod względem programowym nie redukującym złożoności obliczeniowej - poszedłem na długi spacer i... znalazłem proste, choć może mało eleganckie rozwiązanie. Po przetestowaniu - działa!, czyli wynajduje wszystkie duplikaty testowych zbiorów. Pomijając szczegóły techniczne związane z precyzją obliczeń na liczbach zmiennoprzecinkowych ogólna idea wygląda tak: każdej dodatniej liczbie naturalnej nadaję \(\displaystyle{ id(n) = \frac {p_{n+c}} {p_n}}\). Stąd cały zbiór ma unikalny identyfikator:

\(\displaystyle{ ID\left\{ n_1 , n_2 , ... , n_k \right\} = \frac{ \prod_{i=1}^{k} p_{n_i+c} }{ \prod_{i=1}^{k} p_{n_i} } }\)

gdzie \(\displaystyle{ p_{n_i} }\) i \(\displaystyle{ p_{n_i+c} }\) to liczby pierwsze, a \(\displaystyle{ c }\) jest niewielką stałą dobraną doświadczanie tak, aby 13 cyfrowa precyzja liczb zmiennoprzecinkowych podołała, a całe wyrażenie nie było zbyt wielkie. Oczywiście nie wyliczam iloczynu licznika i mianownika w całości, tylko partiami, aby nie przekroczyć zakresu int64. Potem liczę iloraz takiej partii itd...

Pozdrawiam
Waldek

czyli jak masz liczy 17, 287, 1023 to bierzesz 17-tą liczbę pierwszą, 287-tą liczbę pierwszą, 1023-tą liczbę pierwszą?

Borneq pisze: 21 sty 2025, o 18:44 czyli jak masz liczy 17, 287, 1023 to bierzesz 17-tą liczbę pierwszą, 287-tą liczbę pierwszą, 1023-tą liczbę pierwszą?

Tak.

A jak pobierasz 154'678'235'123-tą liczbę pierwszą ?
a poza tym ten identyfikator jest ryzykowny, to nie integer a liczba rzeczywista, wystarczy jakiś błąd zmiennoprzecinkowy, aby był inny identyfikator.

Borneq pisze: 21 sty 2025, o 19:37 A jak pobierasz 154'678'235'123-tą liczbę pierwszą ?
a poza tym ten identyfikator jest ryzykowny, to nie integer a liczba rzeczywista, wystarczy jakiś błąd zmiennoprzecinkowy, aby był inny identyfikator.

Bez przesady, operuję najwyżej na tysiącu początkowych liczbach pierwszych, co jest bezproblemowe. Ale mam tablice do \(\displaystyle{ p[1000000]=15485867}\). Wszystkie indeksy i liczby są całkowite, iloczyny również. Dopiero dzielenie jest zmiennoprzecinkowe. Błędy z-p pojawiają się od 10 cyfry, a do jednoznacznej identyfikacji ID wystarczy 7, czasem 8 cyfr, więc mam bardzo duży zapas (stąd ta stała - dla komfortu przyjąłem \(\displaystyle{ c=2}\), ale dla 1 też działa).

Skoro chcesz zakodować dowolny podzbiór zbioru \(\displaystyle{ \{ 1, 2, \ldots, 1000 \}}\), to czy nie jest oczywiste że potrzeba i wystarczy na to tysiąc bitów? Potrzeba, więc z całą pewnością nie uda Ci się takich zbiorów kodować w 64-bitowym typie double precision bez powtórzeń. Ale i wystarczy, co oznacza że możesz zaalokować na to tablicę rozmiaru 125 bajtów i na każdy element kodowanego zbioru przeznaczyć 1 bit (0 - nie należy, 1 - należy).

I otworzyły się niebiosa i usłyszeli Głos Dasio11...

Dzięki, jakież to oczywiste...

Moje "identyfikatory" przeszły testy, bo testowałem wybrane zbiory, czyli dosyć specjalne, albo losowe - nie mogło to raczej doprowadzić do kolizji. Dlaczego tak długo milczałeś!?