kombinacje kolorów...

Witam

potrzebuję pomocy w budowie algorytmu, piszę pewną aplikację, na razie nie mogę zdradzić jej finalnej funkcjonalności :) ale utknąłem na takim problemie...

otóż, mam matrycę zbudowaną z pixeli która ma rozmiar 300x300, muszę stworzyć funkcję, która wygeneruje wszystkie możliwe kombinacje zapełnienia jej kolorami (na początek może to być np. 16 kolorów)... pixel po pixelku, wszystkie możliwe kombinacje...

pozdrawiam, czy ktoś może podzielić się jakimś pomysłem?
p.s. potrafię się odwdzięczyć :)

Czy wyobrazasz sobie liczbe takich kombinacji?

Jesli nie, to jak sie nie pomylilem to dla 16 kolorow bedzie ich tyle

51048665143419455907108426515682819201016709639403016172988845897839470256549892
09426383867325613524543351416833597764127456946916446081781809010549986553357741
49919022313644125163448958665294227453738486434708826271486702288778636608309092
41413835062294398529773770039005483488983518432593059170459248537716325243702439
27651743845488737416874805848368486492650738383584061192790228759690288354373732
12391543001823461997525404290885893862505930807247831235636308101834627654891900
29175832481515325237901056770741329855563005256232469943989976966419755763438607
51434216573702938766124166198630901624439464793581607521987353750595573887822793
12370581805074643268602210407981760989099419121454680121825587201870338560834519
40430924916208922103020467255826830294891366037746825676802826326857577117644053
03795386293220314902546474539632698134739750566765427099848313932256081872633513
31448312883188148186718489654930906178814001523106834142196250412028188304270621
03465592740473698362808662157285206135254478573739377701998948872589974496581061
74721909842993657489968700917291224846565376

//DOPISANE:
Adamo masz racje, ta liczba wyzej jest tylko dla 30x30 :)

zrób jak z brute forcem, najpierw wszystkie pixele kolor na 0, ostatni pixel 300x300 zmień kolor na 1, potem 2 i do 15, jak ma być 16 to zmień na 0 i zajmij się kolejnym od końca pixelem zmieniając na 1 itd, jak dojdziesz do pixela 1x300 to zmień 300x299 (z kolejnej linijki) itd z wszystkimi pixelami, czyli to będzie tyle kombinacji chyba co liczba 1 w systemie szesnastkowym z 90000-1 (300x300) zerami czyli chyba 1*16^90000 czyli raczej duuuużo więcej niż napisał foflik ale ile to nie wiem bo nie mam kalkulatora z takim zakresem :P, więc twój komputer raczej nigdy tego nie zrobi i żaden inny co jest teraz na świecie raczej też nie ;P

// BTW Nawet jakbyś wygenerował te kombinacje to gdzie zapiszesz wynik ? zajmie ci to najmniej 16^90001 bajtów - twardy żaden też chyba nie ma takiej pojemności ani RAM

a musi być inne wyjście dla tego co chcesz zrobić (chociaż nie wiem co chciałeś) - wystarczy odpowiednio długo pomyśleć - jak to ma być jakiś rewolucyjny program którego jeszcze nikt nie wymyślił to znaczy że wymyślenie sposobu nie jest taki prosty, jak chcesz coś takiego robić to tylko dla canvasu 10x10 dwukolorowego

No całkiem nieźle...z tego co wiem to będzie 16^{90000. Nie wiem czy jakiś procek będzie w stanie to wyrysować w rozsądnym czasie. A tu jeszcze piszesz, że na początek dla 16 kolorów. Nie chce myśleć co będzie z 16,7mln kolorów (16,7mln}90000) O BOŻE...JAKIE CYFRY :)

Liczba oznaczająca ilość różnych obrazów o rozdzielczości 300x300 i 24 bitowej głębi kolorów.
Innymi słowy: 16777216^90000
Czas obliczeń: ~9 minut [1' obliczenia, 8' konwersja na system dziesiętny]
Liczba cyfr: 650227

http://marooned.neostrada.pl/4prog/misc/potega.txt

wiem, że te liczby to kolosy, no nic... kombinuje dalej samemu :) to z brute force niezłe, ale umarłbym chyba w oczekiwaniu na wynik pracy :)

