Skip to content

Instantly share code, notes, and snippets.

@egorvinogradov
Created February 12, 2013 20:32
Show Gist options
  • Save egorvinogradov/4773119 to your computer and use it in GitHub Desktop.
Save egorvinogradov/4773119 to your computer and use it in GitHub Desktop.
Возвращает все комбинации чисел из массива, дающие в сумме 10.
// Все комбинации чисел из массива, дающие в сумме 10
// getCombinations([2,4,6,5,1]) // -> 4,6 и 4,5,1
function getCombinations(array){
var allCombinations = [];
function getLevelCombinations(arr, indexes){
console.log('combinations > ', stringifyCombinations(allCombinations).split('\n'));
indexes = indexes || [];
var currentCombinations = [];
var objects = indexes.map(function(obj){
return {
index: obj.index,
number: arr[obj.index]
};
});
function indexOf(list, index){
for ( var i = 0, l = list.length; i < l; i++ ) {
if ( list[i].index === index ) {
return true;
}
}
return false;
};
console.log('objects:', JSON.stringify(objects));
arr.forEach(function(el, i){
if ( !indexOf(indexes, i) ) {
var newCombination = objects.slice();
newCombination.push({
index: i,
number: el
});
currentCombinations.push(newCombination);
}
});
console.log('Combinations:\n', stringifyCombinations(currentCombinations));
currentCombinations.forEach(function(combination){
getLevelCombinations(arr, combination);
});
allCombinations = allCombinations.concat(currentCombinations);
}
function stringifyCombinations(combinations){
return combinations.map(function(combination){
return combination.map(function(el){
return el.number;
}).join('-');
}).join('\n');
};
function filterDuplicates(combinations){
var filtered = [];
function inArray(combination, combinations){
for ( var i = 0, l = combinations.length; i < l; i++ ) {
var current = combinations[i];
if ( areArraysEqual( getIndexes(current), getIndexes(combination) ) ) {
console.log(
'Removed duplicate:',
stringifyCombinations([combination]), ' == ',
stringifyCombinations([current])
);
return true;
}
}
return false;
};
function areArraysEqual(arr1, arr2){
return arr1.toString() === arr2.toString();
};
function getIndexes(combination){
return combination.map(function(el){
return el.index;
}).sort();
};
//console.log('zzz', combination)
combinations.forEach(function(combination){
if ( !inArray(combination, filtered) ) {
filtered.push(combination);
}
});
return filtered;
};
function getSumm(arr){
return arr.reduce(function(prev, current){
return prev + current;
});
};
function filterByLength(combinations){
return combinations.filter(function(combination){
return combination.length > 1;
});
};
function filterBySumm(combinations){
return combinations.filter(function(combination){
var numbers = combination.map(function(el){
return el.number;
});
return getSumm(numbers) === 10;
});
};
getLevelCombinations(array); // TODO: refactor
return '\n\nКомбинации:\n' + stringifyCombinations(
filterBySumm(
filterDuplicates(
filterByLength(allCombinations)
)
)
)
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment