Dotaz: php: nahodna cisla bez opakovani, priklad do praxe

[Jeason]

Tentokrat mam peknej orisek !

mam za ukol udelat nohodny losovani cisel od 1 - x (zadany rozhocim podle poctu zavodniku). nahodna cisla se nesmi opakovat (poradi zavidniku)

no a aby to nebylo tak jednoduchy zavod probiha ve trech částech a kazdý závodnik musi dostat nahodne 3 startovni pozice,ale musi mezi nima byt rozdil n-míst (zadany rozhocim) , aby nezacinali ze stejneho mista a nemohli se zavodnici vymlouvat, ze meli porad stejny podminky (hendikep)

Odpovědi

[Zdeněk Burda]

Tak ten úkol vyřeš... nebo ti v tom něco brání? Nějak totiž nemůžu najít otázku.

[Jeason]

jo to je ta dorbnost na kterou jsem zapomenl, vubec me nenapada jak bych to mel resit.
premyslel jsme prez random() a ulozit do do db. jenze to mi neresi problem toho ze se mi bude ciselna rada opakovat.
takze je mi kazda rada draha jaky bych to mel vyresit??

[puco]

Vy potrebujete generovat nahodnu n-prvkovu permutaciu, takze do googlu generating permutation.

[Honza Soukup]

Možná by nebylo od věci zkusit vyhledávání třeba na builderu, určitě tam podobný příklad najdete.
Třeba zkuste http://forum.builder.cz/read.php?20,161595,161628#msg-161628
nebo se můžete podívat do manuálu:
http://cz.php.net/rand
http://mirrors.inway.cz/manual/cs/function.srand.php

[volvox]

1. http://mirrors.inway.cz/manual/cs/function.range.php
2. http://mirrors.inway.cz/manual/cs/function.shuffle.php
3. http://mirrors.inway.cz/array

[Dejv]

Nejake odkazy tu uz padly, ale kdybych to chtel resit sam za kazdou cenu, tak bych asi pouzil neco jako

   while ( ('select count(cis) from db') < x )
      {
      cislo = rand
      if ( ('select count(cis) from db where cis=cislo') == 0 )
         {
         VlozCisloDoTabulky (cislo)
         }
      }

Jak rikam, neni to ani nahodou optimalni reseni, je to jen takovy napad.


A pak bych se pokusil si to trochu ulehcit a vygenerovat to jednou a pro druhe, treti... kolo to jenom o tech n mist rotovat...
No nic, ja tusil, ze tenhle napad neprojde...

[Jirka]

misto te rotace bych z intervalu nahodne generovanych cisel vyradil ty co padla a cisla v intervalu +/- n kolem minule vygenerovane hodnoty.

[kaaja]

to se ovsem muzete dostat do siuace, kdy bude zbyvat par poslednich cisel a ty uz nepujdou umistit.

[Jeason]

myslim ze ta situace nemuze nastat

[kaaja]

Kdyz budu mit 6 zavodniku ABCDEFG a jejich poradi v prvmin zavode bude:

A - 1, B - 2, C - 3, D - 4, F - 5, G - 6 

A dalsi poradi zacnu generovat, tak aby nebyla hned vedle sebe

A - 3, B - 4, C - 1, D - 2

Tak mi pro zadovniky F a G zbyla pouze 5 a 6 pozice a to by bylo hned vedle minule pozice a tim to porusi zadani

[Jeason]

koukam ze jste si dal praci to vymyslet. máte pravdu,ale pokud by toto melo byt v kazdem pripade nahodneho rozmisteni zavodniku, tak je to neresitelny. ackoliv si myslim ze bude jen par kombinaci kdy to nepujde.
jde o to vymyslet jen jak na to. a proto jsem psal do teto diskuze.

[kaaja]

Ok uznavam, ze to nastane jev ve specialnich pripadech. Ja chtel jenom upozornit na to, ze se to musi spravne osetrit. Zatim vsechny programy co tu kdo napsal by se pri vhodne konstelaci hvezd na tomhle problemu zasekly.

[Jeason]

to zcela souhlasim. ale musim ocenit snahu nastinit i zdrojovy kod i v jinem jazyce. napadlo me vytrotit jen jedno pole (nahodne) a protocit obsah pole vzdy o x dopredu a tim ziskam druhe startovni pozdice a to same udelat s treti pozici a prozmenu to protocit pospatku zase o x. co myslis bylo by to reseni?

[kaaja]

Pokud bude to x mensi nez 1/3 poctu zavodniku tak to bude urcite ulohu splnovat, ale otazka ovsem je jestli se bude zdat zadavatelum takto vytvorene poradi dostatecne nahodne.

Jinak pro ostatni. Ten problem vubec neni jednoduchy, Kdyz se nad tim clovek zamysli, tak zjisti, ze se to dost podoba sudoku - musim umistit nejaka cisla do radku - jednotlivych startu, ale musim mit zachovana nejaka pravidla i ve sloupeccich - vzdalenost startovnich poradi. A vytvaret sudoku neni pokud se nepletu zadna sranda.

[Jeason]

no nepsal jsem to ale for je v tom ze celkem bude 300 mist odkud bude start. ale rozdeleny ve 3 usecich (A,B,C) od 1 - 100. takze v podstate kazdy zavodnik dostane cislo trikrat. ale nebude stejny. udela li se jedna nahodne zgenerovana rada. a ostatni B a C startovni pozice se vypocitaji prictenim ci odectenim nejakeho cislo X tak to mame jednoduzsi.
problem bude v tom aby se nam nahodne neudelali cisla : 1,2,3,4,5, 35,36,37,38,6,7,8,9,10, ... .
jinak dekuji ze jsi nastinil problem i pro ostatni. ;)

[Jeason]

no nepsal jsem to ale for je v tom ze celkem bude 300 mist odkud bude start. ale rozdeleny ve 3 usecich (A,B,C) od 1 - 100. takze v podstate kazdy zavodnik dostane cislo trikrat. ale nebude stejny. udela li se jedna nahodne zgenerovana rada. a ostatni B a C startovni pozice se vypocitaji prictenim ci odectenim nejakeho cislo X tak to mame jednoduzsi.
problem bude v tom aby se nam nahodne neudelali cisla : 1,2,3,4,5, 35,36,37,38,6,7,8,9,10, ... .
jinak dekuji ze jsi nastinil problem i pro ostatni. ;)

[Jeason]

prosimte nemas icq ?

[Tomáš]

Nebylo by jednoduší naplnit n rozměrné pole čísly <1-n> (event. si tam ještě přidat ty rozestupy (násobkem)) a pak je nějak v poli náhodně rozházet?

[lukas.ramlich]

Programování není o tom, psát svoje dotazy do diskuse, aby je někdo řešil za tebe. Programování je o tom, snažit se problém vyřešit sám. Třeba blbě, ale sám. V diskusi se ptej jen na věci, které se opakují, můžou být přínosem pro ostatní a které třeba už někdo řešil.

Jestli se na to necítíš, můžeš vždycky jít dělat něco jiného.

Nikde v tvém dotazu nevidím "udělal jsem to takhle, ale...", "hledal jsem tady a tady, našel jsem tohle a tohle, ale...". Ty jsi asi tak línej, žes nic nezkoušel a zatepla jsi běžel na diskusi, aby to za tebe někdo vyřešil. Není ti trochu stydno?

Divím se ostatním že vůbec radí, za vás taky nikdo neřeší vaše úkoly.

[tulpik]

Plne souhlasim. I kdyz k tematu: Nejak nechapu na co databazi :DD Copak ti nestaci _jedno_ pole? A generevani, mno jako kdyz chces generovat pozice pro 3 zavodniky, pri cemz musi stat nejmene 3 a maximalne 5 policek od sebe, tak teda moc moznosti nemas :DD No a nejlepsi bude asi pouzit random a kapku improvizace.

[Jeason]

no databazi jsem pouzil bych v ni mel ulozeny vysledky vygenerovyho poradi.
nechci generovat pro 3 zavodniky. chci generovat pro 300 zavodniku a ve 3 zavodnich polocasech (jine rozmisteni) a nemelo by se mi stat ze vygeneruju treba pro zavodnika pozice 25,25,25. pokazdy by to melo byt jinak.

prez to pole me to taky napadlo,ale nedokazu si predstavit jak porovnavam ze jsou startovni pozice od sebe.

[Petr]

Databáze je blbost. Buď celý v (PL/)SQL nebo nic. Musí stačit pole.

DATA:
 - array_of_positions = array(
    runner => position
   );

// generate positions for the first loop
* FOR (i) IN 1 TO {x}:
   * DO
      * generate new valid position by random -> (p)
   * WHILE position (p) is occupated (array_of_positions)

   * (array_of_positions)[(i)] = (p)
* DONE

(first_loop_positions) <- (array_of_positions)

// generate positions for second loop
* FOR (i) IN 1 TO {x}:
   * DO
      * generate new valid position by random between
        ( (first_loop_positions)[i] - {n / 2} ) and ( (first_loop_positions)[i] + {n / 2} ) -> (p)
        // constraint: valid bounds
   * WHILE position (p) is occupated (array_of_positions)

   * (array_of_positions)[(i)] = (p)
