Autor Zpráva
kabanos
Profil *
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 *
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
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 *
juriad:
Mám hotové řešení, které pracuje tím tupým způsobem.
Super,moc díky:-)
juriad
Profil
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
Reaguji na juriada:
Chybí v něm ošetření pro případ, že prohlížeč nepodporuje indexOf na poli.
juriad
Profil
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 *
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
Čí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 *
ok,díky
kabanos
Profil *
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
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 *
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
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]
];
Tvůj skript vygeneruje pole o 3628800 prvcích a pak ho celé projde, aby zjistil, že existuje jediné řešení. Můj to zjistí o dost dřív.
kabanos
Profil *
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
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 úschovna mezivýsledků.
http://kod.djpw.cz/xfbb

Vaše odpověď

Mohlo by se hodit

Neumíte-li správně určit příčinu chyby, vkládejte odkazy na živé ukázky.
Užíváte-li nějakou cizí knihovnu, ukažte odpovídajícím, kde jste ji vzali.

Užitečné odkazy:

Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm:

0