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:

var $numbers = [2,3,6,8,11,25,29,41,52];
var $check = 96;

var $finish = [];

// a végeredmény pl:

for(var $i in $numbers) {
	// itt lenne a logika
	
	$temp.push($numbers[$i])
	// ha megvan a logika, hogy milyen számokat teszek össze egy ciklusban, pl: $temp = [2,3,6]...
	
	$amount = 0;
	// itt akár egy do-while-lal is lehet persze...
	for(var $j in $temp) {
		$amount += $temp[$j];
		if($amount == $check) {
			break;
			$finish.push($temp);
		}
	}
}

$finish = [
	[3,41,52],
	[11,11,11,11,11,11,11,11,8],
	[29,29,8,6,6,6,6,6],
	// és itt lenne a többi találat
];
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:
function subset(arr, n) {
  // triviális eset, ha egy elem maradt
  if (arr.length == 1) {
    // ha pont a keresett szám, akkor egy féle képpen állhat elő: vesszük pont a kiválasztott számot
    if (arr[0] == n) return [[n]];
    // ha nem, akkor sehogy sem lehet előállítani
    return [];
  }
  // a lista első elemét a variációba bevéve a lehetséges megoldások
  var included = subset(arr.slice(1), n - arr[0]);
  // a lista első elemék kihagyva a lehetséges megoldások
  var excluded = subset(arr.slice(1), n);

  // csak az előbbi listához kell hozzáfűzni az első elemet
  for (var i in included) {
    included[i].push(arr[0]);
  }

  // az eredmény a két lista összefűzve
  return included.concat(excluded);
}
Ha érdekel, itt van egy ekvivalens egysoros változat:
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.
(function(){
	var
		$input = [2,3,6,8,11,25,29,41,52],
		$target = 96,
		$results = [],
		$trees = [],
		cycles = 0;

	function SumTree(input, target, parent){
		var
			that = this;

		this.value = input[0];
		this.children = [];
		this.parent = parent;
		this.registerResult = registerResult;

		init();
		function init(){
			if(that.value < target){
				while(input.length){
					//if(cycles++ > 10000) return;
					//console.log(that.value, target, input.length);
					that.children.push(new SumTree(input.slice(0),target-that.value,that));
					input.shift();
				}
			}else if(that.value == target){
				that.registerResult([]);
			}
		}

		function registerResult(result){
			result.unshift(that.value);
			if(that.parent){
				that.parent.registerResult(result);
			}else{
				$results.push(result);
			}
		}
	}

	while($input.length){
		console.log('e',$input.length);
		$trees.push(new SumTree($input.slice(0), $target, null));
		$input.shift();
	}
	console.log('done');

	console.log($results);
})();
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)