Mnożenie permutacji a liczba unikalnych wyników

[osobliwy nick]

Wybieram sobie jakieś permutacje. Każdą permutację numeruję od zera:

0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0

Można je przekonwertować na takie numerowane od jedynki, wystarczy dodać do każdego wiersza na dole liczbę 1. Wypisuję je w taki sposób, bo mi tak wygodniej. Więc mam powiedzmy takie permutacje:

(7 6 5 4 3 2 1 0)

(3 6 1 4 7 2 5 0)

(3 6 5 4 7 2 1 0)

(1 2 3 4 5 6 7 0)

(5 2 7 4 1 6 3 0)

(1 2 7 4 5 6 3 0)

(7 6 1 4 3 2 5 0)

(5 2 3 4 1 6 7 0)

I zaczynam je mnożyć. Powiedzmy, że interesują mnie iloczyny 3-czynnikowe. Tworzę wszystkie wariacje z powtórzeniami. Będzie ich 8^3=512. Ile różnych permutacji otrzymam w wyniku? Jaka będzie ich częstotliwość i rozkład?

Załóżmy, że jakiś iloczyn da mi nową permutację A. Ile razy pojawi się ona jako wśród wszystkich możliwych 512 wariacji bez powtórzeń tych iloczynów.

Można to sprawdzić obliczeniowo, ale chcę rozważać permutacje tak duże, że nie będzie dało się ich sprawdzić obliczeniowo w żadnym rozsądnym czasie. Np. wychodząc od 64 permutacji wygenerować wszystkie 30-wyrazowe wariacje z powtórzeniami ich iloczynów.

[J.F.]

Dnia Tue, 17 Dec 2019 11:33:33 -0800 (PST), osobliwy nick napisał(a):
> Wybieram sobie jakieś permutacje. Każdą permutację numeruję od zera:
>
> 0 1 2 3 4 5 6 7
> 7 6 5 4 3 2 1 0
>
> Można je przekonwertować na takie numerowane od jedynki, wystarczy dodać do każdego wiersza na dole liczbę 1. Wypisuję je w taki sposób, bo mi tak wygodniej. Więc mam powiedzmy takie permutacje:
>
> (7 6 5 4 3 2 1 0)

> [...]

> (5 2 3 4 1 6 7 0)
>
> I zaczynam je mnożyć. Powiedzmy, że interesują mnie iloczyny
> 3-czynnikowe. Tworzę wszystkie wariacje z powtórzeniami. Będzie ich
> 8^3=512. Ile różnych permutacji otrzymam w wyniku? Jaka będzie ich
> częstotliwość i rozkład?
>
> Załóżmy, że jakiś iloczyn da mi nową permutację A. Ile razy pojawi
> się ona jako wśród wszystkich możliwych 512 wariacji bez powtórzeń
> tych iloczynów.
>
> Można to sprawdzić obliczeniowo, ale chcę rozważać permutacje tak
> duże, że nie będzie dało się ich sprawdzić obliczeniowo w żadnym
> rozsądnym czasie. Np. wychodząc od 64 permutacji wygenerować
> wszystkie 30-wyrazowe wariacje z powtórzeniami ich iloczynów.

W jakim sensie "mnożyc" ? Bo na oko to mieszasz rozne pojecia.

30-wyrazowe, czyli "mnozenie" w jakis sposob sklada ci wyrazy,
co prawda w przykladzie masz permutacje 8 wyrazowe, to w efekcie
powstanie 24 wyrazowy element.

Jesli zaczales od N roznych permutacji/elementow,
to takich uporzadkowanych zlozem bedzie N^3, kazde inne.

J.

[osobliwy nick]

> W jakim sensie "mnożyc" ? Bo na oko to mieszasz rozne pojecia.

Chodzi o złożenie permutacji:

(7 6 5 4 3 2 1 8) * (3 6 1 4 7 2 5 8) = (5 2 7 4 1 6 3 8)

Przy okazji taki szczegół. Numerujmy permutacje jednak od 1 do 8, zaś zera zamieńmy na ósemki. Wyjściowe permutacje możemy więc zapisać tak:

1 2 3 4 5 6 7 8
7 6 5 4 3 2 1 8

1 2 3 4 5 6 7 8
3 6 1 4 7 2 5 8

1 2 3 4 5 6 7 9
3 6 5 4 7 2 1 8

1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8
5 2 7 4 1 6 3 8

1 2 3 4 5 6 7 8
1 2 7 4 5 6 3 8

1 2 3 4 5 6 7 8
7 6 1 4 3 2 5 8

1 2 3 4 5 6 7 8
5 2 3 4 1 6 7 8

> 30-wyrazowe, czyli "mnozenie" w jakis sposob sklada ci wyrazy,
> co prawda w przykladzie masz permutacje 8 wyrazowe, to w efekcie
> powstanie 24 wyrazowy element.

No to nie o takie mnożenie mi chodzi.

> Jesli zaczales od N roznych permutacji/elementow,
> to takich uporzadkowanych zlozem bedzie N^3, kazde inne.

Być może według tej definicji mnożenia, którą przyjąłeś, według mojej na pewno nie będzie ich N^3.

Po pierwsze każda permutacja ma na czwartym miejscu 4, a na ostatnim 8, możemy zatem skrócić te permutacje (w celach obliczeniowych, później 4 i 8 trzeba zawsze dopisać), bo nowa wymnożona permutacja zawsze zachowa tę zasadę:

1 2 3 5 6 7
7 6 5 3 2 1

1 2 3 5 6 7
1 2 3 5 6 7

1 2 3 5 6 7
3 6 1 7 2 5

1 2 3 5 6 7
5 2 7 1 6 3

1 2 3 5 6 7
3 6 5 7 2 1

1 2 3 5 6 7
1 2 7 5 6 3

1 2 3 5 6 7
7 6 1 3 2 5

1 2 3 5 6 7
5 2 3 1 6 7

Po drugie, każdy element parzysty daje liczbę parzystą, a nieparzysty - nieparzystą (nie wiem, czy to akurat wnosi, ale tak jest). Po trzecie jak widać każda permutacja ma swoje symetryczne odbicie. Oznacza to, że:

a*sym(b) = sym(a)*b

Czyli na przykład:

(7 6 5 3 2 1) * (3 6 1 7 2 5) = (1 2 3 5 6 7) * (5 2 7 1 6 3) = (5 2 7 1 6 3)

Zmniejsza to liczbę wszystkich unikalnych wyników. Jeżeli zaczniemy od iloczynów dwu-czynnikowych, to teoretycznie mamy 8^2 wariacji z powtórzeniami. Ale wynik każdego iloczynu dwu-elementowego, możemy wyrazić za pomocą innego iloczynu dwu-elementowego (bo występują te symetrie). Więc będzie ich o połowę mniej, tylko 32. Teraz pytanie, czy wśród tych nowych 32 permutacji znowu połowa będzie symetryczna. Wydaje się, że tak, symetrię powinniśmy uzyskać na takiej zasadzie:

a*sym(b)

a*b

Wyniki tych mnożeń powinny być symetryczne. Więc dla każdej wariacji możemy znaleźć jej symetryczny odpowiednik. Teraz musimy pomnożyć nasze uzyskane 32 permutacje razy wyjściowe 8 permutacji. Mnożąc każda z każdą mamy 8*32 możliwości, ale możemy to zrobić na dwa sposoby, gdy nasze pierwotne permutacji są pierwszym czynnikiem albo, gdy są na drugim miejscu (bo mnożenie permutacji nie jest przemienne). Daje to 512 wyników. Tyle, że znów każdy iloczyn możemy zapisać na 2 sposoby:

a*sym(b) = sym(a)*b

Zatem unikalnych wyników powinno być nie więcej niż 256. Tylko, czy dokładnie tyle? Mogą wystąpić jeszcze inne okoliczności, które zmniejszą liczbę unikalnych wyników. Jeżeli jakiś iloczyn a*b da nam element neutralny - permutację neutralną, to a*b*c da nam c. Jeżeli jakaś permutacja będzie odwrotnością innej, to iloczyn da nam element neutralny, który też może się powtarzać w wynikach. Tutaj znowu trzeba by zrobić analizę, czy któraś z permutacji jest odwrotnością innej, czy mamy element neutralny (a mamy) i co powychodzi z tych mnożeń. Trochę żmudna robota i nie wiem, czy to są wszystkie przypadki, które trzeba wziąć pod uwagę, czy są jeszcze jakieś jeszcze.

Zresztą 256 unikalnych wyników, to na oko coś za dużo jak na tak krótkie permutacje. Ostatecznie mamy do poprzestawiania tam tylko 6 liczb, w tym 2 parzyste i 4 nieparzyste. Czyli nieparzyste możemy ułożyć na 4! sposobów zaś parzyste na 2!. Następnie możemy je ze sobą zapisać na 4!*2! = 48 sposobów. Nie ma więc możliwości, żeby wyszło 256 różnych wyników. Wypisałem te 48 permutacji:

12345678

72543618

12347658

52743618

12543678

72345618

12547638

32745618

12743658

52347618

12745638

32547618

32145678

72541638

32147658

52741638

52143678

72341658

52147638

32741658

72143658

52341678

72145638

32541678

16345278

76543218

16347258

56743218

16543278

76345218

16547238

36745218

16743258

56347218

16745238

36547218

36145278

76541238

36147258

56741238

56143278

76341258

56147238

36741258

76143258

56341278

76145238

36541278

Tylko jedno mnie tutaj ciekawi. Czy da się wymnożyć permutację (1 2 3 4 7 6 5 8)? Mam takie podejrzenia, że tej i innych 7 permutacji z tego zbioru nie są się uzyskać z wyjściowych 8 permutacji, nieważne ile czynników będzie miał nasz iloczyn. A może nie da się uzyskać jeszcze wielu innych?

No i pozostaje pytanie o to jaka będzie częstotliwość poszczególnych permutacji wśród tych już uzyskanych? Mamy 512 wariacji iloczynów, natomiast co najwyżej 48 różnych permutacji do uzyskania (być może mniej). Docelowo chcę natomiast rozważać permutacje np. 1024-elementowe (i większe), w których podobnie liczby 2,4,8,16,... zawsze przechodzą same w siebie. Tutaj wariacje iloczynów 3-czynnikowych mogłyby być różnowartościowe, bowiem teoretycznie można stworzyć z tak długich permutacji wystarczająco wiele różnych wyników. Ale czy będą różnowartościowe? Jak to rozstrzygnąć?

[J.F.]

Dnia Wed, 18 Dec 2019 13:04:41 -0800 (PST), osobliwy nick napisał(a):
>> W jakim sensie "mnożyc" ? Bo na oko to mieszasz rozne pojecia.
> Chodzi o złożenie permutacji:
> (7 6 5 4 3 2 1 8) * (3 6 1 4 7 2 5 8) = (5 2 7 4 1 6 3 8)

Czyli wracajac do pytania:

> I zaczynam je mnożyć. Powiedzmy, że interesują mnie iloczyny
> 3-czynnikowe. Tworzę wszystkie wariacje z powtórzeniami. Będzie ich
> 8^3=512. Ile różnych permutacji otrzymam w wyniku? Jaka będzie ich
> częstotliwość i rozkład?

Jesli rozumiem - to wychodzisz od N-elementowych permutacji,
wybierasz M z nich, po czym sobie skladasz 3 z nich.

No coz, niewatpliwe moga powstac nowe permutacje, wykraczajace poza M.

Czy te M to wybrane jakos losowo ?

Zdaje sie, ze moze cie zainteresowac temat "Triple DES".

> Po pierwsze każda permutacja ma na czwartym miejscu 4, a na ostatnim 8, możemy zatem skrócić te permutacje (w celach obliczeniowych, później 4 i 8 trzeba zawsze dopisać), bo nowa wymnożona permutacja zawsze zachowa tę zasadę:

To jest o tyle istotne, ze teraz skrociles permutacje do 6
elementowych.
Jak wiadomo - takich permutacji jest 720, a Ty masz zlozen 512
mozliwych.

Jakies zblizone ilosci.

> 1 2 3 5 6 7
> 7 6 5 3 2 1
>
> 1 2 3 5 6 7
> 1 2 3 5 6 7
>
> 1 2 3 5 6 7
> 3 6 1 7 2 5
>
> 1 2 3 5 6 7
> 5 2 7 1 6 3
>
> 1 2 3 5 6 7
> 3 6 5 7 2 1
>
> 1 2 3 5 6 7
> 1 2 7 5 6 3
>
> 1 2 3 5 6 7
> 7 6 1 3 2 5
>
> 1 2 3 5 6 7
> 5 2 3 1 6 7
>
> Po drugie, każdy element parzysty daje liczbę parzystą, a nieparzysty - nieparzystą (nie wiem, czy to akurat wnosi, ale tak jest). Po trzecie jak widać każda permutacja ma swoje symetryczne odbicie. Oznacza to, że:
>
> a*sym(b) = sym(a)*b

Nie rozumiem o co Ci tu chodzi.

> Tylko jedno mnie tutaj ciekawi. Czy da się wymnożyć permutację
>(1 2 3 4 7 6 5 8)?

