Как я могу реализовать функциональные операторы цикла вместо циклов for в этом случае?

Question

Как проверить, существует ли в массиве сумма любых двух элементов в массиве, используя операторы функционального цикла (map, forEach, Reduce) вместо циклов for.

Например, массив, подобный этому

[1, 2, 9, 4, 3] // would return true as 1 + 2 = 3
[2,7,12,6,8,20]  // true as 2 + 6 = 8 which is enough to make it true
[1, 2, 4, 9] //would return false

Я могу сделать это с помощью циклов:

const checkSumExist = arr => {
  for(let i = 0; i < arr.length; i++) {
    for(let j = i + 1; j < arr.length; j++) {
      if(arr.includes(arr[i] + arr[j])) return true;   
    }
  }

  return false; 
}

Так есть ли решение, использующее функциональный оператор цикла вместо вложенного цикла for в этом случае ???

Answer 1

Это моё решение с использованием Rxjs:

import { Observable, from, of, zip, pairs, combineLatest, empty } from 'rxjs';
import { filter, map, takeUntil, takeWhile, single, zipAll, pairwise, combineAll, mergeMap, merge, first, skip, skipWhile, defaultIfEmpty } from 'rxjs/operators';

let test1 = [1, 2, 9, 4, 3]; // would return true as 1 + 2 = 3
let test2 = [2,7,12,6,8,20];  // true as 2 + 6 = 8 which is enough to make it true
let test3 = [1, 2, 4, 9]; //would return false


let observable1 = from(test1);

let skipSameIndex = (arr:number[], anchorIndex:number) => {
    return from(arr).pipe(
        filter((v, i) => {
        // console.log('anchodIndex:', anchorIndex, ', i:', i);
        return anchorIndex !== i;
        })
    )
}

let pairAll = (arr:number[]) => from(arr).pipe(mergeMap( (x, index) => {
    return combineLatest(of(x), skipSameIndex(arr, index))
}));

let isPairExistsInArray = (pair:[number, number], arr: number[]) => {
    let isExists = arr.indexOf(pair[0] + pair[1]) >= 0; 

    // console.log('pair:', pair, ', isExists:', isExists);

    return isExists;
}


let isSumEachElementsExists = (arr:number[]) => pairAll(arr).pipe(    
    map((pair:[number, number]) => isPairExistsInArray(pair, arr)),    
    // first(isExists => isExists)
    filter(x => x),
    defaultIfEmpty(false)
);

// skipSameIndex(test3, 1).subscribe(x => console.log(x));


isSumEachElementsExists(test1).toPromise()
    .then(isExists => console.log('test1 isExists:', isExists))
    .catch(err => console.log('ERROR:', err));


isSumEachElementsExists(test2).toPromise()
    .then(isExists => console.log('test2 isExists:', isExists))
    .catch(err => console.log('ERROR:', err));

isSumEachElementsExists(test3).toPromise()
    .then(isExists => console.log('test3 isExists:', isExists))
    .catch(err => console.log('ERROR:', err));

Мой вывод после этого - FP, а решение слишком сложное по сравнению с итеративным программированием :).Я открыт для предложений или исправлений, если кто-то может упростить это.

Answer 2

Может быть, это грубое и чрезмерно сложное решение, но я поставил перед собой задачу предложить ванильный JS, чисто функциональный подход для решения проблемы.

Кстати, есть библиотеки вроде Sanctuary или Ramda или многие другие, которые могли бы сохранить часть моего ответа.

У него есть только одна проблема: он проверяет все суммируемые комбинации (possibleSums), но это плюс, так как можно распечатать все совпадения.Кроме того, есть someSumExists, который просто проверяет, выводит ли possibleSums одно или несколько совпадений.

С другой стороны, у него есть другая проблема: он основан на том факте, что входные данные не будут содержать повторяющиеся числа.

// ::: Combinators :::

// I :: a -> a -> a
const I = x => x

// T :: a -> (a -> a) -> a
const T = x => f => f (x)

// W :: a -> (a -> a -> a) -> a
const W = x => f => f (x) (x)

