ugrás a tartalomhoz

Tömb permutáció / értékek hasonlítása

szobek · 2016. Aug. 19. (P), 18.24
Sziasztok!

Egy érdekes kérdéssel keresett meg egy barátom. Készítsek Neki egy szkriptet, ami egy adott tömbben lévő számokból kikeres minden olyan varáíciót, amelynek az összege egyenlő egy meghatározott számmal. Egy példa, hogy mire gondolok:
  1. var $numbers = [2,3,6,8,11,25,29,41,52];  
  2. var $check = 96;  
  3.   
  4. var $finish = [];  
  5.   
  6. // a végeredmény pl:  
  7.   
  8. for(var $i in $numbers) {  
  9.     // itt lenne a logika  
  10.       
  11.     $temp.push($numbers[$i])  
  12.     // ha megvan a logika, hogy milyen számokat teszek össze egy ciklusban, pl: $temp = [2,3,6]...  
  13.       
  14.     $amount = 0;  
  15.     // itt akár egy do-while-lal is lehet persze...  
  16.     for(var $j in $temp) {  
  17.         $amount += $temp[$j];  
  18.         if($amount == $check) {  
  19.             break;  
  20.             $finish.push($temp);  
  21.         }  
  22.     }  
  23. }  
  24.   
  25. $finish = [  
  26.     [3,41,52],  
  27.     [11,11,11,11,11,11,11,11,8],  
  28.     [29,29,8,6,6,6,6,6],  
  29.     // és itt lenne a többi találat  
  30. ];  
A probléma, hogy a logikát szeretném megérteni, de mindig megakadok ott, hogy túl sok ciklus lenne, és még csak nem is működik rendesen a kód. Nem feltétlenül szeretnék komplett megoldást kérni, csak egy kis segítséget, hogy hogyan álljak neki? :)

Előre is köszönök minden választ és segítséget :)

Üdv:
Szobek
‹ jQuery EasyUI - Lassú oldalbetöltés HTML szerkezet ›
 ■
1

A megoldandó feladat

MadBence · 2016. Aug. 20. (Szo), 01.15
A megoldandó feladat tulajdonképpen a részösszeg probléma, ami egy NP-teljes probléma, így sokkal jobb algoritmust nem is remélhetünk annál, mint hogy végignézzük az összes lehetséges választást. Egy ciklussal vagy rekurzióval meg lehet oldani, ez a rekurzív változat:
  1. function subset(arr, n) {  
  2.   // triviális eset, ha egy elem maradt  
  3.   if (arr.length == 1) {  
  4.     // ha pont a keresett szám, akkor egy féle képpen állhat elő: vesszük pont a kiválasztott számot  
  5.     if (arr[0] == n) return [[n]];  
  6.     // ha nem, akkor sehogy sem lehet előállítani  
  7.     return [];  
  8.   }  
  9.   // a lista első elemét a variációba bevéve a lehetséges megoldások  
  10.   var included = subset(arr.slice(1), n - arr[0]);  
  11.   // a lista első elemék kihagyva a lehetséges megoldások  
  12.   var excluded = subset(arr.slice(1), n);  
  13.   
  14.   // csak az előbbi listához kell hozzáfűzni az első elemet  
  15.   for (var i in included) {  
  16.     included[i].push(arr[0]);  
  17.   }  
  18.   
  19.   // az eredmény a két lista összefűzve  
  20.   return included.concat(excluded);  
  21. }  
Ha érdekel, itt van egy ekvivalens egysoros változat:
  1. const subset = ([h, ...t], n) => t.length == 0 ? h == n ? [[n]] : [] : [...subset(t, n - h).map(a => [...a, h]), ...subset(t, n)];  
Ez a sima kombináció (mert a tömb minden eleme csak egyszer szerepelhet benne, és az elemek sorrendje lényegtelen, hiszen összegre vagyunk kíváncsiak), az ismétléses kombináció kicsit bonyolultabb, hiszen potenciálisan végtelen számú megoldás létezik (pl a [-1, 1] listából a 0-t akárhány féle képpen elő tudjuk állítani, csak ismételgetni kell őket), szóval ott érdemes valamilyen méretkorlátot is bevezetni (vagy az inputra valamilyen megkötést adni, pl negatív számokat nem megengedni).
2

Szia! Köszönöm a segítséget,

szobek · 2016. Aug. 22. (H), 08.07
Szia!

Köszönöm a segítséget, de igen, olyan kéne, amiben lehet ismétlődés, ahogy a példában írtam, de azért köszönöm a kódodat, legalább van miből kiindulnom :)

Üdv
3

én valami ilyesmire

szabo.b.gabor · 2016. Aug. 22. (H), 14.39
én valami ilyesmire jutottam.. hogy tényleg jó-e nem tudom, ha van kérdésed, megpróbálok válaszolni.
  1. (function(){  
  2.     var  
  3.         $input = [2,3,6,8,11,25,29,41,52],  
  4.         $target = 96,  
  5.         $results = [],  
  6.         $trees = [],  
  7.         cycles = 0;  
  8.   
  9.     function SumTree(input, target, parent){  
  10.         var  
  11.             that = this;  
  12.   
  13.         this.value = input[0];  
  14.         this.children = [];  
  15.         this.parent = parent;  
  16.         this.registerResult = registerResult;  
  17.   
  18.         init();  
  19.         function init(){  
  20.             if(that.value < target){  
  21.                 while(input.length){  
  22.                     //if(cycles++ > 10000) return;  
  23.                     //console.log(that.value, target, input.length);  
  24.                     that.children.push(new SumTree(input.slice(0),target-that.value,that));  
  25.                     input.shift();  
  26.                 }  
  27.             }else if(that.value == target){  
  28.                 that.registerResult([]);  
  29.             }  
  30.         }  
  31.   
  32.         function registerResult(result){  
  33.             result.unshift(that.value);  
  34.             if(that.parent){  
  35.                 that.parent.registerResult(result);  
  36.             }else{  
  37.                 $results.push(result);  
  38.             }  
  39.         }  
  40.     }  
  41.   
  42.     while($input.length){  
  43.         console.log('e',$input.length);  
  44.         $trees.push(new SumTree($input.slice(0), $target, null));  
  45.         $input.shift();  
  46.     }  
  47.     console.log('done');  
  48.   
  49.     console.log($results);  
  50. })();  
4

Szia! Egy pár tesztet

szobek · 2016. Aug. 22. (H), 15.21
Szia! Egy pár tesztet futtatva arra jutottam, hogy istenkirály vagy :) Egyenlőre nagyon jónak tűnik! :) Szóval köszönöm szépen a segítséget! Egyszer majd meghálálom ha tudom! (sör, whiskey, stb :D)