* DONE

Notes:
V kulatých závorkách je proměnná, ve složených závorkách je parametr (např. vstup od uživatele...)

[Jeason]

nic ve zlem ale prizpevky tveho typu strasne miluju! nejvice na tom jak delaj lidi z druhych blbecky a lemry liny!
ja kdyz neco nevim tak to klidne priznam. a jestli jsi si nevsiml tak na zacatku je psano ze budu rad za kazdou radu jak to resit. ty ses mozna einstain a z huby ti skacou moudra. ale to si nech prosimte pro nehoko jinyho.
a jestli ti vati moje reakce, tak sem nechod, me tvoje reakce prince dost vysmesna :(

[Michal Kubeček]

Já zase miluju lidi, kteří se vrhnou do něčeho, čemu absolutně nerozumějí (ve vašem případě je to programování) a místo toho, aby se do problematiky snažili proniknout, nechají své úlohy za sebe řešit druhé. A když si je někdo dovolí slušnou formou upozornit, že takové chování není přiliš korektní, začnou nadávat a kopat kolem sebe.

Nevím, kde se ta vaše úloha vzala, napadají mne tři možnosti. Buď je to do školy, na kšeft, nebo jste přecenil své síly a slíbil kamarádům vyrobit něco, co nezvládáte. Ať je to tak nebo tak, připadá mi váš postup morálně pochybený. Vaše reakce na příspěvek Lukáše Ramlicha je pak naprosto neomalená (nemluvě o tom, že je vinou vaší lenosti skoro nečitelná).

Doufám, že snesete mou upřímnost. Pokud ne, nedá se nic dělat…

[Jeason]

ja sem nerekl at to za me nekdo udela. to tady celou dobu tvrdite Vy. (ale nevim kde ste na to prisel,ale urcite neco vymyslite abyste se do me mohl navazet)
ja nejake sve reseni mam,ale nestaci na to abych udelal co potrebuji. programovani me osobne problem nedela,ale nedokazu tento priklad logicky vymyslet. prevedeni do jakohokoliv jazyka uz je druha cast.

jinak se nedivim ze tady tolik vysilujete s tim co kdo umi nebo ne. ale vy na tom o moc lip nebudete protoze mistot ztraceni castu tim co zde pisete jste mi mohl poradit. casu by to zapralo uplne stejne, jen to chce mit v hlave v poradku abyste to mohl napsat.

[skonciljsem]

Tos teda trefil. Ty sem nechodíš moc často, co?

[Jeason]

ne moc casto ne,vetsinou neresim takovehle extremni proklady,ale za tu dobu co jsem tady obcas mel nejaky dotaz tak jsem si vsiml ze je tu spis hodne lidi co se nezabejva programovanim (linuxem) ale jen cistou diskuzi o necem - nicem :))

[tupik]

A to ma byt argument k tve lenosti? :DD

[Jeason]

mas na mysli nejaky argumet konktertne? nebo tatris k tem co hodne hovori a nicem a jde jim to dobre? pokud jo tak ses minul povolanim a mel bys jit do politiky, takovych je tam hodne.

a pokud k nim nepatris tak mi rad k veci poradis nebo ne? :o)

[tulpik]

Ach ta cestina XD, proc bych ti mel radit? Ja sam osobne si myslim, ze na tom neni nic slozityho, takze neni duvod radit s domacima ukolama, me taky nikdo neradil, hold budes muset asi zacit pouzivat mozek, za tu dobu co se tu pres o to kdo ma a nema pravdu, kdo je a neni linej, uz si to mohl mit napsany imho 10x. Teda pokud na to mas, pokud ne, nechapu proc to delas.

[Michal Kubeček]

ale nevim kde ste na to prisel,ale urcite neco vymyslite abyste se do me mohl navazet

Ó, běda. Jsem odhalen. Jediný důvod, proč chodím na ABCLinuxu, je ten, abych se do vás mohl navážet…

ja nejake sve reseni mam,ale nestaci na to abych udelal co potrebuji. programovani me osobne problem nedela,ale nedokazu tento priklad logicky vymyslet. prevedeni do jakohokoliv jazyka uz je druha cast.

