OldComp.cz

Komunitní diskuzní fórum pro fanoušky historických počítačů


Právě je 28.03.2024, 10:36

Všechny časy jsou v UTC + 1 hodina [ Letní čas ]




Odeslat nové téma Odpovědět na téma  [ Příspěvků: 30 ]  Přejít na stránku 1, 2  Další
Autor Zpráva
 Předmět příspěvku: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 01:57 
Online
Pan Štábní
Uživatelský avatar

Registrován: 24.05.2018, 22:32
Příspěvky: 1972
Bydliště: Most, Praha
Has thanked: 863 times
Been thanked: 697 times
Nedokázaly by mi zdejší mozkové kapacity poradit s algoritmem pro míchání karet? Úkol je následující:

Mám balíček 50 karet, očíslovaných (odspodu) 1 až 50. Tyto karty budu v pořadí 1 až 50 klást na 6 hromádek (číslovaných 1 až 6). V každé hromádce může být max. 10 karet. Pak hromádky sesbírám na sebe, od 1. hromádky po 6, tj. spodek 1. hromádky bude dole. Pokud to dělám náhodně, vzniknou mi následující grafy (histogramy) rozložení náhodnosti (pro 1 milion míchání) - tj. šance, se kterou se příslušná karta dostane na výstupu na pozici 1 až 50.

V grafech je vidět např. že 1. karta má výrazně vyšší šanci stát se opět 1. kartou. To z důvodu, že musí být položena jako první na začátek některé z hromádek, namísto 1/50 má tedy šanci 1/6 být opět první kartou. Podobně 50. karta má vyšší šanci být opět 50. kartou (dává se nakonec). Kromě toho jsou v grafech vidět oscilace náhodnosti na začátku a konci, způsobené hromádkováním.

Potřeboval bych náhodnost pokládání karet řídit tak, aby se to co nejvíc přiblížilo poslednímu ideálnímu grafu. Zlepšit by to mělo jít - když se např. pro 1. kartu sníží šance položení na 1. hromádku, měl by se snížit ten úlet na začátku. Ale zatím mé pokusy vedly spíš k ještě většímu rozhození náhodnosti. Neměl by někdo nějaký nápad, jak pokládání karet lépe řídit? Podmínky změnit nelze, např. nelze klást kartu dospodu hromádky, ani zvýšit počet hromádek, ani karty promíchat podruhé. Lze pouze ovlivňovat výběr hromádek při pokládání.
Příloha:
karty.png
karty.png [ 17.06 KiB | Zobrazeno 11084 krát ]

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 07:44 
Offline
Óm Nejvyšší

Registrován: 22.05.2013, 21:14
Příspěvky: 3642
Bydliště: Bratislava
Has thanked: 371 times
Been thanked: 788 times
Dva tipy:

1. Pokial pouzivas akykolvek pseudogenerator nahodnych cisel, tak si prever ci ma pre dane potreby dostatocnu nahodnost (dostatocnu periodu opakovania a dostatocne statisticky rovnomerne rozlozenie hodnot v intervale a v ramci poctu generovanych hodnot, ktore realne potrebujes (t.j. kolkokrat ho volas)). Pretoze to je zaklad a bez dobreho generatora je vsetko dalsie v podstate zbytocne.

2. Dopln do algoritmu este jeden krok. Po pozbierani hromadok kariet vyslednu pozbieranu kopu nahodne "sekni" - t.j. rozdel ju na dve casti, pricom prva cast bude mat nahodny pocet, napr. od 15 do 35 kariet, druha cast zvysok a casti prehod. Tym sa ti karty, ktore maju teraz zvysenu pravdepodobnost vyskytu na zaciatku ci na konci, dostanu doprostred a pravdepodobnosti sa vyrazne zrovnaju.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 09:03 
Offline
Pan Generální
Uživatelský avatar

Registrován: 23.03.2014, 20:13
Příspěvky: 2773
Has thanked: 224 times
Been thanked: 601 times
Jaký smysl má těch 6 hromádek? Budou potom potřeba ještě k něčemu dalšímu než k samotnému míchání?

Musí být před rozdílením balíček seřazený? Nešlo by ho prostě promíchat a teprve potom to rozhodit?