GraDios napisał(a)

wiem, że te liczby to kolosy, no nic... kombinuje dalej samemu :) to z brute force niezłe, ale umarłbym chyba w oczekiwaniu na wynik pracy :)

no i może nie tylko y, ale też twój syn, wnuczek, prawnuczek, praprawnuczek, praprapra..., prapraprapra i prapraprpapraprapraprapraprapraprawnuczek :P

Witam :)
Sam niedawno zajmowałem się bardzo podobnym tematem, ale w moich obliczeniach uwzględniałem tylko 2 kolory - czarny i biały. Matrycę można uznać za nic innego niż bitmapę, więc w moich rozważaniach zajmowałem się bitmapami monochromatycznymi. W takiej bitmapie jeden pixel zajmuje (wg moich wiadomości) 1 bit - czyli na bajcie informacji można zmieścić dane o 8 pixelach. Na wykładzie z chemii nawet z nudów obliczałem sobie ile zajęłyby wszystkie bitmapy czarnobiałe (ale nie chodzi tu nawet o odcienie szarości, tylko o 2 stany pixela :P ) o jakimś rozmiarze.
Nie jestem pewien czy moje rozumowanie było prawidłowe, ale doszedłem do czegoś takiego:

Bitmapa o wymiarach:

1x1 = do opisania 1 pixel, 2 możliwości każda o rozmiarze 1 bita = łączny rozmiar 2 bity
2x2 = do opisania 4 pixele, 16 możliwości każda po 4 bity = łączny rozmiar 64 bity (8 bajtów)
3x3 = do opisania 9 px, 512 możliwości każda po 9 bitów = 576 bajtów

itd. itp. :)

Użyty przeze mnie sposób obliczeń jest banalny (i mam nadzieję że słuszny)

AxB - wymiary bitmapy w pixelach
C - liczba kolorów

C^(AxB) = liczba możliwości

potem trzeba obliczyć ile zajmie każda możliwość, w przypadku 2 kolorów jak już wspominałem jest to 1 bajt na każde 8 pixeli (no i chyba jakieś dodatkowe informacje zapisywane w pliku BMP, ale to już pominąłęm)

Łączna objętość bitmap = liczba możliwości x objętość każdej (ale to już jest chyba oczywiste) :)

Z kolegami obliczaliśmy bardzo ciekawe potęgi liczby 2 - na kalkulatorach skończyła się skala więc mieliśmy na kartkach wyniki potęgowania np. 2^128 liczonego ręcznie :)

Ps.Te moje obliczenia miały pewien sens bo mają czemuś służyć, ale również na razie nie będę zdradzał szczegółów na ten temat :)

Może ma szybkiego kompa i jego praprapra...wnuczek dczeka się końca obliczeń :]

Tatusiu, Tatusiu,... a Jasia nowy komputer jest taki szybki, że robi nieskończoną pętlę w 5 minut [!!!] ;)

fajny taki program: generuje sie bitmapki 1600x1200@24bit i nie trzeba chodzic do fotografa:D a co lepsze, mozna wybrac ubranie etc. wsord zdjec mozna znalezc zdjecie nagie zdjecie swojej kolezanki:D

Marooned napisał(a)

Liczba oznaczająca ilość różnych obrazów o rozdzielczości 300x300 i 24 bitowej głębi kolorów.
Innymi słowy: 16777216^90000
Czas obliczeń: ~9 minut [1' obliczenia, 8' konwersja na system dziesiętny]
Liczba cyfr: 650227

http://marooned.neostrada.pl/4prog/misc/potega.txt

czemu aż 9 minut? :) sprzęt czy program? :)
u mnie było ździebko krócej (celeron 2,4GHz) :)
[embraced] >> /usr/bin/time -h bc out.bc > wynik.bc
47,87s real 41,92s user 0,19s sys

celeron 700MHZ :)

start - 0938 2005 CEST
stop - 0926 2005 CEST

wiec i tak lepiej niz u macka :)

//hmm.. to nie u mnie a u kumpla z ADM64 dużo GHz :| - M

/*
~>/usr/bin/time -h calc 16777216^90000 > wynik.txt 12:20
1m34,78s real 1m26,68s user 0,36s sys

D800 - calc r0x :P
*/

Karolaq napisał(a)