Ale to právě je podstata programování. Vymyslet vhodnou reprezentaci dat a algoritmy pro práci s nimi. Ne v tom, kam napsat středník nebo složenou závorku. Naučit se syntaxi programovacího jazyka zvládne kdokoli, podstatné je umět ten jazyk používat. Když se naučíte francouzská slovíčka, nestanete se tím Balzacem nebo Villonem; koupíte-li si kopačky, nestává se z vás tím fotbalista… Vám chybějí základy algoritmického uvažování a to se nedá spravit radou ve fóru, to chce studium.

jinak se nedivim ze tady tolik vysilujete s tim co kdo umi nebo ne. ale vy na tom o moc lip nebudete

Sice netuším, na základě čeho jste to usoudil, ale na tom nezáleží. Nevzpomínám si, že bych mezi svými klienty měl někoho s vaším jménem, takže je mi celkem jedno, co si o mých schopnostech myslíte.

protoze mistot ztraceni castu tim co zde pisete jste mi mohl poradit. casu by to zapralo uplne stejne, jen to chce mit v hlave v poradku abyste to mohl napsat.

To je otázka přístupu. Za ztracený čas bych totiž považoval spíše to, kdybych se vám psal s řešením. Protože jediný efekt by byl ten, že byste zjistil, že tohle je dobrý způsob, jak na problémy "řešit" a až byste příště potřeboval zase něco naprogramovat, hodil byste to zase na fórum. A jinak se na ten dotaz odpovědět nedá, leda: "Jděte a studujte."

Všimněte si ale jedné maličkosti: přestože jsem váš dotaz považoval za nevhodný, nijak jsem na něj nereagoval. Nechal jsem to být, ať si každý sám rozhodne, zda chce vaši práci dělat za vás. Ozval jsem se teprve v okamžiku, kdy jste se neurvale obořil na kolegu, který vás slušně upozornil, že ten dotaz se do fóra nehodí.

[Jeason]

tak dlouhej text a a je tu uplne na nic! :D

[Michal Kubeček]

To je ovšem škoda. Asi jsem naivní, ale trochu jsem doufal, že si z toho aspoň něco vezmete. Není každý den posvícení…

[Jeason]

to me mrzi,ale treba zitra bude lepsi den :)) ne vazne, ja nepotrebuju tu omacku kolem a kolem, potrebuju poradit jak to mam resit a ne rady typu kdyz nevis nedelej to. to dekuju.

[Michal Kubeček]

Nešlo o "když nevíš, nedělej to", ale o "když to neumíš, nauč se to". No nic, jak správně podotýkáte, třeba zítra budete mít lepší den…

[Hynek (Pichi) Vychodil]

Ano, zdá se že na nic, protože jste ho nepochopil, ale třeba ho pochopí někdo jiný a tak úplně na nic nakonec nebude.

[Jeason]

ne ten text k tematicke otazce bubec neopovida a je ciste obecny. (ale to jsou jiste vsem zname veci,ktere zde neresim)

[vencour]

Nejsem si jist, zda chápete, kdo je tu mimo.

[Jeason]

pro kazdeho je ztrata casu neco jineho, nekdo se bavi tim jak buzeruje ostatni Vidte?!<

[vencour]

Ti, co něco umí, něco pochopit těžko nedokážou.

[lukas.ramlich]

No jestli máš problém s takovouhle trivialitou, tak fakt nevím. Možná si myslíš, že programování znamená "převod hotového algoritmu do toho či onoho jazyka". To je bohužel omyl.

To tě opravdu nenapadlo to nejstupidnější řešení? Většina problémů má nějaké rychlé řešení, vymýšlet optimalizace nebo optimální algoritmus lze pozdějí. Že tě nenapadlo vůbec nic a musíš plakat na diskusi, to asi něco znamená.

Stupidní řešení "na první pohled" je toto:

- vygeneruju tři pole od 1 do N - všechny pole náhodně promíchám - projedu pozice "nad sebou" (což jsou pozice jednoho závodníka, daného indexem pole), zda odpovídají podmínce (minimální vzdálenost) - pokud ne, "nějak" je prohodím s okolím (najít vtipný způsob prohození nechám na tobě) - pokud byl prohoz, opakuju kontrolu pozic

Ale možná bys měl vážně použít databázi. Třeba by se tvůj geniální algoritmus dočkal zveřejnění na http://www.thedailywtf.com :)

[Jeason]

ja si myslim ze se db pouzije pro ulozeni vysledku nahodnyho generovani pozic. udela se nekolik generovani a potom se sahne po jednej.

[©]

Tak tady se mi zacyklil mozek:

všechna pole náhodně promíchám

...

[Jeason]