Jinak to míchání bych nechal na Knuthovi, ono už asi nic jednoduššího vymyslet nejde ;-)
Kód:
10 DIM p(50)
20 RANDOMIZE TIMER
30 FOR i = 1 TO 50: p(i) = i: NEXT i
40 FOR i = 50 TO 1 STEP -1
50     j = INT(RND(1) * i) + 1
60     w = p(i): p(i) = p(j): p(j) = w
70     NEXT i
80 FOR i = 1 TO 50: PRINT p(i), : NEXT i
90 END

_________________
Plesnivý sýr z Tesca, zatuchlé kuřecí řízky z Albertu, oslizlé hovězí a myší trus z Lidlu.
Nákup potravinářské inspekce v ČR, říjen 2023.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 10:03 
Online
Pan Štábní
Uživatelský avatar

Registrován: 24.05.2018, 22:32
Příspěvky: 1972
Bydliště: Most, Praha
Has thanked: 863 times
Been thanked: 697 times
Busy:

1. Generátor je dostačující, používá se KISS s periodou 2^127.
2. Mezikrok nejde přidat, je to použité v podmínkách kdy lze měnit jen způsob rozhazování na hromádky.


faraon:

To uvedené je pouze modelovým příkladem jiné problematiky, kterou tady nemohu rozepisovat (z firemních důvodů). Jinak řečeno, na vstupu je X objektů nějak seřazených, ty se náhodně rozloží do Y přihrádek (s menším počtem než je počet objektů) a po seskládání přihrádek musí být výstupní pořadí dostatečně náhodné oproti vstupnímu pořadí. V problematice nelze nic měnit z uvedeného, nelze použít jiné obcházky, lze pouze měnit rozhodování do které přihrádky se objekty přesunou. Je jedno v jakém pořadí vstupní objekty jsou, důležitá je jen změna výstupu oproti vstupu.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 10:11 
Offline
Óm Nejvyšší

Registrován: 22.05.2013, 21:14
Příspěvky: 3642
Bydliště: Bratislava
Has thanked: 371 times
Been thanked: 788 times
Je mozne po kazdom taktomto rozhodeni na hromadky otocit poradie v ktorom sa jednotlive hromadky poskladaju do vyslednej hromady ?


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 11:57 
Offline
Kecálek

Registrován: 28.10.2016, 21:03
Příspěvky: 122
Has thanked: 13 times
Been thanked: 50 times
Zajímavý problém. Při mých pokusech mi vychází, že pro 50 karet je ten limit 10 karet
na hromádku a šest hromádek výrazné omezení. A myslím si, že v daném případě toho
ideálního rozházení (na všech pozicích stejná pravděpodobnost) ani docílit nelze. Když
se některý z těch limitů zvedne, tak by to mělo pomoci.

Jsem schopen dosáhnout rovnoměrného rozložení pro první kartu v zamíchaném balíčku.
Příloha:
karty1.png
karty1.png [ 754 bajtů | Zobrazeno 11006 krát ]


Jiným způsobem jsem schopen dosáhnout rovnoměrného rozložení pro poslední kartu.
Příloha:
karty2.png
karty2.png [ 734 bajtů | Zobrazeno 11006 krát ]


Ale ne obojí najednou. Zkombinováním prvního a druhého postupu dostanu něco co není
úplně špatné, ale ani úplně dobré, jak pro první tak pro poslední kartu.
Příloha:
karty3.png
karty3.png [ 857 bajtů | Zobrazeno 11006 krát ]


První graf je vždy která vstupní karta je na prvním místě výstupu, druhý graf pro
25. kartu a třetí graf pro poslední kartu výstupu.

Chápu, že nemůžeš říkat některá firemní tajemství, ale mohl bys aspoň nějak obecně
říct jaký důvod vede k tomu, že třídění musí být po hromádkách? Jde o elektronickou
implementaci, nebo to je nějaké fyzické zařízení, kde skutečně se přeskupují nějaké
fyzické předměty? Jen by mě to zajímalo, z jaké situace vyplývá takovýto pěkný problém.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 15:22 
Online
Pan Štábní
Uživatelský avatar

Registrován: 24.05.2018, 22:32
Příspěvky: 1972
Bydliště: Most, Praha
Has thanked: 863 times
Been thanked: 697 times
Busy píše:
Je mozne po kazdom taktomto rozhodeni na hromadky otocit poradie v ktorom sa jednotlive hromadky poskladaju do vyslednej hromady ?
Ne, nic z postupu nelze měnit. :-)

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 15:35 
Online
Pan Štábní
Uživatelský avatar