Jesli dobrze rozumiem twoj zapis - to to jest taka permutacja, ktora
nic nie permutuje - zostawia porzadek bez zmian.
To mozna ja skladac dowolna ilosc razy, i nic nie zmieni.

> Mam takie podejrzenia, że tej i innych 7 permutacji z
> tego zbioru nie są się uzyskać z wyjściowych 8 permutacji, nieważne
> ile czynników będzie miał nasz iloczyn. A może nie da się uzyskać
> jeszcze wielu innych?

Ten zbior to specjalnie dobrany, czy jakis losowy ?

Czy dobrze rozumiem pytanie - czy w wyniku zlozenia permutacji mozna
otrzymac tozsamosc (czyli brak permutacji) ?
Mozna.

> No i pozostaje pytanie o to jaka będzie częstotliwość poszczególnych permutacji wśród tych już uzyskanych?
> Mamy 512 wariacji iloczynów, natomiast co najwyżej 48 różnych
> permutacji do uzyskania (być może mniej).

A skad ta liczba 48 ?

J.

[osobliwy nick]

> Jesli rozumiem - to wychodzisz od N-elementowych permutacji,
> wybierasz M z nich, po czym sobie skladasz 3 z nich.

Tak. To przypadek na potrzeby przykładu. Docelowo interesuje mnie wybór dowolnej liczby różnych permutacji początkowych i ich składanie dowolną liczbę razy. Np. wybór 64 permutacji i obliczenie iloczynów 20-czynnikowych. Ile nowych permutacji z tego powstanie, jaki będzie ich rozkład (ile razy poszczególne wyniki będą się powtarzać). W szczególności, czy taka funkcja będzie równowartościowa?

> No coz, niewatpliwe moga powstac nowe permutacje, wykraczajace poza M.

Skąd to wiadomo?

> Czy te M to wybrane jakos losowo ?

Nie do końca. Tak naprawdę chodzi mi o konkretny przypadek pewnych struktur binarnych. Te struktury prawdopodobnie są grupą. Najprostszą (albo najbardziej zrozumiałą) z nich tworzą wypisane pionowo kolejne liczby naturalne w postaci binarnej, w kolumnach obok siebie. Tak to wygląda:

https://zapodaj.net/images/43ff2284da378.png

Uznajmy, że liczby w kratkach są nieistotne, nas interesują tylko czarne i białe kwadraty. Każdą kolumnę możemy odczytać jako liczbę binarną. Czarny kwadrat to jedynka, a biały to zero. Tak dostajemy permutację. Interesują mnie permutacje 2^n-elementowe, zaś liczby binarne odczytujemy na długości n (od góry do dołu, w każdej kolumnie). Możemy utworzyć w ten sposób również inne permutacje, wystarczy pozmieniać kolejność kwadratów:

https://zapodaj.net/images/2e923e8be6554.png

I tak jedynka daje tu liczbę 29, zaś na przykład liczba 10 daje liczbę 2. Struktury te mają pewne zasady tworzenia. Po pierwsze liczba nieparzysta zawsze daje zapis binarny liczby również nieparzystej, zaś liczba parzysta zawsze daje parzystą. Po drugie są one okresowe. Jak widać pierwszy wiersz ma okres 2, drugi 4, trzeci 8 itd. Po trzecie liczby postaci 2^n zawsze dają n białych kratek kolejno w kolumnie, a później kolejna po nich jest zawsze czarna (a potem kolejne mogą być już dowolne). Po czwarte w każdym wierszu na długości od 1 do 2^n kratek, musi występować połowa czarnych kwadratów i połowa białych. Tych zasad musimy przestrzegać przy tworzeniu tych struktur. No i po piąte muszą dawać one permutacje, to znaczy, że ostatni wiersz musimy dobrać tak, aby mieć komplet wszystkich możliwych wektorów binarnych. Poza tym możemy je generować wedle uznania, losowo. Nie wdawajmy się w to co stoi w miejscu kratek, bo to nieistotne z punktu widzenia tego akurat problemu (nie chciało mi się usuwać tych liczb).

Generując takie struktury możemy również stworzyć na ich podstawie permutacje i możemy je rozważać jako pewne szczególne permutacje. Każdą binarną kolumnę możemy zamienić na liczbę dziesiętną. Prawdopodobnie permutacja z takiej struktury, generowanej w ten szczególny sposób, pomnożona razy inną permutację z takiej struktury przechodzi w inną permutację, która zachowuje tę strukturę. Nie wiem jak to udowodnić i czy będzie tak zawsze. Przypuszczam, że tak. Myślę, iż można uznać, że te struktury to jest grupa, bo zachowuje wewnętrzność, łączność, ma element neutralny (jest nim akurat binarny zapis liczb naturalnych, który podałem jako przykład na początku), jest też spełniona odwracalność, chyba (bo każdą permutację można odwrócić).

> A skad ta liczba 48 ?

Tyle jest wszystkich możliwych permutacji 6-elementowych, takich, że każda liczba nieparzysta daje nieparzystą, a każda parzystą-parzystą. Tylko, że np. permutacja (1 2 3 4 7 6 5 8) nie zachowuje zasad tej struktury:

10101010
01100011
10010110

bo drugi wiersz nie jest okresowy. Dlatego sądzę, że nie da się tej permutacji wymnożyć. Ale nie mam dowodu, że te struktury zachowują wewnętrzność, gdy jest mnożymy ze sobą. Można natomiast oszacować ile takich n-wierszowych struktur możemy utworzyć (czyli permutacji 2^n-elementowych). Łatwo zauważyć, że pierwszy wiersz możemy ułożyć tylko na 1 sposób, nie możemy tam nic przestawić. Drugi wiersz możemy ułożyć na dwa sposoby. A trzeci? Ogólnie mamy w nim 8 miejsc, z których miejsce 4 zawsze wypełnia 1, zaś miejsce 8 wypełnia 0. Takie są zasady tworzenia tej struktury. Pozostaje zatem 6 miejsc, które możemy zapełnić trzema 1 i trzema 0. Można to zrobić na 6 po 3 sposobów, czyli 20. Ale to nie będzie aż tyle, będzie to mniej, bowiem nie możemy tego wiersza ułożyć dowolnie, struktura musi dawać permutację, a np. takie ułożenie nie tworzy permutacji:

10101010
01100011
00110110

Wydaje mi się, że zasady tych struktur są spełnione wtedy i tylko wtedy, gdy każdy kolejny wiersz układamy według następującego algorytmu. Dzielimy go na dwie części i druga część musi być przeciwieństwem pierwszej, na przykład w powyższym przypadku ostatni wiersz ma osiem elementów, pierwszą połowę możemy zapisać jako:

0101

wówczas druga połówka musi wyglądać tak:

1010

Jeśli podobnie jeśli pierwsza połowa wygląda tak 1101, to druga musi wyglądać tak 0010. Ta zasada zdaje się gwarantuje, że każdy nowo utworzony wiersz w tej strukturze da nam permutację, ale nie umiem tego udowodnić. Jeśli tak jest, to możemy oszacować liczbę takich unikalnych struktur 3-wierszowych, czyli permutacji 8-elementowych. Trzeci wiersz można wtedy bowiem ułożyć na 8 sposobów, zgodnie z tymi zasadami. Zatem ogólnie mamy 16 takich możliwych struktur 3-wierszowych. I teraz jeśli wychodzimy od 8 permutacji, które podałem:

1 2 3 4 5 6 7 8
7 6 5 4 3 2 1 8

1 2 3 4 5 6 7 8
3 6 1 4 7 2 5 8

1 2 3 4 5 6 7 9
3 6 5 4 7 2 1 8

1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8
5 2 7 4 1 6 3 8

1 2 3 4 5 6 7 8
1 2 7 4 5 6 3 8

1 2 3 4 5 6 7 8
7 6 1 4 3 2 5 8

1 2 3 4 5 6 7 8
5 2 3 4 1 6 7 8

Mamy szanse uzyskać pozostałe 8, przynajmniej teoretycznie, w ramach iloczynów 3-czynnikowych. Ale czy da się je wymnożyć?

Jeśli zaś wyjdziemy od powiedzmy permutacji 4-wierszowych, czyli 16-elementowych, takich możliwych struktur jest już 4064. Wychodząc od powiedzmy 64 początkowych permutacji i tworząc iloczyny powiedzmy też 3-elementowe, powinniśmy mieć większe prawdopodobieństwo wymnożenia jednej z nowych struktur, bo jest ich aż 4064. Ale czy tak będzie? Co więcej, jeśli chodzi o struktury np. 100-wierszowe mamy takich różnych struktur bardzo dużo, o wiele więcej niż iloczynów 3-czynnikowych. Możemy to policzyć ze wzoru na iloczyn sum symboli newtona jak poniżej. W każdym n-tym wierszu możemy ułożyć jedynki i zera na:

2 * [(2^(n-1)-1 po 2^(n-1)-1) + (2^(n-1)-1 po 2^(n-1)-1-1) + ... + (2^(n-1)-1 po 1)] = 2*suma_(i=3)^(2^(n-1)-2) (2^(n-1)-1 po 2^(n-1)-1-i)

sposobów. Przy czym wiersz pierwszy można ułożyć tylko na 1 sposób, zaś wiersz drugi na 2 sposoby, zatem sumę jest sens liczyć tylko dla i=3 i większych. Takich struktur n-wierszowych będzie więc:

2 * iloczyn_(k=3)^(n) 2*suma_(i=2)^(2^(k-1)-2) (2^(k-1)-1 po 2^(k-1)-1-i)

W sumie nie wiem jak to oszacować dla n=100, ale będzie to pewnie gdzieś liczba rzędu 2^100!. Każda taka wariacja iloczynu mogłaby być dawać różną permutację, bo jest ich wystarczająco wiele, ale nie wiem jak to rozstrzygnąć, nawet mając wypisane konkretne permutacje. Oczywiście permutacji 2^100 elementowych nie wypiszemy, ani nie przeanalizujemy w żadnym rozsądnym czasie. Ale może istnieją jakieś ogólne zasady, które można odnieść do dowolnych iloczynów lub na podstawie krótszych permutacji jakoś to rozstrzygnąć.

[J.F.]

Dnia Mon, 23 Dec 2019 11:12:41 -0800 (PST), osobliwy nick napisał(a):
>> Jesli rozumiem - to wychodzisz od N-elementowych permutacji,
>> wybierasz M z nich, po czym sobie skladasz 3 z nich.
>
> Tak. To przypadek na potrzeby przykładu. Docelowo interesuje mnie wybór dowolnej liczby różnych permutacji początkowych i ich składanie dowolną liczbę razy. Np. wybór 64 permutacji i obliczenie iloczynów 20-czynnikowych. Ile nowych permutacji z tego powstanie, jaki będzie ich rozkład (ile razy poszczególne wyniki będą się powtarzać). W szczególności, czy taka funkcja będzie równowartościowa?
>
>> No coz, niewatpliwe moga powstac nowe permutacje, wykraczajace poza M.
>
> Skąd to wiadomo?

Chocby z twojego przykladu - zlozyles dwie permutacje i wyszla
trzecia.

Wiec trzeba by starannie dobrac zbior M, aby sie okazalo, ze obejmuje
wszystkie zlozenia.
Hm, tak sie zastanawiam na ile to mozliwe ... trywialne przypadki tak,
ale nietrywialne ?

>> Czy te M to wybrane jakos losowo ?
>
> Nie do końca. Tak naprawdę chodzi mi o konkretny przypadek pewnych
> struktur binarnych. Te struktury prawdopodobnie są grupą.
> Najprostszą (albo najbardziej zrozumiałą) z nich tworzą wypisane
> pionowo kolejne liczby naturalne w postaci binarnej, w kolumnach
> obok siebie. Tak to wygląda:
>
> https://zapodaj.net/images/43ff2284da378.png
>
> Uznajmy, że liczby w kratkach są nieistotne, nas interesują tylko
> czarne i białe kwadraty. Każdą kolumnę możemy odczytać jako liczbę
> binarną. Czarny kwadrat to jedynka, a biały to zero. Tak dostajemy
> permutację. Interesują mnie permutacje 2^n-elementowe, zaś liczby
> binarne odczytujemy na długości n (od góry do dołu, w każdej
> kolumnie). Możemy utworzyć w ten sposób również inne permutacje,
> wystarczy pozmieniać kolejność kwadratów:

Nie rozumiem jak to ma dzialac.
Jak przeliczasz liczbe binarna na permutacje ?

Mowisz o parzystosci numerow elementow ?

To jesli dobrze rozumiem, aby miec taka wlasciwosc, to de facto
potrzebujemy dwoch permutacji - osobno na elementy parzyste, osobno na
nieparzyste.
Co przy 6 elementach daje dwie trzyelementowe, i razem (3!)^2=36
kombinacji.

J.

[osobliwy nick]

> >> No coz, niewatpliwe moga powstac nowe permutacje, wykraczajace poza M.
> >
> > Skąd to wiadomo?
>
> Chocby z twojego przykladu - zlozyles dwie permutacje i wyszla
> trzecia.

Wyszła trzecia, ale to nie jest nowa permutacja:

(7 6 5 4 3 2 1 8) * (3 6 1 4 7 2 5 8) = (5 2 7 4 1 6 3 8)

To jest jedna z wypisanych przeze mnie 8 permutacji:

1 2 3 4 5 6 7 8
5 2 7 4 1 6 3 8

> Nie rozumiem jak to ma dzialac.
> Jak przeliczasz liczbe binarna na permutacje ?

To jest przykładowa struktura binarna:

10101010
11001100
01011010

Zawsze musi mieć rozmiary 2^n długości i n wysokości (plus okresowość wierszy, poza ostatnim wierszem i wyjątki dla kolumn o numerach 2^i, ponadto pierwszy wiersz w każdej strukturze jest zawsze identyczny i zawsze jest to 101010... itd.). Dla porządku powinniśmy taką strukturę zapisać tak:

01010101
01100110
00101101

czyli przesunąć ostatnią kolumnę z samymi zerami na początek i ponumerować kolejno kolumny od 0 do 7. Wówczas pierwszą kolumnę możemy odczytać jako 0, kolejną jako 1*2^0+1*2^1+0*2^2 = 3. Następna kolumna to 0*2^0+1*2^1+1*2^2 = 6. Możemy więc ponumerować kolumny:

0 1 2 3 4 5 6 7

i przypisać każdej z nich liczby:

0 3 6 1 4 7 2 5

Żeby nie numerować od 0 i nie mieć 0 w permutacji przestawiałem pierwszy wiersza zawsze złożony z 0 na koniec i podmieniałem 0 na liczbę 8. Wówczas możemy rozważać strukturę:

10101010
11001100
01011010

i numerować kolumny od 1 do 8, tylko trzeba pamiętać, żeby ostatnią kolumnę odczytać jako 8, a nie 0.

> Mowisz o parzystosci numerow elementow ?

Tak. W tej permutacji:

0 1 2 3 4 5 6 7
0 3 6 1 4 7 2 5

każda liczba parzysta daje również parzystą. I dla wszystkich możliwych struktur tak będzie, bo pierwszy wiersz jest zdefiniowany jako 0101010101..., gdy numerujemy od 0.

> To jesli dobrze rozumiem, aby miec taka wlasciwosc, to de facto
> potrzebujemy dwoch permutacji - osobno na elementy parzyste, osobno na
> nieparzyste.
> Co przy 6 elementach daje dwie trzyelementowe, i razem (3!)^2=36
> kombinacji.

Każda permutacja stworzona na podstawie tej struktury będzie miała kolumnę, w której 0 przechodzi w 0 oraz 4 przechodzi w 4:

0 1 2 3 4 5 6 7
0 3 6 1 4 7 2 5

więc możemy je usunąć:

1 2 3 5 6 7
3 6 1 7 2 5

Teraz możemy wziąć elementy parzyste:

2 6
6 2

oraz nieparzyste:

1 3 5 7
3 1 7 5

I dla każdej możliwej permutacji 2-elementowej przypisać jedną z permutacji 4-elementowych. Można to zrobić na 2! * 4! = 48 sposobów. Nie będą to dwie 3-elementowe permutacje, tylko jedna 2-elementowa i jedna 4-elementowa.

Tyle, że 48 sposobów to za dużo, bo w ramach tych kombinacji wychodzi nam na przykład taka permutacja:

0 1 2 3 4 5 6 7
0 1 2 3 4 7 6 5

Co daje taką strukturę:

01010101
00110110
00001111

Drugi wiersz w tej strukturze nie jest okresowy, a powinien być, jeśli dobrze mi się wydaje, że mnożenie tych struktur nie daje wyników innych niż te struktury. Jeśli rzeczywiście mnożenie tych struktur zachowuje wewnętrzność, to możemy takich struktur 8-elementowych utworzyć maksymalnie 16, bo na przykład takie struktury jak ta powyżej nie mogą się pojawić. Ale nie wiem, czy mnożenie tych struktur zachowuje wewnętrzność, tylko tak podejrzewam.

[J.F.]

Dnia Thu, 26 Dec 2019 04:37:52 -0800 (PST), osobliwy nick napisał(a):
>>>> No coz, niewatpliwe moga powstac nowe permutacje, wykraczajace poza M.
>>> Skąd to wiadomo?
>>
>> Chocby z twojego przykladu - zlozyles dwie permutacje i wyszla
>> trzecia.
>
> Wyszła trzecia, ale to nie jest nowa permutacja:
>
> (7 6 5 4 3 2 1 8) * (3 6 1 4 7 2 5 8) = (5 2 7 4 1 6 3 8)
>
> To jest jedna z wypisanych przeze mnie 8 permutacji:

Tak czy inaczej - wyszla trzecia, wiec teraz masz problem co musi
wejsc do grupy.

Cos mi sie przypomnialo z kostki Rubika - sa takie permutacje, ze
zlozenie trzech przywraca stan poczatkowy.

>> Nie rozumiem jak to ma dzialac.
>> Jak przeliczasz liczbe binarna na permutacje ?
>
> To jest przykładowa struktura binarna:
>
> 10101010
> 11001100
> 01011010

Dwa pierwsze wiersze jasne, ale trzeci ... skad sie wzial akurat taki?

> Zawsze musi mieć rozmiary 2^n długości i n wysokości (plus okresowość wierszy, poza ostatnim wierszem i wyjątki dla kolumn o numerach 2^i, ponadto pierwszy wiersz w każdej strukturze jest zawsze identyczny i zawsze jest to 101010... itd.).

> Dla porządku powinniśmy taką strukturę zapisać tak:
>
> 01010101
> 01100110
> 00101101
>
> czyli przesunąć ostatnią kolumnę z samymi zerami na początek

IMO - niepotrzebne komplikacje

>i ponumerować kolejno kolumny od 0 do 7.
>Wówczas pierwszą kolumnę możemy odczytać jako 0, kolejną jako 1*2^0+1*2^1+0*2^2 = 3. Następna kolumna to 0*2^0+1*2^1+1*2^2 = 6.
>Możemy więc ponumerować kolumny:
> 0 1 2 3 4 5 6 7
> i przypisać każdej z nich liczby:
> 0 3 6 1 4 7 2 5

Rozumiem, ze to ma tez byc nr pozycji po permutacji.

> Żeby nie numerować od 0 i nie mieć 0 w permutacji przestawiałem
> pierwszy wiersza zawsze złożony z 0 na koniec i podmieniałem 0 na
> liczbę 8. Wówczas możemy rozważać strukturę:

IMO - tez niepotrzebna komplikacja.

I to o okresie akurat 4, tak jak drugi wiersz ?
Ale przeciez w twoim pierwszym przykladzie trzeci wiersz nie ma
takiego okresu.

> jeśli dobrze mi się wydaje, że mnożenie tych struktur nie daje
> wyników innych niż te struktury.

Gubie sie w tych Twoich modyfikacjach, ale jesli tu jest zachowana
pozycja 4 i 8, to nadal mamy jedna z 48 permutacji.

> Jeśli rzeczywiście mnożenie tych
> struktur zachowuje wewnętrzność, to możemy takich struktur
> 8-elementowych utworzyć maksymalnie 16, bo na przykład takie
> struktury jak ta powyżej nie mogą się pojawić. Ale nie wiem, czy
> mnożenie tych struktur zachowuje wewnętrzność, tylko tak
> podejrzewam.

No wlasnie - z ograniczeniami mamy 48 mozliwych permutacji.
A ja tu zobaczylem na razie sposob na generacje jednej.

Pierwszy wiersz ma zawsze postac 10101010 ?
A drugi 11001100 czy moze byc inaczej ?
4 mozliwosci, jesli bedziemy go przesuwac.

a co z trzecim wierszem ?
Bo znow - jesli ma miec pewne wlasciwosci, to ograniczasz ilosc
mozliwosci, i w efekcie koncowym ilosc roznowartosciowych permutacji
jest ograniczona. A 48 to akurat tyle, ze nie pasuje do 2^k.

A do czego w ogole zmierzasz ?
Do udowodnienia, ze pewne struktury binarne, po zmianie na permutacje
powyzsza metoda, generuja grupe ?

J.

[osobliwy nick]

> Tak czy inaczej - wyszla trzecia, wiec teraz masz problem co musi
> wejsc do grupy.

Wychodzę od permutacji:

0 1 2 3 4 5 6 7

0 7 6 5 4 3 2 1

0 1 2 3 4 5 6 7
0 3 6 1 4 7 2 5

0 1 2 3 4 5 6 7

0 3 6 5 4 7 2 1

0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7
0 5 2 7 4 1 6 3

0 1 2 3 4 5 6 7

0 1 2 7 4 5 6 3

0 1 2 3 4 5 6 7

0 7 6 1 4 3 2 5

0 1 2 3 4 5 6 7

0 5 2 3 4 1 6 7

A dostaję w wyniku mnożenia permutację:

(0 7 6 5 4 3 2 1) * (0 3 6 1 4 7 2 5) = (0 5 2 7 4 1 6 3)

To nie jest żadna nowa permutacja, ponad te które mam wypisane. Zachowuje ona też strukturę binarną, zgodną z zasadami, które opisałem. A ja chcę wiedzieć, czy można wymnożyć dwie lub trzy permutacje ze sobą tak, że otrzymać jakieś inne wyniki niż te wypisane, od których wychodzę.

> > To jest przykładowa struktura binarna:
> >
> > 10101010
> > 11001100
> > 01011010
>
> Dwa pierwsze wiersze jasne, ale trzeci ... skad sie wzial akurat taki?

Trzeci możemy utworzyć dowolnie. Musimy tylko pamiętać o tym, że:
- pierwsza pozycja musi wynosić zero,
- musimy go dopisać w taki sposób, aby w kolejnych kolumnach mieć wszystkie kombinacje wektorów zero-jedynkowych, czyli tak, aby mieć permutację (możemy to zrobić na wiele sposobów, a dokładniej - prawdopodobnie trzeci wiersz można dopisać zawsze na 8 sposobów).

Jeśli mamy rozważać permutacje z kolumną ze na początku, musimy ją przepisać tak:

01010101
01100110
00101101

> IMO - niepotrzebne komplikacje

Ok. Czyli pozostańmy przy numerowaniu tych permutacji od 0 do 2^n-1. Wówczas pierwsza kolumna zawsze, z definicji musi się składać z samych zer.

> Rozumiem, ze to ma tez byc nr pozycji po permutacji.

Tak. Przykładowo permutację:

01010101
01100110
00101101

Numerujemy od 0 do 7. Wyniesie ona:

0 1 2 3 4 5 6 7
0 3 6 1 4 7 2 5

> > 01010101
> > 00110110
> > 00001111
> >
> > Drugi wiersz w tej strukturze nie jest okresowy, a powinien być,
>
> I to o okresie akurat 4, tak jak drugi wiersz ?
> Ale przeciez w twoim pierwszym przykladzie trzeci wiersz nie ma
> takiego okresu.

W każdej strukturze pierwszy wiersz ma okres 2 i zawsze wygląda tak samo: 010101... Drugi wiersz ma okres 4, przy czym na pierszym miejscu musi stać zawsze zero, na miejscu liczby porządkowej 2 musi stać 1, więc może on wyglądać na poniższe dwa sposoby:
- 0110, zaś później jest okresowy 011001100110...,
- 0011, zaś później jest okresowy 001100110011....

Inaczej nie da się ułożyć drugiego wiersza, ze względu na ograniczenia. Pierwsze zawsze musi być 0. Zaś na miejscu trzeciego bitu musi stać 1. Z kolei w wierszu trzecim podobnie pierwsze musi być 0, zaś na miejscu piątego bitu musi stać 1 (przy czym piąty bit ma liczbę porządkową w permutacji 4, bo numerujemy od 0). Trzeci wiersze będzie miał okres 8, więc, jeśli rozważamy struktury tylko do trzeciego wiersza, tj. 8-elementowe nie zobaczymy jego okresowości. Dopiero, gdy będziemy generować strukturę 16-elementową, to trzeci wiersz będziesz się powtarzał.

> No wlasnie - z ograniczeniami mamy 48 mozliwych permutacji.
> A ja tu zobaczylem na razie sposob na generacje jednej.

Według moich ustaleń takich struktur można wygenerować maks. 16, nie 48.

> Pierwszy wiersz ma zawsze postac 10101010 ?

Tak. Przy czym, jeśli umawiamy się na numerowanie od zera, to ma mieć postać 010101...

> A drugi 11001100 czy moze byc inaczej ?

Może być inaczej, tak jak wyjaśniłem powyżej.

> a co z trzecim wierszem ?

Tak jak powyżej, mam nadzieję, że będzie to jasne.

> A do czego w ogole zmierzasz ?
> Do udowodnienia, ze pewne struktury binarne, po zmianie na permutacje
> powyzsza metoda, generuja grupe ?

Chcę rozważać tego rodzaju struktury dla dużej liczby wiersz i kolumn. Np. 10-wierszowe, czyli posiadające 2^10=1024 kolumn. Interesuje mnie zagadnienie mnożenia tych struktur. Chcę wybrać arbitralnie powiedzmy zbiór 10 takich struktur i zacząć je mnożyć ze sobą. Powiedzmy wygenerować wszystkie wariacje z powtórzeniami iloczynów 4-elementowych. I chcę wiedzieć, czy takie iloczyny będą dawały nowe permutacje, jeśli tak to ile nowych permutacji ponad zbiór, z którego wychodzę wygeneruję? Jaki będzie rozkład wyników? Załóżmy, że wynikiem będzie jakichś 100 unikalnych permutacji. Ile razy uzyskam permutację pierwszą, ile razy drugą itd.?