jo cyklu tu bude asi hafo :)) protoze jsem prisel na to ze se budou muset genrovat vsechny 3 variianty. jina by zavodnici byly pokazdy za sebou ve stejnym poradi :(

[Jakub Hájek]

ja nejake sve reseni mam,ale nestaci na to abych udelal co potrebuji. programovani me osobne problem nedela,ale nedokazu tento priklad logicky vymyslet. prevedeni do jakohokoliv jazyka uz je druha cast.

Myslim, ze programovani je hlavne o tom " to logicky vymyslet". To ze v tomhle jazyce se podminka dela tak, v tomhle se cyklus dela onak a syntaxe jineho je uplne odlisna, to ze tenhle jazyk dovoluje ukazatale nebo kerursi a tenhle ne, je vec dle meho nazoru vedlejsi.. Naucit se to je jako naucit se jakykoliv jiny jazyk. Treba madarstinu. Ale k programovani to nestaci.

[Jeason]

programovani je hlavne o tom " to logicky vymyslet" a prevect do programu. souhlasim

[herhor]

co takhle:

1) vygeneruj náhodnou permutaci 2) vyber náhodně dva závodníky, kteří jsou od sebe vzdáleni alespoň k, prohoď jejich místa (při dalším výběru už je nevybírej) - tohle opakuj N/2 krát

[©]

Asi to nebude presne to ono, ale je to rozhodne zajimave: RANARRAY

[Peter Figura]

Ako si vobec dovolujes sem dat link na anglicky text ? Koledujes si o takuto reakciu

[Jeason]

vtipalku, jeste ze jsem to tam napsal vid? :))

[juk]

Tohle je ale generátor náhodných čísel, to je tazateli k ničemu.

[Pmx]

Možná by to šlo udělat podobně, jako tu nedávno někdo (nejen) v blogu řešil Sudoku - ten hlavolam teda rád moc nemám, ale zadání mi přijde podobný. Zkoušet možnosti postupně u jednotlivých závodníků a když se všechny vyplácají, vrátit se na předcházejícího, změnit a znova zkoušet. Ale je to jen takový nápad.

[podlesh]

Problém je, že algoritmus spoléhající na to, že se "to jednou povede" vlastně prohledává celý stavový prostor, tedy má složitost minimálně O(N!) (při skutečně náhodných číslech není vůbec zaručeno ukončení algoritmu!). Při počtu závodníků 300 je to 300! , což je číslo... opravdu velké. Jistě, je to jen horní hranice. Ale zaručuji že zrovna když bude potřeba rychle vygenerovat pořadí, bude to generovat miliardy špatných řešení (Murphy).

Vygenerování jednoho pořadí je triviální, již zde bylo několik dobrých odkazů. Stačí jedno pole, cyklus 1 až N-1 (N=počet závodníků) a provádět swap.

Generovat další pořadí, kdy tam je navíc podmínka minimální vzdálenosti od předchozích, již vůbec triviální není. Lze prostě stejným způsobem vygenerovat pořadí a zjistit zda vyhovuje, ale to se může neúměrně protáhnout.

Je tedy nutné vzít v úvahu, že při druhém umísťování má každý závodník až o 5 možností méně (minimálně 3 pro závodníky na krajích pozicích). Obecně, 2D-1 (D je minimální požadovaná vzdálenost mezi pozicemi, D>0). V dalším umisťování je to dokonce až dvakrát tolik, tedy 10 (4D-2).

Algoritmus tedy musí brát v úvahu, že každý závodník má omezený počet pozic. Navrhoval bych tedy u každého evidovat kolik pozic mu ještě zbývá a při každém generování kromě prvního jim pozice přidělovat v pořadí podle počtu možností. Myslím že rozvinutím úvahy v předchozím odstavi půjde dokázat, že pro určitý maximální počet startů S bude vždy možné všem závodníkům přiřadit pozici. Pak nebude potřeba provádět rollback (tedy začínat znova). Možná ale že nic takového dokázat nejde. Skutečně nemám čas to příliš rozebírat...

Je zde jednodušší alternativa: vygenerovat náhodně jen první pozice, pro další starty provádět jen rotaci. V nejjednodušším případě, tedy rotace o D, musí platit podmínka že D+D*(S-1) = D*S <= N (závodník co začíná na pozici D musí po S-1 posunech skončit nejdále na poslední pozici). Toto by ale závodníci rychle prohlédli a asi by se jim to nelíbilo.