Registrován: 24.05.2018, 22:32
Příspěvky: 1972
Bydliště: Most, Praha
Has thanked: 863 times
Been thanked: 697 times
lukz:

Stačilo by aby to rozložení bylo JEN zvlněné, nemusí být ideální, ale hlavně tam nesmí být ty obrovské výkyvy. Když to dělám náhodně, tak místy jde šance dosáhnout některé pozice skoro k nule, což je nepoužitelné.

Jak dosáhneš toho rozložení, že v 1. hromádku necháš prázdnou a dáš tam jen tu kartu která má být na 1. pozici? To jsem uvažoval, asi by se tím úplně znemožnilo řešit ostatní karty.

Důvod je ten, že se jedná o fyzické zařízení, jehož chování nelze změnit, jen se zjistilo, že jeho výsledky nevyhovují. Konkurence má podobná zařízení na stejném principu a tam jim to funguje dobře, takže by to mělo jít vyřešit.

Ty parametry jsou modelovým zjednodušením parametrů. Nevím jistě jestli jsem to přepočtem neomezil moc, možná by se dalo počítat se 7 hromádkami, ale větší volnost tam nebude.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 19:47 
Offline
Óm Nejvyšší

Registrován: 22.05.2013, 21:14
Příspěvky: 3642
Bydliště: Bratislava
Has thanked: 371 times
Been thanked: 788 times
Panda38 píše:
Busy píše:
Je mozne po kazdom taktomto rozhodeni na hromadky otocit poradie v ktorom sa jednotlive hromadky poskladaju do vyslednej hromady ?
Ne, nic z postupu nelze měnit. :-)
V tom pripade, podla mna, nie je mozne s takto popisanym algoritmom ziskat lepsie rozlozenie pravdepodobnosti, nez to co si nameral.

Este tu ale visi otazka ohladom samotneho generatora nahodnych cisel:
Panda38 píše:
Generátor je dostačující, používá se KISS s periodou 2^127.
No a prave toto nie je iste, ci to postaci. KISS je len kombinacia dalsich (obvykle velmi jednoduchych) generatorov, a ide o to ake su tie dalsie generatory. Pri nevhodnej kombinacii sa viac generatorov kludne moze navzajom vyrusit a vysledok moze byt menej kvalitny nez by daval kazdy generator samostatne.
Panda38 píše:
Konkurence má podobná zařízení na stejném principu a tam jim to funguje dobře, takže by to mělo jít vyřešit.
Potom asi nezostava nic ine len zistit presne nastavenie toho konkurencneho zariadenia, vratane toho z akych generatorov maju vyskladany KISS.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 19:58 
Online
Pan Štábní
Uživatelský avatar

Registrován: 24.05.2018, 22:32
Příspěvky: 1972
Bydliště: Most, Praha
Has thanked: 863 times
Been thanked: 697 times
Generátoru náhody věřím, dělal jsem analýzy a vycházel hodně dobře. Ale v tomhle případě by měl dávat rozumné výsledky i klasický 32-bit LCG generátor (nevolá se ho až tak moc) a ne aby to bylo takhle rozhozené, v generátoru problém nebude. Což je vidět i na tom, že při zvýšení počtu hromádek se křivka linearizuje.

Zda to je řešitelné nevím, stále ještě věřím že to má řešení, a jen se mi ho ZATÍM nedaří najít. Pokud to nepůjde vyřešit, tak to bude obrovský průšvih. Ale abych nedopadl jak s Eternity II, kdy jsem 3 měsíce věřil v nalezení řešení a zkoušel stovky metod a až pak teprve pochopil že to takhle nepůjde.

Tak teď chci zkusit metodu, kdy budu sledovat statistiku a akceptovat jen případy míchání vedoucí k linearizaci křivky. Jen pro vyzkoušení, zda se to vůbec dá linearizovat.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 21:10 
Offline
Pan Generální
Uživatelský avatar

Registrován: 23.03.2014, 20:13
Příspěvky: 2773
Has thanked: 224 times
Been thanked: 601 times
Mě tam pořád nesedí to, že balíček musí být na počátku seřazený. Vždycky ti pak vyjde šest hromádek seřazených od nejmenší do největší, a když to složíš, nadělá ti to ty zuby.