Żeby to rozstrzygnąć trzeba wiedzieć, czy mnożenie tych struktur jest wewnętrzne, bo to chociaż zawęża maksymalny zbiór możliwości. Nie interesuje mnie tak do końca, czy te struktury są grupą, chcę się dowiedzieć czegoś o dystrybucji wyników. W przypadku mnożenia dużych struktur, nawet, jeśli rozpatrzymy 10-elementowe wariacje z powtórzeniami, funkcja przyjmująca jako argumenty kolejne iloczyny tych permutacji, a zwracająca jako wartość wynik mnożenia tych permutacji - ma szanse być różnowartościowa. Przynajmniej teoretycznie, bo liczba wariacji z powtórzeniami będzie o wiele mniejsza, niż liczba możliwych struktur do wygenerowania. Ale czy będzie różnowartościowa? Czy można się czegoś spodziewać bardziej lub mniej? Czy raczej większość wymnożonych struktur będzie kompletnie nowa i unikalna, czy może będziemy wciąż wymnażać te same permutacje, w szczególności te, z których tworzymy iloczyny?

[J.F.]

Dnia Thu, 26 Dec 2019 12:44:44 -0800 (PST), osobliwy nick napisał(a):
>> Tak czy inaczej - wyszla trzecia, wiec teraz masz problem co musi
>> wejsc do grupy.
>
> Wychodzę od permutacji:
>
> 0 1 2 3 4 5 6 7

pozwole sobie posortowac i ponumerowac

> 0 7 6 5 4 3 2 1 p1
> 0 3 6 5 4 7 2 1 p2
> 0 7 6 1 4 3 2 5 p3
> 0 3 6 1 4 7 2 5 p4
> 0 1 2 3 4 5 6 7 p5
> 0 1 2 7 4 5 6 3 p6
> 0 5 2 7 4 1 6 3 p7
> 0 5 2 3 4 1 6 7 p8

> A dostaję w wyniku mnożenia permutację:
>
> (0 7 6 5 4 3 2 1) * (0 3 6 1 4 7 2 5) = (0 5 2 7 4 1 6 3)

> To nie jest żadna nowa permutacja, ponad te które mam wypisane.
> Zachowuje ona też strukturę binarną, zgodną z zasadami, które
> opisałem. A ja chcę wiedzieć, czy można wymnożyć dwie lub trzy
> permutacje ze sobą tak, że otrzymać jakieś inne wyniki niż te
> wypisane, od których wychodzę.

p1 do p4 zamieniaja elementy 2 i 6, pozostale nie.
p7 i p8 zamieniaja 5 i 1.

Jakbys tak jeszcze zamienil tylko inne dwa elementy,
to by wyszlo dzalanie wewnetrzne.

ale p1 do p4 wprowadzaja wiecej zamieszania - nazwalbym to obrotem
1, 3, 5, 7. Akurat po dwoch obrotach element 2 6 wroca na swoje
miejsca.

Nie chce mi sie dokladnie sprawdzac, ale wyglada na wewnetrzne.

Tylko ... czy to take odkrywcze ?
z 8! mozliwych permutacji wybrales 8 tworzacych grupe, i to jeszcze
takie, ktore maja dwa elementy stale ...

>>> To jest przykładowa struktura binarna:
>>> 10101010
>>> 11001100
>>> 01011010
>>
>> Dwa pierwsze wiersze jasne, ale trzeci ... skad sie wzial akurat taki?
>
> Trzeci możemy utworzyć dowolnie. Musimy tylko pamiętać o tym, że:
> - pierwsza pozycja musi wynosić zero,
> - musimy go dopisać w taki sposób, aby w kolejnych kolumnach mieć
> wszystkie kombinacje wektorów zero-jedynkowych, czyli tak, aby mieć
> permutację (możemy to zrobić na wiele sposobów, a dokładniej -
> prawdopodobnie trzeci wiersz można dopisać zawsze na 8 sposobów).

to 00001111 jest dopuszczalny.

Bo nakladasz jakies dziwne ograniczenia.
Jesli dwa elementy maja nie permutowac, to zostaje 6 - i 6! mozliwych
permutacji.
Jesli podzielimy dalej na grupy 2 i 4-ro elementowe, to mamy
odpowiednio 2! i 4! permutacji.
Razem 48 - tylko moze nie pasowac do innych twoich ograniczen.

>> A do czego w ogole zmierzasz ?
>> Do udowodnienia, ze pewne struktury binarne, po zmianie na permutacje
>> powyzsza metoda, generuja grupe ?
>
> Chcę rozważać tego rodzaju struktury dla dużej liczby wiersz i
> kolumn. Np. 10-wierszowe, czyli posiadające 2^10=1024 kolumn.
> Interesuje mnie zagadnienie mnożenia tych struktur. Chcę wybrać
> arbitralnie powiedzmy zbiór 10 takich struktur i zacząć je mnożyć
> ze sobą. Powiedzmy wygenerować wszystkie wariacje z powtórzeniami
> iloczynów 4-elementowych. I chcę wiedzieć, czy takie iloczyny będą
> dawały nowe permutacje, jeśli tak to ile nowych permutacji ponad
> zbiór, z którego wychodzę wygeneruję? Jaki będzie rozkład wyników?
> Załóżmy, że wynikiem będzie jakichś 100 unikalnych permutacji. Ile
> razy uzyskam permutację pierwszą, ile razy drugą itd.?
>
> Żeby to rozstrzygnąć trzeba wiedzieć, czy mnożenie tych struktur
> jest wewnętrzne, bo to chociaż zawęża maksymalny zbiór możliwości.
> Nie interesuje mnie tak do końca, czy te struktury są grupą, chcę
> się dowiedzieć czegoś o dystrybucji wyników.

IMO - jakies dziwne pytania.

Widac, ze to zlozenie moze dac inna permutacje.
Wiec kwestia jest taka, czy dobierzesz dobry zestaw.
A zestaw moze byc 2 elementowy(permutacyjny), 3, 4 ... i n!.
Ciekawe, czy sa jakies licznosci wykluczone.

Chyba, ze nalozysz jakies dziwne ograniczenia na te ciagi binarne,
np to ze najmlodszy bit musi byc 01010101 ...

J.

[osobliwy nick]

> to 00001111 jest dopuszczalny.

Tak, jeśli umawiamy się, że kolumna z zerami będzie stała na samym początku i numerujemy od zera.

> Bo nakladasz jakies dziwne ograniczenia.
> Jesli dwa elementy maja nie permutowac, to zostaje 6 - i 6! mozliwych
> permutacji.
> Jesli podzielimy dalej na grupy 2 i 4-ro elementowe, to mamy
> odpowiednio 2! i 4! permutacji.
> Razem 48 - tylko moze nie pasowac do innych twoich ograniczen.

Wcześniej pomyliłem się w jednej sprawie, stąd wzory w moich poprzednich postach były błędne w jednym punkcie i nadmiernie skomplikowane. Ogólnie każdy nowy wiersz można ułożyć na 2^(2^(k-1)-1) sposobów. Pierwszy wiersz można ułożyć tylko na jeden sposób. Drugi wiersz może wyglądać tak 0011 lub tak 0110. Natomiast kolejny wiersz musi mieć na pierwszym miejscu 0, na miejscu piątego bitu 1, zaś reszta może być ułożona dowolnie: 0xxx1xxx. Tyle tylko, że, aby otrzymać wszystkie kombinacje wektorów zero-jedynkowych (a musimy to zrobić, żeby mieć permutację) w naszych 8 kolumnach, to pierwsza połowa 0xxx musi być przeciwieństwem drugiej 1xxx. Jednocześnie musi mieć w całym wierszu cztery jedynki i cztery zera. Zatem jeśli pierwsza połowa wygląda tak 0000, to druga musi być 1111, zaś cały wiersz musi wyglądać tak 00001111. Mamy zatem dowolność w wypełnieniu tylko trzech miejsc w pierwszej połowie wiersza. Możemy tam wstawić same 1, same 0 lub dowolne wektory złożone z jednej jedynki lub dwóch jedynek. Liczbę 1, mając do dyspozycji 3 miejsca możemy ułożyć na 3 po 1 sposobów, zaś dwie 1 możemy ułożyć na 3 po 2 sposobów. W sumie daje to 8 sposobów:

000
100
010
001
110
011
101
111

W kolejnym wierszu mamy podobny problem 0xxxxxxx1xxxxxxx. Trzeba tu zatem sumować 7 po 7, 7 po 6, ..., 7 po 1, 7 po 0. Taka suma, to suma elementów w n-tym wierszu trójkąta Pascala. Liczba możliwości będzie wynosić 2^(2^(k-1)-1), jeśli za k przyjmiemy k-ty wiersz w takiej strukturze.

> >> A do czego w ogole zmierzasz ?
> >> Do udowodnienia, ze pewne struktury binarne, po zmianie na permutacje
> >> powyzsza metoda, generuja grupe ?
> >
> > Chcę rozważać tego rodzaju struktury dla dużej liczby wiersz i
> > kolumn. Np. 10-wierszowe, czyli posiadające 2^10=1024 kolumn.
> > Interesuje mnie zagadnienie mnożenia tych struktur. Chcę wybrać
> > arbitralnie powiedzmy zbiór 10 takich struktur i zacząć je mnożyć
> > ze sobą. Powiedzmy wygenerować wszystkie wariacje z powtórzeniami
> > iloczynów 4-elementowych. I chcę wiedzieć, czy takie iloczyny będą
> > dawały nowe permutacje, jeśli tak to ile nowych permutacji ponad
> > zbiór, z którego wychodzę wygeneruję? Jaki będzie rozkład wyników?
> > Załóżmy, że wynikiem będzie jakichś 100 unikalnych permutacji. Ile
> > razy uzyskam permutację pierwszą, ile razy drugą itd.?
> >
> > Żeby to rozstrzygnąć trzeba wiedzieć, czy mnożenie tych struktur
> > jest wewnętrzne, bo to chociaż zawęża maksymalny zbiór możliwości.
> > Nie interesuje mnie tak do końca, czy te struktury są grupą, chcę
> > się dowiedzieć czegoś o dystrybucji wyników.
>
> IMO - jakies dziwne pytania.

W sumie widzę, że to do niczego nie prowadzi. Tym bardziej, że chcę rozważać iloczyny takich struktur powiedzmy 128-wierszowe. To tak jakby mnożyć permutacje 2^128-elementowe. Takich permutacji nie da się po prostu wypisać (z tego co liczyłem nie zmieściłyby się nawet na wszystkich komputerach świata), przeanalizować, ocenić ile unikalnych wyników dadzą. Wydaje mi się, że istnieją jednak jakieś minimalne ograniczenia. Tzn., że, jeśli bierzemy kompletnie losowo np. 50 takich struktur 100-wierszowych i tworzymy iloczyny 10-elementowe, to musi powstać minimum ileś tam nowych struktur/permutacji (nowych, czyli innych niż te 50 wyjściowych struktur). Ale to zagadnienie wydaje się być poza zasięgiem, a nawet nie wiem, czy nie poza zasięgiem obecnie znanych metod.

Dodam może tylko na koniec skąd się biorą te struktury. Struktura dotycząca kolejnych liczb naturalnych jest wynikiem po prostu zapisania ich binarnie. I ma swój prosty rekurencyjny algorytm:
a) jeśli x jest nieparzyste, to x*0,5-0,5,
b) jeśli x jest parzyste, to x/2.

Generując takie ciągi możemy zapisać każdą liczbę binarnie. Np. liczba pięć daje ciąg: 2, 1, 0. Wystarczy zamienić teraz te liczby, które powstały wskutek operacji a) na 1, zaś te które powstały wskutek operacji b) na 0. I mamy 101, zapis binarny liczby 5. To znany, elementarny algorytm zamiany liczb z systemu dziesiętnego na binarny. Rzecz w tym, że dokładnie to samo możemy zrobić np. dla funkcji zdefiniowanej tak:
- jeśli x jest nieprzyste, to x*1,5+0,5,
- jeśli x jest parzyste, to x/2.

I to akurat jest słynny ciąg Collatza. Generuje on strukturę binarną zupełnie inną niż liczby naturalne zapisane binarnie, ale spełnia ona wszystkie zasady struktur, o których pisałem. Możemy wymyślić dowolną funkcję typu x*a/2+b/2 i będzie ona generować jakąś tego rodzaju strukturę binarną. Same te struktury są mocno nietrywialne, tj. wyglądają i zachowują się dosyć chaotycznie. Jeszcze trudniejsze do przewidzenia są wyniki złożeń tych funkcji. Chcę mnożyć te struktury, które możemy wyznaczyć za pomocą takich właśnie rekurencyjnych funkcji.

Zasady generowania tych struktur nie są więc moim wymysłem, tylko właściwością tych funkcji. Ale widzę, że to podejście do niczego nie prowadzi. Żeby ocenić dystrybucję i częstotliwość różnych wyników trzeba temat ugryźć jakoś inaczej.