fajny taki program: generuje sie bitmapki 1600x1200@24bit i nie trzeba chodzic do fotografa:D a co lepsze, mozna wybrac ubranie etc. wsord zdjec mozna znalezc zdjecie nagie zdjecie swojej kolezanki:D

no fucktycznie, tam musiałoby być miliony bitmap identycznych ze zdjęciami ale znalezienie wśród wygenerowanych bitmapek chociaż jednej takiej zajęłoby pewno więcej czasu niż same generowanie tych wszystkich bitmap - czyli nie obejrzy się tak cz y siak :(

GraDios napisał(a)

...piszę pewną aplikację, na razie nie mogę zdradzić jej finalnej funkcjonalności :) ale utknąłem na takim problemie...

Ej [!!!] a może on chce napisać przełomowy software, który zabrałby zajęcie milionom fotografów na świecie.
Nawet nie trzeba będzie kupować aparatów cyfrowych... :-/
Tylko 'aplikację' i dobry sprzęcior troszkę wolnego czasu i za parę miliardów lat (oczywiście, jeśli się system nie zawiesi - to ma być aplikacja okienkowa :0 ) będzie miał wszystkie możliwe obrazki o rozdzielczości 800:600 8-0

I będzie miał zdjęcia wszystkich ludzi na Ziemii << Ale cfaniak [rotfl]

Mc napisał(a)

1x1 = do opisania 1 pixel, 2 możliwości każda o rozmiarze 1 bita = łączny rozmiar 2 bity
2x2 = do opisania 4 pixele, 16 możliwości każda po 4 bity = łączny rozmiar 64 bity (8 bajtów)
3x3 = do opisania 9 px, 512 możliwości każda po 9 bitów = 576 bajtów

jak ty to liczysz....

1x1 - jeden dwustanowy piksel to jeden bit
2x2 - 4 dwustanowe piksele, 4 bity
3x3 - 9 x 1bit, bajt i trochę
...
256x256 = 65536b = 2048B = 2kB

[dopisane]
ok, nie skumałem idei - Twoje obliczenia są ok.

Adamo napisał(a)

// BTW Nawet jakbyś wygenerował te kombinacje to gdzie zapiszesz wynik ? zajmie ci to najmniej 16^90001 bajtów - twardy żaden też chyba nie ma takiej pojemności ani RAM

otóż mylisz się, i to bardzo. 16^{90001 = 2}360004, czyli 360004b, czyli raptem 44kB - powinno się zmieścić, nawet na twoim dysku :> - Ł

[dopisane]
to jest liczone dla 16 kolorów. poza tym nie mówię o zapisaniu obrazków, tylko samej ich liczby. czyżby kolejne nieporozumienie?

ŁF napisał(a)

Adamo napisał(a)

// BTW Nawet jakbyś wygenerował te kombinacje to gdzie zapiszesz wynik ? zajmie ci to najmniej 16^90001 bajtów - twardy żaden też chyba nie ma takiej pojemności ani RAM

otóż mylisz się, i to bardzo. 16^{90001 = 2}360004, czyli 360004b, czyli raptem 44kB - powinno się zmieścić, nawet na twoim dysku :> - Ł

jak ty liczysz ?

http://marooned.neostrada.pl/4prog/misc/potega.txt

tu masz ile kombinacji jest możliwych - to trzeba jeszcze pomnożyć razy 30030024b kolorów i jeszcze jakiś bajt żeby to jakoś w pamięci oddzielić, a ty chyba policzyłeś ile w systemie 256-kowym (czyli najwydajniejszym chyba na zapisanie liczby na dysku) zajęłaby liczba kombinacji na dysku

otóż mylisz się, i to bardzo

faktycznie - nie wiem co ja obliczyłem - pomyliłem się o pomnożenie - tym bardziej się nie zmieści na żadnym dysku

A twoim zdaniem chyba zdjęcia wszystkich ludzi na świecie i tych co się jeszcze nie urodzili, zdjęcia ufo, yeti, ujęcia wszystkich krajobrazów na świecie, twoje zdjęcia we wszystkich możliwych ujęciach, w różnych ubraniach, w różnych miejscach i zlepki pikselów na dysku zajęłyby mniej miejsca niż jedno zdjęcie zajmuje normalnie ? to może napiszesz taki rewolucyjny paker plików i już żaden RAR czy ZIP ci nie podskoczy - nawet jak w paru bajtach zmieścisz tylko gigabajt danych.