// ::: Non-generalized, partial Functor, Chain, Applicative Array-specific instances... :::

// map :: (a -> a) -> [a] -> [a]
const map = f => xs => xs.map (f)

// chain :: (a -> a) -> [a] -> [a]
const chain = f => xs => xs.reduce((o, x) => [...o, ...f (x)], [])

// ap :: [a -> b] -> [a] -> [b]
const ap = ms => m => chain (x => map (f => f(x)) (ms)) (m)

// lift2 :: [a -> c -> d] -> [a -> b] -> [b -> c] -> [d]
const lift2 = f => xs => ys => ap (map (f) (xs)) (ys)

// join :: [[a]] -> [a]
const join = chain (I)

// ::: Utils :::

// pipe :: [Any -> Any] -> Any -> Any
const pipe = xs => x => xs.reduce ((x, f) => f (x), x)

// any :: (a -> Boolean) -> [a] -> Boolean
const any = f => xs => xs.some (f)

// joinWith :: String -> [Any] -> [String]
const joinWith = sep => xs => xs.join (sep)

// length :: [Any] -> Number
const length = xs => xs.length

// equals :: a -> a -> Boolean
const equals = x => y => x === y

// not :: a -> Boolean
const not = x => x !== true

// possibleSums :: Number -> [[Number, Number, Number]]
const possibleSums = input =>
    pipe ([
       W,
       T (lift2 (x => y => x !== y && input.includes (x + y) ? [[x, y, x + y]] : [])),
       join
    ]) (input)
    
// someSumExists :: [Number] -> Boolean
const someSumExists = pipe ([ 
    possibleSums,
    length,
    equals (0),
    not
])

// printSums :: [[Number, Number, Number]] -> [String]
const printSums = pipe ([
    map (([x, y, r]) => `${x} + ${y} = ${r}`),
    joinWith ('\n')
])

// printPossibleSums :: [[Number, Number, Number]] -> String
const printPossibleSums = pipe ([ possibleSums, printSums ])
      
const input1 = [1, 2, 9, 4, 3] 
const input2 = [2,7,12,6,8,20] 
const input3 = [1, 2, 4, 9]

const output1 = printPossibleSums (input1)
const output1_ = someSumExists (input1)

const output2 = printPossibleSums (input2)
const output2_ = someSumExists (input2)

const output3 = printPossibleSums (input3)
const output3_ = someSumExists (input3)


console.log ('Input 1 has a case:', output1_)
console.log (output1)


console.log ('Input 2 has a case:', output2_)
console.log (output2)


console.log ('Input 3 has a case:', output3_)
console.log (output3)

Меньше шаблонного: Ramda !

Это тот же подход с использованием функций Рамды для сохранения некоторых строк кода:

const { map, join, length, equals, not, pipe, lift, unnest } = R
const W = x => f => f (x) (x)
const T = x => f => f (x)

const possibleSums = input =>
    pipe (
       W,
       T (lift ((x, y) => x !== y && input.includes (x + y) ? [[x, y, x + y]] : [])),
       unnest
    ) (input)
    
const someSumExists = pipe ( 
    possibleSums,
    length,
    equals (0),
    not
)

const printSums = pipe (
    map (([x, y, r]) => `${x} + ${y} = ${r}`),
    join ('\n')
)

const printPossibleSums = pipe (possibleSums, printSums)

const input1 = [1, 2, 9, 4, 3] 
const input2 = [2,7,12,6,8,20] 
const input3 = [1, 2, 4, 9]

const output1 = printPossibleSums (input1)
const output1_ = someSumExists (input1)

const output2 = printPossibleSums (input2)
const output2_ = someSumExists (input2)

const output3 = printPossibleSums (input3)
const output3_ = someSumExists (input3)


console.log ('Input 1 has a case:', output1_)
console.log (output1)


console.log ('Input 2 has a case:', output2_)
console.log (output2)


console.log ('Input 3 has a case:', output3_)
console.log (output3)

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.25.0/ramda.min.js"></script>

Answer 3

Упрощенная реализация -