Wszystkie z tych struktur wydają się być fraktalami (choć nie wiem jak to formalnie wykazać), samopodobnymi w zakresie od 1 do 2^n, tak jak liczby naturalne zapisanie binarnie (widać to na oko w przypadku zapisu binarnego liczb naturalnych). Można udowodnić, że każda taka funkcja daje unikalną strukturę w danym zakresie, stąd ich złożenia też powinny być teoretycznie unikalne w tym zakresie.

Problem rozwiązałaby jedna rzecz. Umiejętność mnożenia tych struktur mając do dyspozycji tylko parametr a i b. Na przykład składamy strukturę funkcji 3/2*x+1/2 oraz 5/2*x+7/2 dla permutacji np. 8-elementowej. Możemy zatem zapisać mnożenie tak:

(3,1) * (5,7) mod 8 = ?

Przy czym mod 8 ma oznaczać, że generujemy strukturę dla 8 elementów, czyli każda kolumna będzie miała 3 bity. Dokładnie o takie struktury chodzi:

https://zapodaj.net/images/e8e26607fa0b8.jpg

https://zapodaj.net/images/954ed40d02b60.jpg

Nie mogę jednak zrozumieć zasad mnożenia tych struktur na tym skrótowym poziomie. I nie wiem, czy w ogóle istnieją takie zasady. Nie wszystkie iloczyny będą w ogóle zdefiniowane, to znaczy, że mogą nie istnieć takie 2 liczby (a,b), które dadzą rozwiązanie. Muszę sam popracować nad tym problemem, bo wydaje się, że w matematyce gotowych rozwiązań na to nie ma.

[J.F.]

Użytkownik "osobliwy nick" napisał w wiadomości grup
dyskusyjnych:52fb4a69-3dc6-4be0...@googlegroups.com...

W dniu piątek, 27 grudnia 2019 01:01:02 UTC+1 użytkownik J.F. napisał:
> Dnia Thu, 26 Dec 2019 12:44:44 -0800 (PST), osobliwy nick
> napisał(a):

[...]

>> Nie chce mi sie dokladnie sprawdzac, ale wyglada na wewnetrzne.

>> Bo nakladasz jakies dziwne ograniczenia.
>> Jesli dwa elementy maja nie permutowac, to zostaje 6 - i 6!
>> mozliwych
>> permutacji.
>> Jesli podzielimy dalej na grupy 2 i 4-ro elementowe, to mamy
>> odpowiednio 2! i 4! permutacji.
>> Razem 48 - tylko moze nie pasowac do innych twoich ograniczen.

>Wcześniej pomyliłem się w jednej sprawie, stąd wzory w moich
>poprzednich postach były błędne w jednym punkcie i nadmiernie
>skomplikowane.
>Ogólnie każdy nowy wiersz można ułożyć na 2^(2^(k-1)-1) sposobów.
>Pierwszy wiersz można ułożyć tylko na jeden sposób.

Pamietasz kod Graya ? pierwszy wiersz/najmlodszy bit moze wygladac
0110011001100...

Jak to pasuje do Twoich permutacji to nie wiem.

>> >> A do czego w ogole zmierzasz ?
>> >> Do udowodnienia, ze pewne struktury binarne, po zmianie na
>> >> permutacje
>> >> powyzsza metoda, generuja grupe ?
> >
>> > Chcę rozważać tego rodzaju struktury dla dużej liczby wiersz i
>> > kolumn. Np. 10-wierszowe, czyli posiadające 2^10=1024 kolumn.
>> > Interesuje mnie zagadnienie mnożenia tych struktur. Chcę wybrać
>> > arbitralnie powiedzmy zbiór 10 takich struktur i zacząć je mnożyć
>> > ze sobą. Powiedzmy wygenerować wszystkie wariacje z powtórzeniami
>> > iloczynów 4-elementowych. I chcę wiedzieć, czy takie iloczyny
>> > będą
>> > dawały nowe permutacje, jeśli tak to ile nowych permutacji ponad
>> > zbiór, z którego wychodzę wygeneruję? Jaki będzie rozkład
>> > wyników?
>> > Załóżmy, że wynikiem będzie jakichś 100 unikalnych permutacji.
>> > Ile
>> > razy uzyskam permutację pierwszą, ile razy drugą itd.?
> >

>> IMO - jakies dziwne pytania.

>W sumie widzę, że to do niczego nie prowadzi.
>Tym bardziej, że chcę rozważać iloczyny takich struktur powiedzmy
>128-wierszowe.

Czyli liczby 128 bitowe, czy 128 wybranych pemutacji ?

>To tak jakby mnożyć permutacje 2^128-elementowe.
>Takich permutacji nie da się po prostu wypisać (z tego co liczyłem
>nie zmieściłyby się nawet na wszystkich komputerach świata),
>przeanalizować, ocenić ile unikalnych wyników dadzą.

A ile tych permutacji chcesz wybrac ? 128 to jeszcze idzie
przeanalizowac ktore sie powtarzaja .

No nie calkiem - ciagi sa zmiennej dlugosci. Liczby na kolejnych
etapach moga byc znacznie wieksze niz poczatkowa.
Jak chcesz to zamienic potem na permutacje ?

Nadal nie rozumiem, do czego zmierzasz, czy co chcesz osiagnac.
Jesli wychodzimy od N bitow, to bity moga kodowac liczby od 0 do
2^N-1.

Ktore z tych liczb chcesz wybrac do swojego podzbioru ?

>Nie mogę jednak zrozumieć zasad mnożenia tych struktur na tym
>skrótowym poziomie. I nie wiem, czy w ogóle istnieją takie zasady.

Ja tam na razie widze, ze M-elementowych permutacji jest mozliwych M!,
i mozesz z nich wybrac podzbior w ktorym zlozenie permutacji bedzie
wewnetrzne:
2-elementowy, 3 elementowy, k-elementowy - gdzie k<=M,
M! elementowy, (M-1)!, i cala masa innych licznosci.

Ciekawe, czy sa jakies licznosci, dla ktorych nie mozna stworzyc
zamknietego podzbioru.

Oczywiscie stwierdzenie "mozna wybrac", nie oznacza, ze losowo wybrany
podzbior bedzie mial taka wlasciwosc.


J.

[osobliwy nick]

> Pamietasz kod Graya ? pierwszy wiersz/najmlodszy bit moze wygladac
> 0110011001100...
>
> Jak to pasuje do Twoich permutacji to nie wiem.

Też nie wiem, ale na pierwszy rzut oka nie widzę raczej związków.

> >W sumie widzę, że to do niczego nie prowadzi.
> >Tym bardziej, że chcę rozważać iloczyny takich struktur powiedzmy
> >128-wierszowe.
>
> Czyli liczby 128 bitowe, czy 128 wybranych pemutacji ?

Liczby 128-bitowe. Każda liczba od 0 do 2^128-1 ma mieć przypisaną jakąś liczbę 128-bitową.

> A ile tych permutacji chcesz wybrac ? 128 to jeszcze idzie
> przeanalizowac ktore sie powtarzaja .

64. Ale permutacji liczącej 2^128 elementów nie przeanalizujesz. Z 64 takich permutacji chcę utworzyć powiedzmy iloczyny 20-czynnikowe. To jest 2^120 wariacji z powtórzeniami iloczynów. Zaś każda permutacja liczy 2^128 elementów. Przemnożenie tylko dwóch takich permutacji może zająć miliardy lat, a co dopiero powyliczanie wszystkich wariacji 20-czynnikowych. Poza tym nawet, jeśli każdą liczbę 128-bitową w jakiś cudowny sposób uprościlibyśmy tak, że zajmowałaby 1 bajt, to wciąż potrzeba nam 2^128/(100*10^12) = 3.4028237e+24 dysków SSD 100-terabajtowych. Na Ziemi nie ma tylu ziarenek piasku, a co dopiero takich dysków.

Dlatego nie da się tego ustalić dla tak dużych liczb obliczeniowo. Trzeba to jakoś oszacować (o ile oszacować się da, to też nie jest jasne).

> >Generując takie ciągi możemy zapisać każdą liczbę binarnie.
> >Np. liczba pięć daje ciąg: 2, 1, 0. Wystarczy zamienić teraz te
> >liczby, które powstały wskutek operacji a) na 1, zaś te które
> >powstały wskutek operacji b) na 0.
> >I mamy 101, zapis binarny liczby 5. To znany, elementarny algorytm
> >zamiany liczb z systemu dziesiętnego na binarny.
> >Rzecz w tym, że dokładnie to samo możemy zrobić np. dla funkcji
> >zdefiniowanej tak:
> >- jeśli x jest nieprzyste, to x*1,5+0,5,
> >- jeśli x jest parzyste, to x/2.
>
> >I to akurat jest słynny ciąg Collatza.
> >Generuje on strukturę binarną zupełnie inną niż liczby naturalne
> >zapisane binarnie, ale spełnia ona wszystkie zasady struktur, o
> >których pisałem.
>
> No nie calkiem - ciagi sa zmiennej dlugosci. Liczby na kolejnych
> etapach moga byc znacznie wieksze niz poczatkowa.
> Jak chcesz to zamienic potem na permutacje ?

Każdą liczbę liczymy do ustalonej iteracji. Jeśli chcemy permutację np. 8 elementową, to liczymy 3 iteracje:

https://zapodaj.net/images/e8e26607fa0b8.jpg

> Nadal nie rozumiem, do czego zmierzasz, czy co chcesz osiagnac.
> Jesli wychodzimy od N bitow, to bity moga kodowac liczby od 0 do
> 2^N-1.

Zgadza się.

> Ktore z tych liczb chcesz wybrac do swojego podzbioru ?

Wszystkie. Całe permutacje. I mnożyć te permutacje ze sobą. Na przykład mnożyć takie 2 permutacje.

https://zapodaj.net/images/e8e26607fa0b8.jpg

https://zapodaj.net/images/954ed40d02b60.jpg

Docelowo permutacji ma być więcej, np. 64. No i mają być większe.

> >Nie mogę jednak zrozumieć zasad mnożenia tych struktur na tym
> >skrótowym poziomie. I nie wiem, czy w ogóle istnieją takie zasady.
>
> Ja tam na razie widze, ze M-elementowych permutacji jest mozliwych M!,
> i mozesz z nich wybrac podzbior w ktorym zlozenie permutacji bedzie
> wewnetrzne:
> 2-elementowy, 3 elementowy, k-elementowy - gdzie k<=M,
> M! elementowy, (M-1)!, i cala masa innych licznosci.

Nie jest możliwych M! permutacji, bo struktury, które zadają te ciągi mają określone zasady (o których pisałem). Te zasady zawężają ten zbiór. 2^n-elementowych permutacji jest tylko:

ILOCZYN_(k=1)^(n) 2^(2^(k-1)-1)

Na przykład struktur 8-elementowych jest:

1*2*8 = 16

Te zasady obowiązują dla dowolnych ciągów (gdzie a i b są jakimiś całkowitymi liczbami nieparzystymi):

f(x)=a/2*x+b/2 - gdy x nieparzyste
f(x)=x/2 - gdy x parzyste

Nie wiem, czy mnożenie tych struktur zachowuje wewnętrzność, czyli, czy wynik nadal spełnia zasady struktury. Wówczas permutacji może być więcej, ale prawdopodobnie mnożenie jest wewnętrzne. Więc zarówno wejściowych struktur mamy teoretycznie ILOCZYN_(k=1)^(n) 2^(2^(k-1)-1), jak i wyjściowych też prawdopodobnie będzie ILOCZYN_(k=1)^(n) 2^(2^(k-1)-1). Należy też pamiętać, że nie wszystkie te struktury możemy zdefiniować za pomocą pary a i b. Możemy zdefiniować tylko część wszystkich możliwych struktur za pomocą ciągów, inne możemy (prawdopodobnie) wymnożyć (a to ile innych unikalnych struktur możemy wymnożyć i czy w ogóle możemy, jest właśnie przedmiotem moich dociekań).

[osobliwy nick]

> No nie calkiem - ciagi sa zmiennej dlugosci. Liczby na kolejnych
> etapach moga byc znacznie wieksze niz poczatkowa.
> Jak chcesz to zamienic potem na permutacje ?

Jeszcze raz, bo poprzednio nie zrozumiałem pytania. Oznaczamy na czarno operację typu a/2*x+b/2, zaś na biało operację typu x/2. W ciągu:

f(x) = 3/2*x+1/2 - gdy x nieparzyste
f(x) = x/2 - gdy x parzyste

Będzie to wyglądać tak:

https://zapodaj.net/images/e8e26607fa0b8.jpg

W ten sposób generujemy właśnie jedną z takich struktur. Nie ma znaczenia, co za liczby stoją w kratkach z punktu widzenia naszych struktur. Dla jasności taką strukturę możemy odczytać jako nastepującą permutację:

0 1 2 3 4 5 6 7

0 5 2 3 4 1 6 7

A tutaj:

https://zapodaj.net/images/954ed40d02b60.jpg

Mamy ciąg:

f(x) = 5/2*x+7/2 - gdy x nieparzyste
f(x) = x/2 - gdy x parzyste

Możemy to odczytać jako permutację:

0 1 2 3 4 5 6 7

[J.F.]

Użytkownik "osobliwy nick" napisał w wiadomości grup