ŁF napisał(a)

3x3 - 9 x 1bit, bajt i trochę

to chyba opisałeś ile zajmuje monochromatyczna bitmapka 3x3 px a nie ile kombinacji ma taka bitmapka - to jeszcze trza pomnożyć na ilość kombinacji

Może to zabrzmi mało skromnie, ale myślę że moje obliczenia były poprawne :P
Obliczałem ile zajmuje jedna bitmapka dwukolorowa, a następnie wynik mnożyłem przez ilość wszystkich kombinacji. I wydaje mi się, że ten sposób obliczania ile zajmą wszystkie takie bitmapy jest prawidłowy :)

Ale przejdźmy do rzeczy ważniejszej - widzę że inni też już znajdują jakieś ciekawe zastosowania programiku który w teorii generowałby wszystkie możliwe bitmapy. W moim "projekcie" sprawa wygląda tak:
jeśli by mieć wszystkie możliwe ułożenia pixeli (dajmy na to, że w rozdzielce 800x600) - czyli wszystkie możliwe bitmapy 800x600, to byłaby w tym zapisana przerażająca ilość informacji. Niektórzy wspominali np. o różnych fajnych (hehe) zdjęciach koleżanek. Skoro byłyby to wszystkie możliwe bitmapy, to mielibyśmy każde możliwe zdjęcie każdej osoby na Ziemi... i nie tylko :) Idąc dalej takim tokiem rozumowania - przecież wśród tych bitmap byłyby też skany książek... tych które wydrukowano, oraz tych które zostaną dopiero napisane. A z tym wiąże się ciekawy fakt - mając wszystkie bitmapy posiadałoby się całą możliwą do wymyślenia wiedzę świata... ba... Wszechświata :) Nie byłoby żadnej rzeczy, której nie mielibyśmy na "fotkach". Czyli wiedzielibyśmy wszystko o wszystkim co było jest i będzie. Jeden mój kolega stwierdził, że to jest wiedza jaką posiada Bóg :) Z ciekawych (dla mnie) rzeczy jakie możnaby było tam znaleźć byłyby np. plany budowy wehikułu czasu :) Oczywiście największym problemem związanym z tymi bitmapami jest to, że większość to tylko chaotyczne, losowe ułożenia pixeli, które nic by nie mówiły... i najpierw ktoś by to musiał posegregować wg przydatności - mi po głowie chodziło coś w stylu SETI.

PS.Takie właśnie zagadnienia chodzą po głowie studenta któremu nudzi się na wykładach :) Więc proszę przyjąć moje wywody z lekkim przymrużeniem oka, bo ja sam nie biorę tego do końca na serio, aczkolwiek pomysł z generowaniem takich bitmap można uznać za ciekawy :)

PS2.I na koniec zagadnienie filozoficzne - czy można uznać, że na tych bitmapach byłoby wszystko, co znajduje się we Wszechświecie? Bo jeśli tak... to wynika z tego, że nawet jeśli Wszechświat jest nieskończony, to można go całego opisać za pomocą skończonej ilości informacji (co prawda ogromnej) :)

Mc napisał(a)

Oczywiście największym problemem związanym z tymi bitmapami jest to, że większość to tylko chaotyczne, losowe ułożenia pixeli, które nic by nie mówiły... i najpierw ktoś by to musiał posegregować wg przydatności - mi po głowie chodziło coś w stylu SETI.

Mylisz sie :)
Najwiekszym problemem jest to ze nawet gdybys wzial setki tysiecy superkomputerow IBM (BlueGen) to do konca swiata bys kombinacji z 24 bitowa glebia kolorow nie wygenerowal...

<font color="green">[<font color="red">dopisane</span>]</span>
A co do rozmiaru 16 kolorowej bitmapy 300x300 zapisanej w formacie .bmp:
16^{9000045718 = 1440000}145718 = 65833920000 bajtow = 64290937,5 kB ~ 62784 MB ~ 61,3 GB
Wiec zmiescilo by sie to na srednim twardzielu...

Mc napisał(a)