Složitější bezpečná varianta je provádět posuny o náhodnou hodnotu z intervalu <D,(N-D)/(S-1)> (oboje včetně). Opět je zajištěno, že ani v nejhorším případě nedojde k vygenerování nepřijatelné startovací listiny (cvičení: dokažte .

Problém obou rotačních řešení je, že jednotlivé startovací listiny nejsou navzájem nezávislé - tedy, zjednodušeně, nejsou "opravdu náhodné". Samozřejmě že po jejich vygenerování je nutno je navzájem zamíchat.

Nejlepší bude hybridní řešení: Nejprve zkusit startovací listiny generovat náhodnými pokusy a zavrhováním špatných výsledků. Počet pokusů však omezit nějakým empiricky zjištěným rozumným číslem (třeba 100). Pokud počet pokusů vyprší aniž by bylo vygenerování S použitelných listin, použije se výše zmíněný rotační algoritmus.

PS: Doufám že to bude užitečné... A hlavně doufam že jsem nikde neudělal botu a nepíšu ptákoviny.

[Jeason]

urcite moznost,ale mozna by stacilo nahodne vygenerovat pole ( nebo matici) a do dalsich startovnich pozici pridat nahodne generovani s tim ze by se vzalo kazde cislo pole/matice a vygenerovalo se nahodne cislo P=> (N+5) or (N-5). (P je puvodní císlo a N je nove číslo , 5 zastupuje priklad pro minimalni rozestup) pokud je podminka splnena prejde na jine cislo. bylo by ale tyto cisla jiz negenrovat ale cerpat z nejakeho zasobniku cisel a nahodne je vybirat. a pokud podminka neni splneno vybere se nove cislo.

bouzel se da predpokladat ze v kazdem pripade bude vygenerovani takoveto rady cisel s jistou zavilsosti velmi zdlouhave.

[podlesh]

Jistě, o tom jsem psal ve 4. a 5. odstavci. Každá již vygenerovaná startovací listina omezí výběr pozic pro závodníka. Při generování další listiny se pak závodníkovi přidělí pozice náhodným výběrem z těch, co jsou ještě k dispozici. Může se udržovat množina jako zásobník, nebo se může vždy dopočítat - to už je detail. Otázka zní: za jakých podmínek může dojít k tomu, že již závodníkovi žádná možná pozice nezbyde? A hlavně: existují podmínky takové, že k tomu nedojde a vždy bude pro závodníka minimálně jedna volná a přijatelná pozice? Pokud ano, je potřeba tyto podmínky najít a provést důkaz.

bouzel se da predpokladat ze v kazdem pripade bude vygenerovani takoveto rady cisel s jistou zavilsosti velmi zdlouhave.

"Zdlouhavé" ani tak nevadí, pokud ta doba je nějak rozumně omezena, a hlavně pokud je vůbec deterministicky omezena. Náhodně generovat hodnoty tak dlouho, dokud se nevygeneruje akceptovatelná hodnota není dobrý algoritmus. Mám s tím vlastní, špatné zkušenosti.

[Jeason]

Pravda. ono zasobníkem cisel se to bude asi muset resit, protze denerovat nahodna cisla neni logicky ok, pak dostanu n. 5 a n.10 . Tim co si piseme mozna vyresime pri dobre napsanem algoritmu ze nedostaneme stejne cislo startovniho cisla (nazaciname na stejnem miste),ale musim jeste myslet na overeni aby vedle me nezavodili stejni zavodnici do "k" poctu.

Shrneme-li to tak mame 300 soutezicich rozdelenych na 3 drahy (A,B,C) po 100.
Vygenerovani startovni pozice je nahodne,ale na zadne draze nezacinam ze stejneho mista a okolnim (zleva i zprava)k (cca 5 lidi) zavodniku kolem me nesmi byt stejnych (vzajemne napomahani pri zavode apod.)

mozna otazkou je predem si rici kolik je k abychom se vyhnuli moznosti ne-resitelnosti.

krasnou otazkou pro matematiky je kolik muzeme udelat celkem takovych kombinaci rozmisteni zavodniku ???

[podlesh]

Koukám že jsem to zadání původně pochopil špatně.

[KIT]

Nevím sice co to tady blábolíte, ale to je jedno. Já bych postupoval takto: Celé si to představím jako graf. Vrcholy budou účastníci. Hranou budou spojeni ti, kteří se mezi sebou mohou vzájemně prohodit (rozdíl jejich pozic je alespoň předepsaný minimální). V něm pak najít nějaké náhodné perfektní párování (tak, aby každé párování mělo stejnou pravděpodobnost (*)). Dvojice sportovců odpovídající hranám v nalezeném perfektním párování si prohodí místa. Zajistit (*) asi nebude jednoduché, ale dalo by se to udělat přibližně nějak takto: hranám přiřadím náhodně váhy a použiju nějaký algoritmus pro nalezení minimálního p.p.

[podlesh]

Ano, jistě, lze to reprezentovat i takto. A je to dobrý nápad. Jenomže řeší jenom jednu část algoritmu, tedy vygerování nového pořadí jestliže již máme předchozí.

Ale co když perfektní párování neexistuje? Co když dokonce ten graf není spojitý?

Když už grafy, tak kompletně celý problém. Vrcholy účastící v jednotlivých startech (kartézský součin) plus jednotlivé pozice v jednotlivých startech a ještě pomocné vrcholy pro zajištění minimálního rozdílu pozic. Místo perfektního párování samozřejmě barvení. Tak by to snad mohlo jít...ale to jsou stejně jenom bláboly.

[KIT]

První pořadí si můžu vygenerovat zcela náhodně. Na druhé použiju popsaný algoritmus. P.P. existovat bude (při rozumně zvolené minimální vzdálenosti pozic, označme k), protože ten graf bude obsahovat silně regulární podgraf žijící na všech vrcholech. V tomto případě se dá dokázat, že pp existuje. Pojem PP není omezen jen na souvislé grafy. Problém tedy nebude ani v další iteraci algoritmu, protože odeberu hrany párování a zakážu další hrany, každý vrchol bude mít zase stupeň alespoň nějaké n (kladné při rozumně zvoleném k) a nějaký podraf na N vrcholech bude zase silně n-regulární.

Blábolením jsem myslel povídačky o špatných a dobrých algoritmech. Krom toho tohle je krásný případ úlohy, která pravděpodobnostním algoritmem řešit jde.

[podlesh]

No dobře, s tou souvislostí jsem si nepromyslel co píšu... prostě jde jen o to, zda to párování v další iteraci existuje.

Problém tedy nebude ani v další iteraci algoritmu, protože odeberu hrany párování a zakážu další hrany, každý vrchol bude mít zase stupeň alespoň nějaké n (kladné při rozumně zvoleném k) a nějaký podraf na N vrcholech bude zase silně n-regulární.

Toto je sice hezké, ale vůbec to neodpovídá na otázku. Jenom se důkaz přesouvá na nějaké "rozumně zvolené k, kdy každý uzel bude mít stupeň kladný". Takže jsme pořád tam, kde jsme začali.

Blábolením jsem myslel povídačky o špatných a dobrých algoritmech. Krom toho tohle je krásný případ úlohy, která pravděpodobnostním algoritmem řešit jde.

Náhodně generovat hodnoty tak dlouho, dokud se nevygeneruje akceptovatelná hodnota není dobrý algoritmus.

Aha. Prosím osvětlit, rád se poučím.

[KIT]

Prostě, když budu zakazovat jiným způsobem - sportovci jsou rozmístěni jakoby na kružinici (1 až N, n-tý a první jsou sousedé) a každému zakážu mít pozice v k-okolí. Takže z grafu odeberu 2k hran každému vrcholu, tedy bude (N-2k)-regulární. To jsem tedy zakázal moc, prvních a posledních k jich má zakázáno víc. Tak tam ty hrany odebrané navíc zase vrátím. Nyní už ale každý vidí, že mám ten (N-2k)-regulární podgraf a mám zajištěnou existenci PP, pokud k < N/2. Pokud chci pokračovat do další iterace musí být k < N/4.

[podlesh]

Prostě, když budu zakazovat jiným způsobem - sportovci jsou rozmístěni jakoby na kružinici (1 až N, n-tý a první jsou sousedé) a každému zakážu mít pozice v k-okolí. Takže z grafu odeberu 2k hran každému vrcholu, tedy bude (N-2k)-regulární. To jsem tedy zakázal moc, prvních a posledních k jich má zakázáno víc. Tak tam ty hrany odebrané navíc zase vrátím. Nyní už ale každý vidí, že mám ten (N-2k)-regulární podgraf a mám zajištěnou existenci PP, pokud k < N/2. Pokud chci pokračovat do další iterace musí být k < N/4.

Teď vidím že jsem to zadání pochopil trochu jinak, já počítal vzdálenost pozic, ne lidí... i když to je evidentní blbost :-/

[KIT]

První pořadí si můžu vygenerovat zcela náhodně. Na druhé použiju popsaný algoritmus. P.P. existovat bude (při rozumně zvolené minimální vzdálenosti pozic, označme k), protože ten graf bude obsahovat silně regulární podgraf žijící na všech vrcholech. V tomto případě se dá dokázat, že pp existuje. Pojem PP není omezen jen na souvislé grafy. Problém tedy nebude ani v další iteraci algoritmu, protože odeberu hrany párování a zakážu další hrany, každý vrchol bude mít zase stupeň alespoň nějaké n (kladné při rozumně zvoleném k) a nějaký podraf na N vrcholech bude zase silně n-regulární.

Blábolením jsem myslel povídačky o špatných a dobrých algoritmech. Krom toho tohle je krásný případ úlohy, která pravděpodobnostním algoritmem řešit jde.

[Jeason]

nedokazu si predstavit jakym zpusobem se budou dostavat data z grafu. protoze php neba takove moznosti jako MATLAB ve kterem se s grafy da pracovat daleko lepe nez v php..

[podlesh]

Graf je jen matematická reprezentace. Výsledný algoritmus pak vůbec nemusí pracovat s grafem jako s datovou strukturou. Naopak, typicky pak ve výsledku nemusí být vůbec zřejmé že tam nějaký graf je.

[Marek Bernát]

Presne tak, graf je len reprezentácia a grafové algoritmy sa dajú napísať v ľubovoľnom programovacom jazyku (dokonca aj takej oblude ako php).

Ale dovolím si nesúhlasiť, že typicky grafy nie sú vidieť. Práve naopak, všetky klasické algoritmy týkajúce sa ciest, párovania, atď sú vidieť na prvý pohľad (ak to teda niekto neimplementuje z nejakých vlastných pohnútok úplne úchylne).

[Jeason]

nedokazu si predstavit jakym zpusobem se budou dostavat data z grafu. protoze php neba takove moznosti jako MATLAB ve kterem se s grafy da pracovat daleko lepe nez v php..

[Marek Bernát]

Zrejme došlo k nedorozumeniu, pretože z tvojho príspevku to vyzerá, že za graf považujš diagram znázorňujúci nejakú funkčnú závislosť, alebo nejakú štatistiku.

V informatickom kontexte je však graf implicitne chápaný ako niečo úplne iné a obávam sa, že tento problém bez skúsenosti s grafmi určite správne nevyriešiš. A teda ani tie pekné príspevky o párovaní ti asi nič nedali.

[jekub]

Pokud jsem správně pochopil zadání, tak bych postupoval asi takto:

Postupně každému závodníkovi v každém kole přidělím náhodně jednu z (pro něj) neobsazených drah (nemá smysl náhodně vybírat už z obsazených). Dráha je pro závodníka obsazena, pokud splňuje alespoň jednu z podmínek:

1. v tomto kole už je přidělena

2. v některém z předchozích kol měl dráhu +/- N míst

3. pokud dráhu přidělím, nebude možné řešení

Typ 1 a 2 jsou jasné, typ 3 je splněn, pokud je vybraná dráha prvkem průniku obsazených drah typu 1 a 2 dosud nezařazených závodníků.

Složitost je O(n), nemusím složitě testovat počáteční podmínky (neřešitelnost vyplyne z algoritmu), jako oříšek mi to nepřipadá.

Jen doufám, že pokud Vám cokoli z této diskuse pomůže k řešení, nezapomenete uvést abclinuxu jako zdroj informací.

[kaaja]

Jenom se chci zeptat zda jsem dobre pochopil typ 3. Podivam se na drahu a budu prochazet vsechny neobsazene zavodniky a kdyz pro vsechny tyto zavodniky splnuje podminky 1 a 2 tak ji vezmu?

[Shteffi]

Zdravim. Sice jsem nečet těch 70 příspěvků o tom jak se tu někdo hádá.. ale k problému. Nejsem matematik abych tu nastínil elegantní matematicko-logické univerzální řešení, ale použil bych na to jednoduše selskej rozum.

1) 300 lidí rozlosuju do náhodného pořadí. (na to ta funkce rand() bude stačit.)

2) Pak to pořadí rozdělim na 3 skupiny A B C.

3) v první dráze necham skupiny zasebou jak sou. v druhý dráze dám pořadí skupin B C A. ve třetí dráze dám pořadí skupin C A B.

Timhle vznikne rodělení skupin tak jak potřebuješ nikomu se nestane aby mu kolidoval start na kařdý dráze a nemusíš nic složitě počítat..

Element rozlosování tam je a fertig.

[Shteffi]

sorry nějak se mi tam vloudily ty 3 dráhy, ale na principu to nic nemění.

[Jeason]

diky ta pokus ale precti si ty prsipevky, to co navrhujes tak poradi tak porad poradi bude stejne jen se prohodi poradi odstartovani na draze. ale naresi to to ze zavodnico budou vedle sebe.