dyskusyjnych:fd47eaf3-c502-41f2...@googlegroups.com...

>> No nie calkiem - ciagi sa zmiennej dlugosci. Liczby na kolejnych
>> etapach moga byc znacznie wieksze niz poczatkowa.
>> Jak chcesz to zamienic potem na permutacje ?

>Jeszcze raz, bo poprzednio nie zrozumiałem pytania. Oznaczamy na
>czarno operację typu a/2*x+b/2, zaś na biało operację typu x/2. W
>ciągu:
>f(x) = 3/2*x+1/2 - gdy x nieparzyste
>f(x) = x/2 - gdy x parzyste

>Będzie to wyglądać tak:
>https://zapodaj.net/images/e8e26607fa0b8.jpg

Jesli dobrze rozumiem - w kolumnie mamy kolejne wyrazy ciagu, a w
kolejnych kolumnach - kolejne liczby poczatkowe ?

>W ten sposób generujemy właśnie jedną z takich struktur. Nie ma
>znaczenia, co za liczby stoją w kratkach z punktu widzenia naszych
>struktur.

To rozumiem, ale jesli chodzi o ciag Collatza, to ma on zmienna
dlugosc dla kazdej liczby.
Chyba, ze sie ograniczysz do kilku bitow, i dopelnisz zerami gdy sie
skonczy - a nie, nie musisz, on wpada w petle ..

>Dla jasności taką strukturę możemy odczytać jako nastepującą
>permutację:
>0 1 2 3 4 5 6 7
>0 5 2 3 4 1 6 7

Tylko czy to jest jednoznaczne/wielowartosciowe ?
Ten przyklad jest, ale w ogolnosci to chyba nie musi.

>A tutaj:
>https://zapodaj.net/images/954ed40d02b60.jpg
>Mamy ciąg:
>f(x) = 5/2*x+7/2 - gdy x nieparzyste
>f(x) = x/2 - gdy x parzyste

No i pieknie, tylko ... rozumiem, ze docelowo kolumn chcesz wiecej,
bitow adekwatnie do ilosci kolumn,
a ile tych roznych funkcji/struktur ?

Chcialbys sie dowiedziec czy funkcje z rodziny
f(x) = a/2*x+b/2 - gdy x nieparzyste

f(x) = x/2 - gdy x parzyste

generuja jakas rodzine permutacji o "wewnetrznym" charakterze ?

J.

[J.F.]

Użytkownik "osobliwy nick" napisał w wiadomości grup

dyskusyjnych:d08dcb7e-6286-405f...@googlegroups.com...

>> Pamietasz kod Graya ? pierwszy wiersz/najmlodszy bit moze wygladac
>> 0110011001100...
>>
>> Jak to pasuje do Twoich permutacji to nie wiem.

>Też nie wiem, ale na pierwszy rzut oka nie widzę raczej związków.

Do twoich funkcji nie pasuje, natomiast w ogolnosci - to jest kod, w
ktorym sasiednie wartosci roznia sie o 1 bit ...

>> >W sumie widzę, że to do niczego nie prowadzi.
>> >Tym bardziej, że chcę rozważać iloczyny takich struktur powiedzmy
>> >128-wierszowe.
>
>> Czyli liczby 128 bitowe, czy 128 wybranych pemutacji ?

>Liczby 128-bitowe. Każda liczba od 0 do 2^128-1 ma mieć przypisaną
>jakąś liczbę 128-bitową.

>> A ile tych permutacji chcesz wybrac ? 128 to jeszcze idzie
>> przeanalizowac ktore sie powtarzaja .

>64. Ale permutacji liczącej 2^128 elementów nie przeanalizujesz.

Faktycznie - troche duzo :-)

>Z 64 takich permutacji chcę utworzyć powiedzmy iloczyny
>20-czynnikowe.

ale "powiedzmy" czy dokladnie ?
Bo o ile w podzbiorze 64 permutacji wzglednie latwo (ale nie dla
permutacji 2^128 elementowej) sprawdzic czy ich zlozenie (a jest ich
raptem 64*64) jest wewnetrzne,
to jesli wewnetrzne musi byc dopiero zlozenie 20, to juz trudniej
sprawdzic :-)

>To jest 2^120 wariacji z powtórzeniami iloczynów. Zaś każda
>permutacja liczy 2^128 elementów. Przemnożenie tylko dwóch takich
>permutacji może zająć miliardy lat, a co dopiero powyliczanie
>wszystkich wariacji 20-czynnikowych. Poza tym nawet, jeśli każdą
>liczbę 128-bitową w jakiś cudowny sposób uprościlibyśmy tak, że
>zajmowałaby 1 bajt, to wciąż potrzeba nam 2^128/(100*10^12) =
>3.4028237e+24 dysków SSD 100-terabajtowych. Na Ziemi nie ma tylu
>ziarenek piasku, a co dopiero takich dysków.

>Dlatego nie da się tego ustalić dla tak dużych liczb obliczeniowo.
>Trzeba to jakoś oszacować (o ile oszacować się da, to też nie jest
>jasne).

A masz jakis dalszy sens w tym sprawdzaniu ?

>> Nadal nie rozumiem, do czego zmierzasz, czy co chcesz osiagnac.
>> Jesli wychodzimy od N bitow, to bity moga kodowac liczby od 0 do
>> 2^N-1.

>Zgadza się.

>> Ktore z tych liczb chcesz wybrac do swojego podzbioru ?

>Wszystkie. Całe permutacje. I mnożyć te permutacje ze sobą. Na
>przykład mnożyć takie 2 permutacje.

>Docelowo permutacji ma być więcej, np. 64. No i mają być większe.

Ale czemu tylko 64 ?

>> >Nie mogę jednak zrozumieć zasad mnożenia tych struktur na tym
>> >skrótowym poziomie. I nie wiem, czy w ogóle istnieją takie zasady.
>
>> Ja tam na razie widze, ze M-elementowych permutacji jest mozliwych
>> M!,
>> i mozesz z nich wybrac podzbior w ktorym zlozenie permutacji bedzie
>> wewnetrzne:
>> 2-elementowy, 3 elementowy, k-elementowy - gdzie k<=M,
>> M! elementowy, (M-1)!, i cala masa innych licznosci.

>Nie jest możliwych M! permutacji, bo struktury, które zadają te ciągi
>mają określone zasady (o których pisałem).

Na te struktury na razie w ogole nie patrze.
Zbior wszystkich permutacji (M!) jest grupa - skladanie jest
wewnetrzne.
Ciekawe czy da sie wybrac taki podzbior o licznosci np M!-1.
Albo M!/2

>Te zasady zawężają ten zbiór. 2^n-elementowych permutacji jest tylko:
>ILOCZYN_(k=1)^(n) 2^(2^(k-1)-1)
>Na przykład struktur 8-elementowych jest:
>1*2*8 = 16
>Te zasady obowiązują dla dowolnych ciągów (gdzie a i b są jakimiś
>całkowitymi liczbami nieparzystymi):
>f(x)=a/2*x+b/2 - gdy x nieparzyste
>f(x)=x/2 - gdy x parzyste

>Nie wiem, czy mnożenie tych struktur zachowuje wewnętrzność, czyli,
>czy wynik nadal spełnia zasady struktury.

no coz, proponuje sprawdzic dla mniejszej ilosci. Byc moze szybko sie
okaze, ze nie ma wewnetrznosci
Niestety - kolejny krok to 16, a nastepny - 32, i to juz moze byc za
duzo do obliczen.

ale nie - masz przeciez wtedy iles tam wybranych (powiedzmy 16)
permutacji po 32 elementy kazda - to ciagle drobiazg.
Wewnetrznosc jednego zlozenia sprawdzisz bez wiekszych problemow i dla
miliona elementow.
Dopiero jakiesz szersze sprawdzenie zajmie wiecej czasu.

Alternatywnie pozostaje analiza jaka wczesniej przeprowadzilem - co
sie w tych permutacjach dzieje, ale to raczej dla malej ilosci.

J.

[osobliwy nick]

> >Jeszcze raz, bo poprzednio nie zrozumiałem pytania. Oznaczamy na
> >czarno operację typu a/2*x+b/2, zaś na biało operację typu x/2. W
> >ciągu:
> >f(x) = 3/2*x+1/2 - gdy x nieparzyste
> >f(x) = x/2 - gdy x parzyste
>
> >Będzie to wyglądać tak:
> >https://zapodaj.net/images/e8e26607fa0b8.jpg
>
> Jesli dobrze rozumiem - w kolumnie mamy kolejne wyrazy ciagu, a w
> kolejnych kolumnach - kolejne liczby poczatkowe ?

Tak. Pierwszy wiersz to tylko liczby początkowe - inicjujące ciąg.

> >W ten sposób generujemy właśnie jedną z takich struktur. Nie ma
> >znaczenia, co za liczby stoją w kratkach z punktu widzenia naszych
> >struktur.
>
> To rozumiem, ale jesli chodzi o ciag Collatza, to ma on zmienna
> dlugosc dla kazdej liczby.
> Chyba, ze sie ograniczysz do kilku bitow, i dopelnisz zerami gdy sie
> skonczy - a nie, nie musisz, on wpada w petle ..

Nie ma czegoś takiego jak długość ciągu Collatza, bo każdy taki ciąg możemy iterować w nieskończoność. Zwyczajowo długością ciągu Collatza nazywa się liczbę iteracji, po których osiąga on liczbę 1, ale iterować możemy dalej. Nie interesuje nas, czy ciąg się zapętli lub będzie rozbieżny do nieskończoności. Nie ma więc ograniczeń co do wysokości, czy szerokości takiej struktury. Nie ma problemu, żeby wygenerować strukturę dla np. 100 iteracji i 2^100 kolejnych liczb.

> >Dla jasności taką strukturę możemy odczytać jako nastepującą
> >permutację:
> >0 1 2 3 4 5 6 7
> >0 5 2 3 4 1 6 7
>
> Tylko czy to jest jednoznaczne/wielowartosciowe ?
> Ten przyklad jest, ale w ogolnosci to chyba nie musi.

Jeśli chodzi Ci o to, czy każda taka macierz daje taką strukturę i permutację, to tak. Istnieje wiele prac poruszających ten temat w odniesieniu do ciągu Collatza. Ciągi tego typu dla liczb od 0 do 2^n-1 dają wszelkie możliwe kombinacje przekształceń (mnożeń z dodawaniem i dzieleń), co więcej zachowują one zasady tych struktur, które opisałem. Dowody dotyczące ciągów Collatza można uogólnić na wszelkie ciągi typu:

a/2*x+b/2
x/2

Terence Tao w swojej niedawnej pracy używał tych właściwości do oszacowania, że ciągi Collatza są zbieżne dla niemal wszystkich liczb naturalnych:

https://arxiv.org/abs/1909.03562

Ale akurat jego pracy na ten temat nie polecam, bo ciężko z tego coś zrozumieć. Trochę jest o tym też tutaj:

https://arxiv.org/pdf/1805.00133.pdf

Ogólnie autorzy badający problem Collatza nazywają to "induced automorphism" i ogólnie badają "dynamics on the 2-adic integers" w tym kontekście. Te dowody, czy raczej lematy można uogólnić na dowolne ciągi jak wyżej. Nie są one jakoś szczególnie trudne do zrobienia, ani też odkrywcze, czy przełomowe w kontekście hipotezy Collatza, po prostu są. Zatem zawsze dostaniemy nie tylko permutację, rozważając strukturę o wymiarach dokładnie n na 2^n, ale także strukturę o tych konkretnych właściwościach.

> >A tutaj:
> >https://zapodaj.net/images/954ed40d02b60.jpg
> >Mamy ciąg:
> >f(x) = 5/2*x+7/2 - gdy x nieparzyste
> >f(x) = x/2 - gdy x parzyste
>
> No i pieknie, tylko ... rozumiem, ze docelowo kolumn chcesz wiecej,
> bitow adekwatnie do ilosci kolumn,
> a ile tych roznych funkcji/struktur ?

Tak, chcę rozważać struktury o wiele większe. Docelowo myślałem o 64 strukturach iterowanych do 128 iteracji o 2^128 elementach. Chodzi o wszelkie możliwe funkcje typu (a,b):

a/2*x+b/2
x/2

dla a=-7,-3,-5,-3,-1,1,3,5,7 oraz b=-7,-5,-3,-1,1,3,5,7. Dodatkowo funkcja może mieć również dzielnik ujemny:

a/2*x+b/2
x/-2

Co zwiększa liczbę wariacji. Np. (-5,7,-2):

f(x) = -5/2*x+7/2 - gdy x nieparzyste
f(x) = x/-2 - gdy x parzyste

Takich różnych wariacji jest 128, odpuszczając funkcje z dzielnikiem -2 mamy 64 różne wariacje z powtórzeniami parametrów tych funkcji.

> Chcialbys sie dowiedziec czy funkcje z rodziny
> f(x) = a/2*x+b/2 - gdy x nieparzyste
> f(x) = x/2 - gdy x parzyste
>
> generuja jakas rodzine permutacji o "wewnetrznym" charakterze ?