PS2.I na koniec zagadnienie filozoficzne - czy można uznać, że na tych bitmapach byłoby wszystko, co znajduje się we Wszechświecie? Bo jeśli tak... to wynika z tego, że nawet jeśli Wszechświat jest nieskończony, to można go całego opisać za pomocą skończonej ilości informacji (co prawda ogromnej) :)

Nie, bo na 800x600 nie zmieścisz całej ksiażki, tylko co najwyżej jedną stronę. A kolejność stron w ksiażce jest zwykle istotna, więc również jest informacją. Aby więc mieć uporządkowane ksiażki na zdjęciu, musiałbyś mieć nieskończonych rozmiarów obrazek. Wniosek z tego, że zarówno wszechświat jak i wiedza są nieskończone :P (Einstein dodaje jeszcze do tego głupotę :) ).

A co do generowania tak wszystkiego, to jeżeli przyjąć, że słowa są w stanie opisać dużą część wiedzy, to generuj lepiej teksty, a nie obrazy. Z rozpoznawaniem tekstu idzie nam łatwiej niż z rozpoznawaniem obrazów :)

No i jeszcze jedna uwaga. Lepsze są jednak ukierunkowane wysiłki w wyszukiwaniu informacji, niż przeglądanie chaosu. Może więc spożytkujesz swoją energię szukając czegoś konkretnego, a nie przeglądając chaos? Bo może się okazać, że przeglądając to co wygenerował Ci komputer, nie dostrzeżesz informacji :)

Mc napisał(a)

Z ciekawych (dla mnie) rzeczy jakie możnaby było tam znaleźć byłyby np. plany budowy wehikułu czasu :)

I dostałbyś miliony informacji, że wehikuł czasu można zbudować z patyka i cytryny, albo inne podobne bzdety :P.

thenkles napisał(a)

Mc napisał(a)

Z ciekawych (dla mnie) rzeczy jakie możnaby było tam znaleźć byłyby np. plany budowy wehikułu czasu :)

I dostałbyś miliony informacji, że wehikuł czasu można zbudować z patyka i cytryny, albo inne podobne bzdety :P.

I to wszystko napisane dziesiatkami tysiecy fontow w kropki, kreski, i z innymi fajnymi bajerami...

grzequ napisał(a)

thenkles napisał(a)

Mc napisał(a)

Z ciekawych (dla mnie) rzeczy jakie możnaby było tam znaleźć byłyby np. plany budowy wehikułu czasu :)

I dostałbyś miliony informacji, że wehikuł czasu można zbudować z patyka i cytryny, albo inne podobne bzdety :P.

I to wszystko napisane dziesiatkami tysiecy fontow w kropki, kreski, i z innymi fajnymi bajerami...

Wiem, i właśnie dlatego sam nie biorę tego wszystkiego na poważnie :)
Ale cały ten temat doskonale pasuje do "Nietuzinkowych tematów" :)

A wracając do wehikułu... gdyby tak rozwinąć nieco sztuczną inteligencję... to możnaby stworzyć program, który będzie sobie przeglądał wszystkie projekty budowy wspomnianego wehikułu i sprawdzał, czy to może działać. W końcu prawa fizyczne są jako tako opisane (chociaż są pewnie jeszcze setki nieodkrytych rzeczy) Gdyby program miał zaszyty bardzo realistyczny "silnik" i symulował połączenia patyka i cytryn (albo te bardziej sensowne) to może po miliardzie lat doszedłby do prawidłowego projektu :) Bo skoro PSpice (nie jestem pewien czy to się dokładnie tak nazywa) pozwala symulować zależności między poszczególnymi tranzystorami, kondensatorami itp. - w sumie dałoby radę w tym projektować nowe procesory - to "nasz" program mógłby oprócz tego dorzucić kilka bardziej wymyślnych elementów :) Aż mi na myśl przyszła pewna nazwa części z DeLoreana z Powrotu do przyszłości - kondensator przepływu ;)

Ps.Ponownie zaznaczam że moje rozważania są czysto abstrakcyjne, trochę mi się nudzi w ten długi weekend :)