const main = (xs = []) =>
  xs .some ((n, i) =>
    xs .some ((m, j) =>
      i < j && xs .includes (n + m)
    )
  )
  
console.log
  ( main ([ 1, 2, 4, 9, 4, 3 ])   // true
  , main ([ 2, 7, 12, 6, 8, 20 ]) // true
  , main ([ 1, 2, 4, 9 ])         // false
  )

Эта оптимизация с использованием Set повышает скорость до O(1) -

const main = (xs = [], s = new Set (xs)) =>
  xs .some ((n, i) =>
    xs .some ((m, j) =>
      i < j && s .has (n + m)
    )
  )

console.log
  ( main ([ 1, 2, 4, 9, 4, 3 ])   // true
  , main ([ 2, 7, 12, 6, 8, 20 ]) // true
  , main ([ 1, 2, 4, 9 ])         // false
  )

Не забудьте оптимизировать только при необходимости

Answer 4

Идея в следующем решении состоит в том, чтобы использовать reduce и map, чтобы построить все возможные комбинации из 2 чисел, а затем использовать some, чтобы проверить, есть ли сумма любой комбинации в массиве.

function sumExists(arr) {
  return arr
    .reduce((acc, curr, i) => acc.concat(arr.slice(i + 1).map(e => [curr, e])), [])
    .some(([a, b]) => arr.includes(a + b));
}

console.log(sumExists([1, 2, 9, 4, 3]));
console.log(sumExists([2, 7, 12, 6, 8, 20]));
console.log(sumExists([1, 2, 4, 9]));

Версия O (n ^ 2) будет выглядеть следующим образом:

function sumExists(arr) {
  const sums = new Set(arr);
  return arr
    .reduce((acc, curr, i) => {
      acc.push(...arr.slice(i + 1).map(e => [curr, e]));
      return acc;
    }, [])
    .some(([a, b]) => sums.has(a + b));
}

console.log(sumExists([1, 2, 9, 4, 3]));
console.log(sumExists([2, 7, 12, 6, 8, 20]));
console.log(sumExists([1, 2, 4, 9]));

Answer 5

Edit - я забыл, что .some предоставляет индекс каждого элемента в качестве 2-го параметра.Это делает его немного чище!

const foo = [1, 2, 9, 4, 3]; // would return true
const bar = [1, 2, 4, 9]; // would return false
const baz = [2,7,12,6,8,20]; // should also be true

const sumOf2Exists = (arr) => {
  // create a hash of the values in arr so we can check the
  // accept condition in O(1) time
  const hash = arr.reduce((acc, n) => {
    acc[n] = true;
    return acc;
  }, {});
  
  // find some n, m where n and m aren't the same entry 
  // and the sum n+m is in arr (using the hash)
  return arr.some((n, i) => arr.some((m, j) => j > i && hash[n + m]));
};

console.log(sumOf2Exists(foo))
console.log(sumOf2Exists(bar))
console.log(sumOf2Exists(baz));

Вдохновлено комментариями из tex и использованием Immutable.js

const { Set, Range } = Immutable

const foo = [1, 2, 9, 4, 3]; // would return true
const bar = [1, 2, 4, 9]; // would return false
const baz = [2, 7, 12, 6, 8, 20]; // should also be true

const sumOf2Exists = (arr) => {
  const hash = Set(arr);
  return arr.some((n, i) => (
    Range(i+1, arr.length).some(j => hash.has(n + arr[j]))
  ));
};

console.log(sumOf2Exists(foo))
console.log(sumOf2Exists(bar))
console.log(sumOf2Exists(baz));

<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/3.8.2/immutable.min.js"></script>

Answer 6

Я не уверен, что это правильное решение, потому что я не совсем понимаю, что вы подразумеваете под функциональным циклом, но проверьте, это решение без каких-либо циклов.

function check(list, i, j) {
    if(i >= list.length || j >= list.length) return false;
    if(i != j && list.includes(list[i] + list[j])) return true;
    return check(list, i+1, j) || check(list, i, j+1)
}

check([1,2,9,4,3], 0, 0)
true

check([1,2, 4, 9], 0, 0)
false