Вы можете получить комбинацию из 2 элементов массива, а затем фильтровать/уменьшать их в соответствии с разницей.
Можно выполнить эту работу на JavaScript следующим образом;
Array.prototype.combinations = function(n){
return this.reduce((p,c,i,a) => p.concat(n > 1 ? a.slice(i+1).combinations(n-1).map(e => (e.push(c),e))
: [[c]]),[]);
};
function getAcordingToDiff(a,d){
return a.combinations(2)
.reduce((p,c) => Math.abs(c[0]-c[1]) >= d ? (p.push(c),p) : p ,[]);
}
var arr = Array(30).fill().map((_,i) => i+1); // array from [1,...,30]
console.log(JSON.stringify(arr))
console.log(JSON.stringify(getAcordingToDiff(arr,25))); // diff >= 25
Объяснение:
Таким образом, в центре кода выше, очевидно, лежит функция Array.prototype.combinations. Для тех, кто не знаком с JS, это просто обычная функция, которую мы определяем в прототипе объекта Array (так что теперь у каждого массива есть доступ к этой функции, например, arr.combinations(n)). Но давайте использовать более выразительный язык и реорганизовать вышеупомянутый набор комбинаций метод в общую функцию.
function combinations(a,n){
var sa;
return a.reduce(function(p,c,i,a){
if (n > 1) sa = combinations(a.slice(i+1), n-1).map(e => (e.push(c),e));
else sa = [[c]];
return p.concat(sa);
},[]);
}
Так как вы заметите combinations(a,n) рекурсивная функция, которая принимает массив a и число пунктов n. Он работает на основе сохранения первого элемента входного массива и рекурсивного вызова самого себя с помощью одного элемента более короткого массива, combinations(a.slice(i+1), n-1), и с одним меньшим количеством элементов подсчитывается до n уменьшается до 1, и в этом случае он начинает цикл возврата с тем, что осталось от входной массив и каждый элемент обернут в массив, sa = [[c]].
Итак, в цикле возврата рекурсивных вызовов мы берем результирующий массив и нажимаем сохраненный первый элемент (помним -> Он работает на основе сохранения первого элемента входного массива) в каждый элемент возвращаемого массива (помните -> ... и каждый элемент обернут в массив, sa = [[c]]).
Так вот оно ... Вы должны уметь выяснить подробности.
Однако в нашем приложении нам задан массив чисел, и мы попросили получить только 2 комбинации товаров с определенной разницей. В этом конкретном случае нам не нужно вычислять все комбинации, а затем фильтровать их. Мы можем сделать это на пути построения наших комбинаций.По мере увеличения требуемой величины разности d это приведет к огромному усилению по сравнению с методом фильтрации, так как теперь, когда d становится больше, мы устраняем все больше и больше двух комбинаций элементов, даже до их создания. И ... давайте прочно связать наш код с работой только с двумя элементами и слить все в одну функцию. Ниже приведены результаты работы;
function getCombosWithDiff(a, d, n = 2){
var sa;
return a.reduce(function(p,c,i,a){
if (n > 1) sa = getCombosWithDiff(a.slice(i+1), d, n-1).reduce((r,e) => Math.abs(e[0]-c) > d ? (e.push(c),r.push(e),r)
: r, []);
else sa = [[c]];
return p.concat(sa);
},[]);
}
var arr = Array(100).fill().map((_,i) => i+1);
result = getCombosWithDiff(arr,89);
console.log(JSON.stringify(arr));
console.log(JSON.stringify(result));
Так вот это. Я попробовал приведенный выше код, чтобы перечислить комбинации из двух элементов, каждый из которых имеет разницу больше 10 из массива из 1000 элементов. Он занимает около 5000 мс в Chrome и 14000 мсек в FF. Однако, как упоминалось выше, чем больше значение разности d становится больше, тем короче оно требуется. например, тот же массив с diff 900 будет разрешен всего за 1100 мкс с помощью Chrome и 4000 мсек с FF.
Вы можете проверить и играть here
Что вы хотите сказать? – hatchet
@hatchet отредактировал вопрос – Moulick