Nie, to jest fakt do udowodnienia na podstawie obecnej wiedzy o problemie Collatza, wystarczy uogólnić znane dowody. Funkcje te na pewno generują permutacje spełniające wewnętrzny charakter - czyli zasady tych struktur, które opisałem. Mnie interesuje mnożenie tych struktur, wychodząc od struktur danych przez te funkcje rekurencyjne. Pewne jest, że możemy pomnożyć/złożyć dwie funkcje (ich permutacje) i dostać nową permutację/strukturę, nową czyli taką, której nie opiszemy żadną znaną funkcję rekurencyjną (i wszystkie, które sobie roboczo wymnożyłem jak na razie również spełniały zasady tych struktur). Mnie interesuje częstotliwość pojawiania się tych nowych permutacji dla np. iloczynów/złożeń 20-czynnikowych oraz rozkład wyników.

Na przykład, czy nie będzie tak, że jak powyliczamy wszelkie wariacje z powtórzeniami 20-czynnikowych iloczynów, to np. 90% z otrzymanych wyników to będzie ta sama permutacja - że pomimo, że robimy złożenia różnych struktur i wszystkie wariacje, to mają one taką dziwną skłonność do dawania najczęściej tej samej struktury/permutacji na końcu. Czy może tak być? Teoretycznie tak, choć dla permutacji 2^128-elementowych zbiór potencjalnych różnych od siebie struktur jest ogromny i funkcja wszystkich wariacji iloczynów mogłaby być spokojnie różnowartościowa - pytanie, czy będzie?

[osobliwy nick]

> >Z 64 takich permutacji chcę utworzyć powiedzmy iloczyny
> >20-czynnikowe.
>
> ale "powiedzmy" czy dokladnie ?
> Bo o ile w podzbiorze 64 permutacji wzglednie latwo (ale nie dla
> permutacji 2^128 elementowej) sprawdzic czy ich zlozenie (a jest ich
> raptem 64*64) jest wewnetrzne,
> to jesli wewnetrzne musi byc dopiero zlozenie 20, to juz trudniej
> sprawdzic :-)

Dokładnie. To muszą być tego rzędu wielkości. Może iloczyny 10-czynnikowe, może 30-czynnikowe. Gwoli ścisłości muszą być to liczby tak duże, że nikt tego w rozsądnym czasie przez następne kilkadziesiąt lat nie policzy. Zastosowania mają być kryptograficzne.

> >Dlatego nie da się tego ustalić dla tak dużych liczb obliczeniowo.
> >Trzeba to jakoś oszacować (o ile oszacować się da, to też nie jest
> >jasne).
>
> A masz jakis dalszy sens w tym sprawdzaniu ?

Tak. Permutacje wyjściowe, powiedzmy, że 64 z nich mają być składowymi kluczy szyfrujących. Wylosowana wariacja z powtórzeniami np. 20-elementowa ma być kluczem, zaś końcowa permutacja 2^128-elementowa unikalnym sposobem zaszyfrowania wiadomości. Dlatego tak ważne jest, aby ktoś kto dobierze sobie losową wariację - złożenie 20-krotne tych struktur dostał na wyjściu nową unikalną strukturę, która daje jakiś schemat szyfrowania. Jeśli iloczyny będą dawać zbyt często te same permutacje w wyniku, to coś takie w ogóle nie będzie bezpieczne. Bo atakujący będzie mógł sobie wylosować dowolny klucz i z dużym prawdopodobieństwem na końcu uzyska ten sam wynik, jeśli dystrybucja wyników nie jest nazwijmy to wystarczająco różnowartościowa.

> Ale czemu tylko 64 ?

Można więcej, ale współczynniki a i b nie mogą być zbyt duże, bo obliczanie tych ciągów jest kosztowne obliczeniowo. Musi być tego jednak jednocześnie wystarczająco dużo, aby zbiór możliwych wariacji był duży - niemożliwy do przeszukania w rozsądnym czasie.

> >> Ja tam na razie widze, ze M-elementowych permutacji jest mozliwych
> >> M!,
> >> i mozesz z nich wybrac podzbior w ktorym zlozenie permutacji bedzie
> >> wewnetrzne:
> >> 2-elementowy, 3 elementowy, k-elementowy - gdzie k<=M,
> >> M! elementowy, (M-1)!, i cala masa innych licznosci.
>
> >Nie jest możliwych M! permutacji, bo struktury, które zadają te ciągi
> >mają określone zasady (o których pisałem).
>
> Na te struktury na razie w ogole nie patrze.
> Zbior wszystkich permutacji (M!) jest grupa - skladanie jest
> wewnetrzne.
> Ciekawe czy da sie wybrac taki podzbior o licznosci np M!-1.
> Albo M!/2

Da się - na przykład takie permutacje, w których co drugi element przechodzi sam w siebie. Ogranicza to zbiór wszystkich możliwych permutacji M!, jasne jest też, że złożenia nie wyprowadzą poza ten zbiór. Tylko, że mój przypadek jest mniej trywialny i ten przykład niewiele to wnosi.

> no coz, proponuje sprawdzic dla mniejszej ilosci. Byc moze szybko sie
> okaze, ze nie ma wewnetrznosci
> Niestety - kolejny krok to 16, a nastepny - 32, i to juz moze byc za
> duzo do obliczen.

Nie umiem tego zaprogramować, od lat nie zaglądałem do języka C. A ręcznie nie będę tego mnożył :) Zresztą prawdopodobnie okaże się, że wewnętrzność jest i będziemy w tym samym punkcie. Poza tym wewnętrzność pozwala rozstrzygnąć tylko jak duża jest potencjalnie przeciwdziedzina funkcji wszystkich wariacji złożeń. Nie będzie to dowód, że wyniki realnych złożeń będą różnowartościowe albo, że chociaż będzie sporo nowych unikalnych struktur w wynikach.

[J.F.]

Dnia Fri, 3 Jan 2020 16:22:24 -0800 (PST), osobliwy nick napisał(a):
>>>Z 64 takich permutacji chcę utworzyć powiedzmy iloczyny
>>>20-czynnikowe.
>>
>> ale "powiedzmy" czy dokladnie ?
>> Bo o ile w podzbiorze 64 permutacji wzglednie latwo (ale nie dla
>> permutacji 2^128 elementowej) sprawdzic czy ich zlozenie (a jest ich
>> raptem 64*64) jest wewnetrzne,
>> to jesli wewnetrzne musi byc dopiero zlozenie 20, to juz trudniej
>> sprawdzic :-)
>
> Dokładnie. To muszą być tego rzędu wielkości. Może iloczyny 10-czynnikowe, może 30-czynnikowe. Gwoli ścisłości muszą być to liczby tak duże, że nikt tego w rozsądnym czasie przez następne kilkadziesiąt lat nie policzy.
>Zastosowania mają być kryptograficzne.

Tak cos czulem :-)

Ale ... czy przypadkiem nie chcesz swojej kryptografii oprzec na dwoch
niewielkich liczbach a i b ?

>> Zbior wszystkich permutacji (M!) jest grupa - skladanie jest
>> wewnetrzne.
>> Ciekawe czy da sie wybrac taki podzbior o licznosci np M!-1.
>> Albo M!/2
>
> Da się - na przykład takie permutacje, w których co drugi element
> przechodzi sam w siebie. Ogranicza to zbiór wszystkich możliwych
> permutacji M!, jasne jest też, że złożenia nie wyprowadzą poza ten
> zbiór.

Ale to nam od razu ogranicza do (M-1)! dla jednego stalego elementu
czy (M/2)! dla co drugiego. czyli wielokrotnie mniej

A ja sie pytam o M!-1 - czyli w praktyce - czy jest taka permutacja,
ktorej nie da zlozyc z dwoch dowolnych innych.

I juz sobie sam odpowiem - nie ma, bo zamienmy w niej dwa elementy, i
juz mamy dwie permutacje - zamieniajaca i wynikową, ktorych zlozenie
daje nam te pierwotna.

Wiec pytanie sie zmienia na: jaki jest licznosc maksymalnego podzbior
permutacji, ktory tworzy grupe.

Da ktos przyklad na M!/2 ?

Bo na (M-1)! to sie znajdzie.

J.

[osobliwy nick]

> Ale ... czy przypadkiem nie chcesz swojej kryptografii oprzec na dwoch
> niewielkich liczbach a i b ?

To znaczy? Ma to być wiele par (a,b), które złożymy ze sobą. Każda z par a,b powinna być nie za duża.

> Ale to nam od razu ogranicza do (M-1)! dla jednego stalego elementu
> czy (M/2)! dla co drugiego. czyli wielokrotnie mniej
>
> A ja sie pytam o M!-1 - czyli w praktyce - czy jest taka permutacja,
> ktorej nie da zlozyc z dwoch dowolnych innych.

Fakt.

Ja bardziej skupiam się na zasadach mnożenia tych struktur, wychodząc od (a,b).

Ogólnie każdą taką strukturę uzyskaną z jakiegoś ciągu rekurencyjnego możemy opisać za pomocą czterech parametrów a, b, 2 lub -2 oraz wymiary struktury dane powiedzmy liczbą n. n niech oznacza liczbę iteracji, jednocześnie liczba elementów permutacji będzie wynosić 2^n. Odpuśćmy chwilowo parametr 2 lub -2 i rozważajmy tylko ciągi z dzieleniem przez 2. Wówczas na przykład taką strukturę:

https://zapodaj.net/images/e8e26607fa0b8.jpg

Możemy zapisać jako S=(3,1)_3. Jest jednak jeszcze jedna właściwość tych ciągów i struktur i parametr, który może być ważny. Mianowicie jak dotychczas rozważaliśmy ciągi generowane dla kolejnych liczb naturalnych. Możemy też jednak rozważać ciągi dla liczb 0,0+c,0+2c,0+3c,... Gdzie c to jakaś liczba nieparzysta. I okazuje się, że ciągi generowane dla tych liczb też dają takie struktury. Np. niech n=4, c=3, a=3, b=1, czyli S=(3,1,3)_4:

https://zapodaj.net/images/afcd8e64f7cb6.jpg

Możemy zatem dodać jeszcze jeden parametr c i rozważać struktury S=(a,b,c)_n. To co udało mi się dotychczas ustalić, to prawdopodobne zasady mnożenia parametrów a. Mianowicie jeśli mnożymy dwie takie struktury:

S1=(a1,b1,c1)_n

S2=(a2,b2,c1)_n

to uzyskamy jakąś strukturę S3=(a3,b3,c3)_n i możemy obliczyć parametr a, o ile wynik mnożenia jest zdefiniowany. Struktury te dublują się dla parametrów a,b,c powiększonych o 2^n. Na przykład (1,1,1)_3 jest tym samym co (9,1,1)_3. To są te same struktury. Podobnie identyczne są (-7,1,1)_4 i (9,1,1)_4. Jeśli np. n=3, to sens ma zatem rozważanie struktur z parametrami a różniącymi się od siebie o maks. 8. Na przykład a=1,3,5,7 albo a=-3,-1,1,3. Jeśli weźmiemy a=-3 oraz a=5, to będą to te same struktury dla n=3. Wiedząc to możemy wyliczyć a1*a2=a3. Wystarczy pomnożyć a1*a2, zaś następnie sprawdzić, czy wynik mieści się w przedziale -2^(n-1)-1 do 2^(n-1)-1,, jeśli tak, to a3 będzie wynikiem tego mnożenia. Jeżeli wynik nie mieści się w tym przedziale, to należy obliczyć a1*a2 - 2^n*x, dla takiego x, że wynik będzie się mieścił w tym przedziale. Przykład:

(5,3)_4*(3,1)_4=(-1,-3)_4

Widzimy, że 5*3=15. Zaś a może wynosić od -7 do 7. Musimy zatem odjąć 15-16=-1. Stąd a3=-1. Inny przykład:

(7,1)_4*(3,1)_4= ?

Ten iloczyn z kolei nie jest zdefiniowany. Nie istnieje rozwiązanie, ale wiemy, że a3 powinno wynieść 7*3-16=5, gdyby rozwiązanie istniało.

Ta zasada wydaje się być uniwersalna. I to jedyna zasada mnożenia tych struktur, którą udało mi się jak na razie ustalić. Problematyczne jest to, że mnożenie nie jest przemienne. Na przykład:

(3,1)_4*(5,-3)_4=(-1,3)_4

(5,-3)_4*(3,1)_4= ?

Pierwszy iloczyn ma rozwiązanie, drugi nie ma. Jedne niewielu nieprzemiennych działań w matematyce to sumy nieskończone oraz odejmowanie (sumy nieskończone tu raczej nie będą występować). Wydaje mi się zatem, żeby aby obliczać drugi parametr b, jako wynik mnożenia tych struktur należy coś odejmować od siebie. Co więcej w tym drugim iloczynie to odejmowanie musi jakoś wyprowadzać nas poza zbiór możliwych b dla n=4 (i nie może istnieć zasada, która do tego zbioru z powrotem prowadzi jak w przypadku parametru a). Zaś w tym pierwszym tak się nie dzieje i dostajemy b=3.

Tutaj mam przykładowe wyniki składania:

(3,1)_4*(5,3)_4=(-1,-3)_4
(3,1)_4*(5,-3)_4=(-1,3)_4
(-3,1)_4*(5,3)_4=(1,-5)_4
(-3,1)_4*(5,-3)_4=(-1,-5)_4

(5,3)_4*(3,1)_4=(-1,-3)_4
(5,-3)_4*(3,1)_4= niezdefiniowane
(5,3)_4*(-3,1)_4=(1,-3)_4
(5,-3)_4*(-3,1)_4=(1,-5)_4

c zawsze przyjąłem jako równe 1. Nie wiem, czy nie trzeba pokombinować z jakimiś innymi c, żeby to zrozumieć.

[osobliwy nick]

Widzę, że to mnożenie współczynników "a" sprawdza się, ale nie zawsze znak się zgadza. Tu mamy:

(-3,1)_4*(5,3)_4=(1,-5)_4

czyli -3*5=-15, dodajemy 16 i otrzymujemy 1, zgodnie z przewidywaniami. Ale tu:

(-3,1)_4*(5,-3)_4=(-1,-5)_4

też powinniśmy dostać 1, a otrzymujemy -1.

Jeszcze kilka przykładów:

(3,3)_4 * (7,-1)_4 = (5,7)_4

(5,3)_4*(7,1)_4 = (3,-3)_4

(3,3)_4*(7,-1)_4 = (5,7)_4

(7,5)_4*(7,7)_4 = (1,5)_4

[osobliwy nick]

Kolejna porcja mnożeń na struktur n=4:

(5,3)*(1,1)=(5,-3)
(5,3)*(1,-1)=(5,3)
(5,3)*(-1,1)=(-5,-3)
(5,3)*(-1,-1)=(-5,3)

(1,1)*(5,3)=(5,5)
(1,-1)*(5,3)=(5,3)
(-1,1)*(5,3)=(-5,-3)
(-1,-1)*(5,3)=(-5,-5)


(3,1)*(5,3)=(-1,-3)
(3,1)*(5,-3)=(-1,3)
(-3,1)*(5,3)=(1,-5)
(-3,1)*(5,-3)=(-1,-5)

(5,3)*(3,1)=(-1,-3)
(5,-3)*(3,1)=niezdefiniowane
(5,3)*(-3,1)=(1,-3)
(5,-3)*(-3,1)=(1,-5)

(5,3)*(7,1)=(3,-3)
(3,3)*(7,-1)=(5,7)
(7,5)*(7,7)=(1,5)
(1,7)*(-5,3)=(-5,-5)

(7,1)*(3,1)=(-7,-5)

Nic z tego nie rozumiem. Zaczynam wątpić, czy w ogóle rządzi się to jakimikolwiek zasadami. Ile razy coś wygląda na jakąś zasadę znajduje się od niej wyjątek.

[osobliwy nick]

Stworzyłem pewien parametr, który może pomóc sklasyfikować jakoś te struktury. Coś w rodzaju środka ciężkości. Możemy go wyznaczyć traktując kolejne wiersze jako liczby binarne. Weźmy n=3. Dla (3,1) mamy:

01010101
00110011
01001011

Możemy więc obliczyć pierwszy wiersz jako:

1 * 2^0 + 0 * 2^1 + 1 * 2^2+ 0 * 2^3 + 1 * 2^4 + 0 * 2^5 + 1 * 2^6 = 85

Drugi wiersz wyniesie 102, zaś trzeci 105. Suma tych wierszy to parametr W. W tym przypadku wyniesie 292. Parametr ten pozwala określić chyba jednoznacznie każdą taką strukturę za pomocą jednej liczby. Jednocześnie określa on rozkład takiej struktury - czy ma ona ona większe zagęszczenie po lewej, czy po prawej stronie. Możemy na przykład od razu stwierdzić, że jeśli jedna struktura ma W większe od drugiej, to ma większe zagęszczenie 1 po prawej stronie, od tej drugiej.

Wypisałem i policzyłem wszystkie wariacje (a,b) dla n=4.

39062 -7 -7
78494 -7 -5
83582 -7 -3
89864 -7 -1
60737 -7 1
67019 -7 3
72107 -7 5
111539 -7 7
107174 -5 -7
48527 -5 -5
71384 -5 -3
84317 -5 -1
85499 -5 1
60002 -5 3
82859 -5 5
62642 -5 7
68282 -3 -7
107204 -3 -5
43397 -3 -3
82319 -3 -1
87407 -3 1
94199 -3 3
56402 -3 5
63194 -3 7
86684 -1 -7
66977 -1 -5
102839 -1 -3
44702 -1 -1
67559 -1 1
79982 -1 3
89834 -1 5
63827 -1 7
60737 1 -7
67019 1 -5
72107 1 -3
111539 1 -1
39062 1 1
78494 1 3
83582 1 5
89864 1 7
85499 3 -7
60002 3 -5
82859 3 -3
62642 3 -1
107174 3 1
48527 3 3
71384 3 5
84317 3 7
87407 5 -7
94199 5 -5
56402 5 -3
63194 5 -1
68282 5 1
107204 5 3
43397 5 5
82319 5 7
67559 7 -7
79982 7 -5
89834 7 -3
63827 7 -1
86684 7 1
66977 7 3
102839 7 5
44702 7 7

Jest ich 64, ale połowa się powtarza. Dzieje się tak ponieważ dowolne (a,b) jest równe (a+8,b+8). Np. (-1,5) = (7,-3). Zrobiłem wykres:

https://zapodaj.net/images/6bd1543629705.png

I wygląda to jak biały szum. Żadnego porządku względem uporządkowanych par (a,b). Pomyślałem, że może w takim razie rządzi się to jakimś innym porządkiem, niezwiązanym z (a,b). Pozbyłem się powtórzeń, zostając z 32 parametrami W i uporządkowałem je od najmniejszego do największego:

39062
43397
44702
48527
56402
60002
60737
62642
63194
63827
66977
67019
67559
68282
71384
72107
78494
79982
82319
82859
83582
84317
85499
86684
87407
89834
89864
94199
102839
107174
107204
111539

I znów nie wygląda to zachęcająco:

https://zapodaj.net/images/b6a66a1abdd56.png

Te dane każą mi przypuszczać, że nie ma w tym żadnego porządku ze względu na parametry (a,b). Mnożenie tych struktur za pomocą tych parametrów też nie daje żadnych sensownych wyników. Trzeba to zatem faktycznie spróbować rozpatrywać eksperymentalnie. Na przykład sprawdzić liczbę wyników dla małych struktur np. n=4,5,6,7 przy zwiększających się iloczynach 2-czynnikowych, 3-czynnikowych, 4-czynnikowych. Czy, jeśli bierzemy wariacje z powtórzeniami coraz dłuższych iloczynów, to zwiększa to liczbę wyników? Oraz jaki wpływ na liczbę unikalnych wyników ma rozmiar struktury? Myślę, że rozmiar struktur jest kluczowy i dla dużych struktur liczba nowych wymnożonych struktur w zbiorze wszystkich wariacji z powtórzeniami iloczynów będzie ogromna. Choć na ścisły dowód tego faktu nie ma raczej co liczyć, dopóki nie będzie wiadomo jak mnożyć te struktury (a możliwe, że nigdy nie będzie wiadomo).

[osobliwy nick]

Ogólnie a i b z przedziału -(2^(n-1)-1) do 2^(n-1)-1 generują struktury o n-wierszach. Większych a i b dla struktur n-wierszowych nie ma sensu rozpatrywać, bo każde "a" jest równe a+2^(n-1) oraz b=b+2^(n-1). Więc dla liczb spoza przedziału i tak otrzymamy znów te same struktury.

Wydaje się, że, jeżeli a i b są z przedziału -(2^(n-1)-1) do 2^(n-1)-1, natomiast my rozpatrujemy struktury co najmniej n+1 wierszowe, to iloczyny zawsze będą różnowartościowe. Np. dla a i b z przedziału -3 do 3 struktury 4-wierszowe dają różne wyniki dla wszystkich wariacji:

3,1 * -3,-3 = -1,-5
3,1 * -3,-1 = -1,-7
3,1 * -3,1 = -1,7
3,1 * -3,3 = -1,5
3,1 * -1,-3 = 5,3
3,1 * -1,-1 = 5,1
3,1 * -1,1 = -3,7
3,1 * -1,3 = -3,5
3,1 * 1,-3 = -5,-5
3,1 * 1,-1 = 3,1
3,1 * 1,1 = 3,-1
3,1 * 1,3 = 3,-3
3,1 * 3,-3 = 1,3
3,1 * 3,-1 = 1,1
3,1 * 3,1 = 1,-1
3,1 * 3,3 = 1,-3

Co więcej znika właściwość wychodzenia poza zbiór zdefiniowany za pomocą a i b (choć i tak nie zdarzało się to często). Każdy iloczyn ma swój wynik określony za pomocą a i b, bo liczba struktur 4-wierszowych, nawet, jeśli weźmiemy tylko te określone za pomocą a i b z przedziału -7 do 7 jest większa niż liczba możliwych złożeń (wynosi 64).

Ponadto wynikowe a i b zdarzają się być większe niż te wyjściowe. Prawdopodobnie mnożąc struktury dla n=128, ale niewielkich a i b, np. z przedziału -7 do 7, możemy otrzymać w wynikach pary a i b nawet tak duże jak z przedziału -2^(128-1)-1 do 2^(128-1)-1. Wyniki zapewne będą zupełnie chaotyczne, podobnie jak te dla mniejszych przypadków. A złożenia tych wynikowych permutacji znów mogą dawać jakieś inne pary a,b z przedziału -2^(128-1)-1 do 2^(128-1)-1. To stwarza nadzieję, że takie iloczyny rzeczywiście mogą być różnowartościowe, pomimo, że nie otrzymamy żadnych struktur niezdefiniowanych, tj. niemożliwych do opisania za pomocą a i b. Bowiem wariacji z powtórzeniami iloczynów 20-czynnikowych zbioru np. 128-elementowego jest 1,39*10^42, zaś różnych struktur możliwych do określenia za pomocą a i b (wszystkie wariacje z powtórzeniami par a i b), które są liczbami z przedziału -2^(128-1)-1 do 2^(128-1)-1 jest 1,16*10^77. Wszystkie iloczyny 2-czynnikowe prawdopodobnie będą dawały zatem różne wyniki, podobnie jak w przykładzie powyżej, zaś iloczyny o większej liczbie czynników również powinny dawać różne, niepowtarzające się wyniki, bo par a,b z przedziału -2^(128-1)-1 do 2^(128-1)-1 jest o wiele rzędów więcej niż wariacji z powtórzeniami naszych struktur bazowych.

[osobliwy nick]

Lekko się pomyliłem co do wielkości struktur, które trzeba rozpatrywać, aby wyniki były różnowartościowe (hipotetycznie, bo ścisłych dowodów nie mam). Iloczyny będą prawdopodobnie różnowartościowe, gdy liczba wszystkich wariacji iloczynów (a,b), które są n-czynnikowe, będzie mniejsza niż liczba wszystkich struktur n-elementowych możliwych do opisania za pomocą jakichś (a,b). Na przykład za pomocą a i b z przedziału -3 do 3 możemy wyznaczyć 16 par/struktur (a,b). Możemy więc zrobić z nich 4096 wariacji złożeń 3-czynnikowych. Jeżeli weźmiemy sobie struktury n-wierszowe, które są określone za pomocą co najmniej równie dużej (4096) liczby par (a,b), to złożenia powinny być różnowartościowe.

Pytanie ile różnych struktur n-wierszowych można określić za pomocą (a,b)? Można to policzyć, bowiem można udowodnić, że każde (a,b), które jest n-wierszowe jest równe (a+2^(n-1),b+2^(n-1)). Na tej podstawie wiemy, że, jeśli weźmiemy a i b z przedziału -(2^(n-1)-1) do 2^(n-1)-1, to wszystkie ich wariacje (a,b) generują unikalne struktury o n-wierszach. Np. biorąc n=7 oraz a i b z przedziału -63 do 63 mamy dokładnie 4096 różnych wiariacji (a,b). Więcej nie można utworzyć, bo biorąc większe a lub b dla n=7, dostaniemy powtarzające się struktury. Np. (65,65)=(-63,-63). Zatem dla złożeń dowolnych struktur a i b z przedziału -3 do 3 dla struktur 7-wierszowych powinniśmy otrzymać odwzorowanie różnowartościowe. Podobnie dla struktur większych niż 7-wierszowe.

Przynajmniej to wygląda. Brdę musiał to sprawdzić obliczeniowo. Przy czym wykluczyłbym element neutralny (1,-1). Mnożenie tych struktur można tak ogólnie traktować jak mnożenie liczb pierwszych. Każdy iloczyn jest jak nowa liczba złożona, przemnożenie jej przez 1 ma niewielki sens. Podobnie jeśli pomnożymy dwie struktury przeciwne do siebie (a,b)*(c,-d) oraz (a,b)*(c,d), to dadzą one ten sam wynik różniący się tylko drugim znakiem (a jedna struktura będzie symetrycznym odbiciem drugiej). Natomiast z uwagi na fakt, że mnożenie permutacji nie jest przemienne nie możemy tego przenieść na przypadek:

(a,-b)*(c,d)
(a,b)*(c,d)

Tutaj wyniki mogą być zupełnie inne, niesymetryczne. Warto zlikwidować zatem elementy neutralne i pamiętać, że połowa wyników będzie symetryczna.