Tak mocno OT, w nawiązaniu do podróży w czasie: ciekawe ile osób, spośród czytających ten wątek zdaje sobie sprawę, że podróże w czasie są możliwe, ba! każdy z nas je odbywa, zupełnie nieświadomie. Nie mam tu bynajmniej na myśli jakichś transcendetalnych objawień, ale banalną jazdę autobusem :) Ze szczególnej teorii względności wynika, że czas, dla obiektów posuszających się płynie wolniej, a więc, gdy jedziemy sobie autobusem podróżujemy w przyszłość. Lepiej obrazuje to zjawisko tzw. Paradoks bliźniąt. Z praktycznych przykładów można podać, że marynarze, płynący prze 6 m-cy łodzią podwodną "nadrabiają" w stosunku do reszty świata około 1/1000000000 sekundy :)

PS.
Mam wrażenie, że za taaaki OT ten post pójdzie do NULLa :)

grzequ napisał(a)

<font color="green">[<font color="red">dopisane</span>]</span>
A co do rozmiaru 16 kolorowej bitmapy 300x300 zapisanej w formacie .bmp:
16^{9000045718 = 1440000}145718 = 65833920000 bajtow = 64290937,5 kB ~ 62784 MB ~ 61,3 GB
Wiec zmiescilo by sie to na srednim twardzielu...

bardziej miałem na myśli 24 bitowe w JPG nawet zapisane

ale to by była potęga - mieć zdjęcia wszystkiego i wszędzie ! Superszybki komputer z dobrze rozbudowaną sztuczną inteligencją i prosty algorytm i może za kilka tysięcy lat coś takiego ktoś sobie zrobi ... ;P

oj tam chaos:D wystarczy znalezc kilka bitmapek opisujacych, ktore zdjecia sa przydatne, a ktore nie :D jescze zamontowac ocr'a do programu. kazde wygenerowane zdjecie sprawdzalby, czy jest jakis tekst.

Ponosi Was chłopaki [green]

Mc napisał(a)

Wiem, i właśnie dlatego sam nie biorę tego wszystkiego na poważnie :)
Ale cały ten temat doskonale pasuje do "Nietuzinkowych tematów" :)

Mi się zdaje, że o wiele bardziej pasowałby do 'Off-Topic' :]

Mc napisał(a)

A wracając do wehikułu... gdyby tak rozwinąć nieco sztuczną inteligencję...

Nie sztuczną inteligencję tylko symulację (virtualną rzeczywistość) :P

Ai jeszcze a'propo tego, że da się wszystko zapisać w skończonej ilości informacji:

1. nie zapisałbyś tam informacji o obrazkach o 1 pixel szerszych :]
2. nie zapisałbyś tam rozwinięcia dziesiętnego liczby PI (ani wielu innych liczb których nie będę tu wymieniał bo nie starczy miejsca :P )
3. nie zapisałbyś wszystkich możliwych ciągów binarnych :P
4. na żadnym z tych obrazków nie zapisałbyś informacji o pozostałych obrazkach w kolekcji :P

Sebo napisał(a)

Ai jeszcze a'propo tego, że da się wszystko zapisać w skończonej ilości informacji:

1. nie zapisałbyś tam informacji o obrazkach o 1 pixel szerszych :]
2. nie zapisałbyś tam rozwinięcia dziesiętnego liczby PI (ani wielu innych liczb których nie będę tu wymieniał bo nie starczy miejsca :P )
3. nie zapisałbyś wszystkich możliwych ciągów binarnych :P
4. na żadnym z tych obrazków nie zapisałbyś informacji o pozostałych obrazkach w kolekcji :P

wszystko z tych rzeczy by się zapisało, co najwyżej w tak dużym pomniejszeniu obrazka że się tego za bardzo nie odczyta ;P

Fakt faktem, że z tych kombinacji kolorów zrobił się straszny off-topic :)
A co do tego, że nie da się zapisać / zakodować w bitmapie informacji o bitmapie o pixel większej... no ale przecież takie bitmapki 800x600 można sobie potem układać jak puzzle jedna obok drugiej :D Na wszystko (prawie) są sposoby ;)

hehe
Nie wiem czy zdajecie sobie sprawę, że program o którym tu piszecie i z którego istnienia tu korzyści płynące rozważacie już istnieje :] . Odkrył go pewien człowiek o nazwisku Darwin i wygląda na to, iż program ten nadal jest sprawny :)
pozdrawiam