Autor | Zpráva | ||
---|---|---|---|
kabanos Profil * |
#1 · Zasláno: 11. 1. 2014, 13:21:23
Ahoj,nevíte jak z několika (různý počet, obvykle v rozmezí 2-30 polí) jednorozměrných polí vybrat vždy z každé jeden náhodný prvek tak, aby se vybrané prvky neopakovaly? Každé z polí má různý počet členů, vždy alespoň jeden. Výběr je vždy nutné provést ze všech použitých polí (v příkladu je jich 5). Stačí najít jedno libovolné řešení. Samozřejmě to může znamenat i to, že řešení neexistuje -> chybová hláška.
příklad data1 = ['a','b','c','d','e','f']; data2 = ['b','c','d']; data3 = ['a','b','c','d','e','f','g','h','i']; data4 = ['d','e']; data5 = ['e']; možná řešení např: a,b,c,d,e b,c,a,d,e PS: v příkladu je jasné, že z data4 bude vždy řešením jen písmeno d vzhledem k data5, kde je jen e, které vzhledem k neopakování se vybraných dat eliminuje e při výběru z ostatních polí. Myslím, že je to snad srozumitelné. Díky za cokoli podnětného, lépe i konkrétního. |
||
juriad Profil |
Matematika: http://cs.wikipedia.org/wiki/Hallova_v%C4%9Bta
Hledej systém různých reprezentantů nebo raději anglicky system of distinct representatives nebo marriage theorem Nejjednodušší je zkusit zafixovat prvek z prvního pole, odebrat jej z ostatních polí a zavolat se rekurzivně nad zbytkem. Není to nejspíš příliš efektivní. |
||
kabanos Profil * |
#3 · Zasláno: 11. 1. 2014, 14:17:15
juriad:
> Nejjednodušší je zkusit zafixovat prvek z prvního pole, odebrat jej z ostatních polí a zavolat se rekurzivně nad zbytkem. > Není to nejspíš příliš efektivní. Takto se o to asi pokusím. Jen by se to asi zefektivnilo, kdyby se mi podařilo procházet jednotlivá pole seřazená podle počtu členů v nich, od nejméně po nejvíce, v mém příkladu začít od data5,data4,data2,data1,data3. Názvy prohledávaných polí (promnných), tím myslím data1-5 mám uloženy v samostaném poli. Jak jejich pořadí v něm zpřeházet podle jejich velikostí (počtu členů)? |
||
_es Profil |
#4 · Zasláno: 11. 1. 2014, 14:21:29
kabanos:
„Názvy prohledávaných polí (promnných), tím myslím data1-5 mám uloženy v samostaném poli.“ Prečo? Prečo si do toho „samostatného poľa“ neuložíš už rovno tie polia? Potom by si si ich mohol ľahko zoraďovať podľa hocičoho, trebárs aj podľa ich dĺžky. |
||
juriad Profil |
Mám hotové řešení, které pracuje tím tupým způsobem.
http://kod.djpw.cz/zdbb |
||
kabanos Profil * |
#6 · Zasláno: 11. 1. 2014, 15:02:25
juriad:
„Mám hotové řešení, které pracuje tím tupým způsobem.“ Super,moc díky:-) |
||
juriad Profil |
#7 · Zasláno: 11. 1. 2014, 15:35:21
kabanos:
To však neznamená, že si to nemáš naprogramovat sám. :) V mém kódu je několik míst, která by šla napsat lépe. |
||
Chamurappi Profil |
#8 · Zasláno: 11. 1. 2014, 15:38:53
Reaguji na juriada:
Chybí v něm ošetření pro případ, že prohlížeč nepodporuje indexOf na poli.
|
||
juriad Profil |
#9 · Zasláno: 11. 1. 2014, 15:45:55
Chamurappi:
OK, na to jsem nepomyslel; pokud bych chtěl efektivní praktickou implementaci, napsal bych to stejně jinak. Šlo mi spíš o demonstraci algoritmu a při ní je jazyk jen formou zápisu, kterému má rozumět autor (OK, JS moc nerozumím) a publikum. |
||
kabanos Profil * |
#10 · Zasláno: 11. 1. 2014, 22:37:03
Tak teď jsem si to zakomponoval do svého a zjistil, že to nějak nefunguje na čísla nebo co? V čem to je? Díky
var data = [ [1,1,1,3,3,4,4,4,5,5,6,7,8,8], [1,7], [1,1,1,3,3,4,4,4,5,5,6,7,8,8], [1,2,5,5], [2,2,3,3,4,5,5,5,6,8], [1,2,2,4,6,6,8] ]; |
||
juriad Profil |
#11 · Zasláno: 11. 1. 2014, 22:53:20
Čísla se ti tam opakují, nejde podle mě o platné zadání úlohy.
Můj skript nalezne index prvního výskytu a ten odstraní; ostatní výskyty ponechá (řádky 12 -- 14). |
||
kabanos Profil * |
#12 · Zasláno: 11. 1. 2014, 23:31:18
ok,díky
|
||
kabanos Profil * |
#13 · Zasláno: 13. 1. 2014, 15:10:32
Mám ještě doplňující dotaz, šlo by to nějak poupravit na generování všech možných kombinací? Mám totiž dále ve skriptu další podmínky, kterými některé z vygenerovaných kombinací řešení neprojdou -> nové generování. Nových pokusů generování dám omezený počet -> není zajištěno, že při náhodném míchání najdu jiné řešení, i když existuje (vzhledem k random). Potřeboval bych tedy vždy jinou kombinaci čísel při novém spuštění generování s randomize = false. Nebo jen při prvním spuštění vypsat všechny kombinace do nějakého pole.
Díky |
||
juriad Profil |
#14 · Zasláno: 13. 1. 2014, 18:05:10
kabanos:
Samozřejmě, že šlo, není to tak těžké, ukázku mám hotovou. Ještě jsem objevil jednu chybu v původním řešení způsobenou přesunem prvku na konec pole během iterace skrz to pole (ten prvek najde dvakrát a existuje jiný prvek, který nenajde vůbec) Abych ti nekazil radost z tvé vlastní úpravy, zveřejním ukázku až zítra večer. |
||
kabanos Profil * |
#15 · Zasláno: 14. 1. 2014, 00:00:03
Tak s pomocí jednoho ze skriptu na této stránce: http://stackoverflow.com/questions/15298912/javascript-generating-combinations-from-n-arrays-with-m-elements jsem vytvořil toto:
data = [ [1,1,1,3,3,4,4,4,5,5,6,7,8,8], [1,7], [1,1,1,3,3,4,4,4,5,5,6,7,8,8], [1,2,5,5], [2,2,3,3,4,5,5,5,6,8], [1,2,2,4,6,6,8] ]; function arrayUnique(arr) { var a = []; for (var i = 0; i < arr.length; i++) { for (var j = i + 1; j < arr.length; j++) {if (arr[i] === arr[j]) {j = ++i;}} a.push(arr[i]); } return a; } function removeDuplicateElement(arr) { var newArray = new Array(); label: for (var i = 0; i < arr.length; i++) { var tempArray = arr[i].slice(0);; arr[i].sort(); for (var j = 0; j < tempArray.length; j++) { for (var k = j+1; k < tempArray.length; k++) {if (arr[i][j] == arr[i][k]) {continue label;}} } newArray[newArray.length] = tempArray; } return newArray; } function getPermutation(n, arr, divisors) { var result = []; var curArray; for (var i = 0; i < arr.length; i++) { curArray = arr[i]; result.push(curArray[Math.floor(n / divisors[i]) % curArray.length]); } return result; } function arraysToCombine(arr) { for (var i = 0; i < arr.length; i++) {arr[i] = arrayUnique(arr[i]);} var divisors = []; for (var i = arr.length - 1; i >= 0; i--) {divisors[i] = divisors[i + 1] ? divisors[i + 1] * arr[i + 1].length : 1;} var numPerms = arr[0].length; for (var i = 1; i < arr.length; i++) {numPerms *= arr[i].length;} var combinations = []; for (var i = 0; i < numPerms; i++) {combinations.push(getPermutation(i, arr, divisors));} return combinations; } var unique = removeDuplicateElement(arraysToCombine(data)); document.write('počet kombinací: '+unique.length+'<hr>'); for (var i = 0; i < unique.length; i++) {document.write(unique[i]+'<br>');} Přesto prosím i o to tvé řešení. Díky |
||
juriad Profil |
#16 · Zasláno: 14. 1. 2014, 14:04:44
Moje řešení:
http://kod.djpw.cz/sebb Prošel jsem si kód toho tvého. Sice funguje, ale moc elegantní není; postupně vygeneruje všechny možnosti a pak eliminuje ty, které nevyhovují zadání. Zkus si tvůj skript na vstupu: data = [ [1,2,3,4,5,6,7,8,9,10], [1,2,3,4,5,6,7,8,9], [1,2,3,4,5,6,7,8], [1,2,3,4,5,6,7], [1,2,3,4,5,6], [1,2,3,4,5], [1,2,3,4], [1,2,3], [1,2], [1] ]; |
||
kabanos Profil * |
#17 · Zasláno: 15. 1. 2014, 23:11:13 · Upravil/a: kabanos
Ještě asi hloupý dotaz (v rekurzních cyklech nejsem zběhlý), kam mám ve tvém řešení zakomponovat tu mou podmínku, kterou bych potřeboval ověřit při každé jednotlivé vygenerované kombinaci a pokud bude podmínka splněna, generování to ukončí, pokud ne, tak by pokračovalo. Předpokládám, že by to mohlo být ve někde ve funkci srr ihned za results.push(result.slice(0));, ale nedaří se mi generování přerušit a pokračovat dál ve skriptu navazujícímu za spuštěnou funkcí gen().
Díky Nebo alternativně funkci gen spustit vždy jen pro vygenerování jedné další kombinace -> musela by si pamatovat, kde zkončila. Cílem je najít jednu vhodnou kombinaci odpovídající následným podmínkám a pokud nevyhoví otestovat další z kombinací. Rozsah databáze není úpně malý a generování všech kombinací z několika polí vychází do milionů, při nichž se prohlížeč zasekne. Samozřejmě to pak omezím jen na otestování např. 100000 kombinací, čímž se může stát, že řešení v nich nebude. ale lépe omezit a nenajít než zaseknout prohlížeč (skript). Ideální by možná bylo zjistit výpočtem celkový počet kombinací a pak cíleně vygenerovat jen každou x-tou.... |
||
juriad Profil |
#18 · Zasláno: 15. 1. 2014, 23:36:11
Třeba takto; snažil jsem se provést minimum změn. Funkce srr vrací true, pokud našla řešení (a tedy se má okamžitě vynořovat z rekurze) a false jinak (pokračuj ve zkoušení dalších možností. Pole results už není nutné, pokud tě zajímá první řešení; řešení se nalézá v poli result, které slouží jako úscho>vna mezivýsledků.
http://kod.djpw.cz/xfbb |
||
Časová prodleva: 10 let
|
0