_________________
Plesnivý sýr z Tesca, zatuchlé kuřecí řízky z Albertu, oslizlé hovězí a myší trus z Lidlu.
Nákup potravinářské inspekce v ČR, říjen 2023.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 22:12 
Online
Pan Štábní
Uživatelský avatar

Registrován: 24.05.2018, 22:32
Příspěvky: 1972
Bydliště: Most, Praha
Has thanked: 863 times
Been thanked: 697 times
Balíček nemusí být seřazený. Je v nějakém stavu a jen pro výpočty statistiky jsou karty očíslované 1 až 50. Důležité je, jak ten algoritmus to pořadí změní. Není důležitý výchozí stav. Algoritmus to musí dostatečně zamíchat ať už to na vstupu je seřazené nebo ne.

První karta bude tedy vždy vespod některé z hromádek a aby se zabránilo častějšímu výskytu mezi prvními kartami na výstupu, musí se častěji pokládat do poslední hromádky než do první.

Hromádky, resp. přihrádky, jsou tam proto, protože to zařízení není schopné pojmout plný počet objektů aby si pro každý vyhradilo 1 přihrádku. Proto to míchá takhle složitě. Má jen vstup a výstup, nemůže dělat nějaké mezioperace.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 24.08.2018, 22:56 
Offline
Radil

Registrován: 18.10.2014, 23:10
Příspěvky: 377
Has thanked: 28 times
Been thanked: 120 times
Aby sa dostala prvá karta z balíčka na vrch musí byť v poslednej kôpke a navyše ako jediná. To je dosť náročné oproti nejakému inému umiestneniu, alebo oproti poslednej karte kde je šanca až 1:6


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 26.08.2018, 16:48 
Online
Pan Štábní
Uživatelský avatar

Registrován: 24.05.2018, 22:32
Příspěvky: 1972
Bydliště: Most, Praha
Has thanked: 863 times
Been thanked: 697 times
Důkaz, že problém má řešení - akceptoval jsem jen taková míchání, která statisticky vedou k linearizaci průběhu. Pro praxi je to sice nepoužitelná metoda (např.: lineárnost musí fungovat už při malém množství míchání a ne až zpětnou korekcí), ale lze na tom vidět, že se dá najít posloupnost míchání vedoucí k linearizaci. Ale i tak tahle metoda ještě bude stát za úvahu, pokud se to nepodaří vyřešit jinak.
Příloha:
linearizace_50.png
linearizace_50.png [ 15.04 KiB | Zobrazeno 10818 krát ]

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement


Nahoru
 Profil  
 
 Předmět příspěvku: Re: Algoritmus pro míchání karet
PříspěvekNapsal: 27.08.2018, 09:36 
Offline
Óm Nejvyšší

Registrován: 22.05.2013, 21:14
Příspěvky: 3642
Bydliště: Bratislava
Has thanked: 371 times
Been thanked: 788 times
Panda38 píše:
Důkaz, že problém má řešení - akceptoval jsem jen taková míchání, která statisticky vedou k linearizaci průběhu.
Podla mna toto ale nie je dokaz, pretoze cielenym vyberom vysledkov mozes dospiet k akejkolvek statistike, ktoru chces :)

Napriklad generujem nahodne cisla od 0 do 100 pomocou statisticky dobreho generatora (t.j. generovane cisla su rovnomerne rozdelene v celom intervale). Lenze ja chcem, aby v 90% pripadoch padli cisla mensie ako 10. Tak budem akceptovat iba tie vysledky kde padnu cisla do 10 a obcas (kazdy 9.krat) akceptujem aj cisla nad 10. A mam statistiku aku chcem:)


Nahoru
 Profil  
 
Zobrazit příspěvky za předchozí:  Seřadit podle  
Odeslat nové téma Odpovědět na téma  [ Příspěvků: 30 ]  Přejít na stránku 1, 2  Další

Všechny časy jsou v UTC + 1 hodina [ Letní čas ]


Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 16 návštevníků


Nemůžete zakládat nová témata v tomto fóru
Nemůžete odpovídat v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete přikládat soubory v tomto fóru

Hledat:
Přejít na:  
Založeno na phpBB® Forum Software © phpBB Group
Český překlad – phpBB.cz