[javascript] JavaScript에서 여러 배열의 데카르트 곱

Program / 글쓴이

JavaScript에서 여러 배열의 데카르트 곱을 어떻게 구현 하시겠습니까?

예로서,

cartesian([1, 2], [10, 20], [100, 200, 300])

돌아와야한다

[
  [1, 10, 100],
  [1, 10, 200],
  [1, 10, 300],
  [2, 10, 100],
  [2, 10, 200]
  ...
]

답변

2017 업데이트 : 바닐라 JS를 사용한 2 줄 답변

여기에있는 모든 답변은 지나치게 복잡 하며 대부분 20 줄 이상의 코드가 필요합니다.

이 예제는 lodash, underscore 또는 기타 라이브러리없이 두 줄의 바닐라 JavaScript 만 사용합니다 .

let f = (a, b) => [].concat(...a.map(a => b.map(b => [].concat(a, b))));
let cartesian = (a, b, ...c) => b ? cartesian(f(a, b), ...c) : a;

최신 정보:

위와 동일하지만 ESLint 를 eslint-config-airbnb- base 와 함께 사용하여 검증 된 Airbnb JavaScript 스타일 가이드 를 엄격하게 따르도록 개선되었습니다 .

const f = (a, b) => [].concat(...a.map(d => b.map(e => [].concat(d, e))));
const cartesian = (a, b, ...c) => (b ? cartesian(f(a, b), ...c) : a);

원본 코드의 linter 문제에 대해 알려 주신 ZuBB 에게 특별히 감사드립니다 .

예

이것은 귀하의 질문에 대한 정확한 예입니다.

let output = cartesian([1,2],[10,20],[100,200,300]);

산출

다음은 해당 명령의 출력입니다.

[ [ 1, 10, 100 ],
  [ 1, 10, 200 ],
  [ 1, 10, 300 ],
  [ 1, 20, 100 ],
  [ 1, 20, 200 ],
  [ 1, 20, 300 ],
  [ 2, 10, 100 ],
  [ 2, 10, 200 ],
  [ 2, 10, 300 ],
  [ 2, 20, 100 ],
  [ 2, 20, 200 ],
  [ 2, 20, 300 ] ]

데모

데모보기 :

통사론

여기에서 사용한 구문은 새로운 것이 아닙니다. 내 예에서는 스프레드 연산자와 나머지 매개 변수를 사용합니다.이 기능은 2015 년 6 월에 발행 된 ECMA-262 표준 6 판에 정의 된 JavaScript의 기능이며 훨씬 더 일찍 개발되었으며 ES6 또는 ES2015로 더 잘 알려져 있습니다. 보다:

이렇게 코드를 간단하게 만들어서 사용하지 않는 것은 죄악입니다. 기본적으로 지원하지 않는 이전 플랫폼의 경우 항상 Babel 또는 기타 도구를 사용하여 이전 구문으로 변환 할 수 있습니다. 사실 Babel로 변환 한 제 예제는 여기에있는 대부분의 예제보다 여전히 짧고 간단하지만 그렇지 않습니다. 번역의 결과물은 이해하거나 유지해야하는 것이 아니기 때문에 정말 중요합니다. 단지 제가 흥미로워 한 사실입니다.

결론

유지 관리가 어려운 수백 줄의 코드를 작성할 필요가 없으며 두 줄의 바닐라 자바 ​​스크립트가 작업을 쉽게 수행 할 수있는 간단한 작업을 위해 전체 라이브러리를 사용할 필요가 없습니다. 보시다시피 언어의 최신 기능을 사용하는 것이 실제로 효과가 있으며 최신 기능을 기본 지원하지 않는 구식 플랫폼을 지원해야하는 경우 항상 Babel 또는 기타 도구를 사용하여 새 구문을 이전 구문으로 변환 할 수 있습니다. .

1995 년처럼 코딩하지 마세요

자바 스크립트는 진화하고 있으며 그 이유가 있습니다. TC39는 새로운 기능을 추가하여 언어 디자인의 놀라운 작업을 수행하고 브라우저 공급 업체는 이러한 기능을 구현하는 놀라운 작업을 수행합니다.

브라우저의 특정 기능에 대한 현재 기본 지원 상태를 보려면 다음을 참조하십시오.

Node 버전의 지원을 보려면 다음을 참조하십시오.

기본적으로 지원하지 않는 플랫폼에서 최신 구문을 사용하려면 Babel을 사용하세요.

답변

여기서 문제의 해결책 기능 (임의없이 가변 변수 사용!) reduce과 flatten의해 제공 underscore.js:

function cartesianProductOf() {
    return _.reduce(arguments, function(a, b) {
        return _.flatten(_.map(a, function(x) {
            return _.map(b, function(y) {
                return x.concat([y]);
            });
        }), true);
    }, [ [] ]);
}

// [[1,3,"a"],[1,3,"b"],[1,4,"a"],[1,4,"b"],[2,3,"a"],[2,3,"b"],[2,4,"a"],[2,4,"b"]]
console.log(cartesianProductOf([1, 2], [3, 4], ['a']));  
<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore.js"></script>

스 니펫 확장

비고 :이 솔루션은 http://cwestblog.com/2011/05/02/cartesian-product-of-multiple-arrays/ 에서 영감을 얻었습니다 .

답변

다음은 라이브러리를 사용하지 않고 일반 자바 스크립트로 된 @viebel 코드의 수정 된 버전입니다.

function cartesianProduct(arr) {
    return arr.reduce(function(a,b){
        return a.map(function(x){
            return b.map(function(y){
                return x.concat([y]);
            })
        }).reduce(function(a,b){ return a.concat(b) },[])
    }, [[]])
}

var a = cartesianProduct([[1, 2,3], [4, 5,6], [7, 8], [9,10]]);
console.log(JSON.stringify(a));

스 니펫 확장

답변

커뮤니티는 이것이 사소하고 참조 구현을 찾기가 쉽다고 생각하는 것 같습니다. 간단한 검사를 통해 내가 할 수 없었거나 어쩌면 내가 바퀴를 다시 발명하거나 교실과 같은 프로그래밍 문제를 해결하는 것을 좋아하는 것 같습니다. :

function cartProd(paramArray) {

  function addTo(curr, args) {

    var i, copy,
        rest = args.slice(1),
        last = !rest.length,
        result = [];

    for (i = 0; i < args[0].length; i++) {

      copy = curr.slice();
      copy.push(args[0][i]);

      if (last) {
        result.push(copy);

      } else {
        result = result.concat(addTo(copy, rest));
      }
    }

    return result;
  }


  return addTo([], Array.prototype.slice.call(arguments));
}


>> console.log(cartProd([1,2], [10,20], [100,200,300]));
>> [
     [1, 10, 100], [1, 10, 200], [1, 10, 300], [1, 20, 100],
     [1, 20, 200], [1, 20, 300], [2, 10, 100], [2, 10, 200],
     [2, 10, 300], [2, 20, 100], [2, 20, 200], [2, 20, 300]
   ]

상대적으로 효율적인 전체 참조 구현 … 😀

효율성에 대한 : 루프에서 if를 취하고 기술적으로 일정하고 분기 예측과 모든 혼란을 돕고 있기 때문에 2 개의 개별 루프를 가지면 얻을 수 있지만 그 요점은 자바 스크립트에서 일종의 논쟁입니다.

누구든지 즐기세요 -ck

답변

다음의 효율적인 생성 기능은 모두 제공의 직교 제품 반환 반복 가능 객체를 :

// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
  const remainder = tail.length > 0 ? cartesian(...tail) : [[]];
  for (let r of remainder) for (let h of head) yield [h, ...r];
}

// Example:
console.log(...cartesian([1, 2], [10, 20], [100, 200, 300]));

스 니펫 확장

반복 가능한 프로토콜을 구현하는 배열, 문자열, 집합 및 기타 모든 개체를 허용 합니다 .

n 항 데카르트 곱 의 사양에 따라 다음 을 산출합니다.

  • []하나 이상의 주어진 이터 러블이 비어있는 경우, 예 : []또는''
  • [[a]]단일 값을 포함하는 단일 iterable a이 제공되는 경우.

다른 모든 케이스는 다음 테스트 케이스에서 설명하는대로 예상대로 처리됩니다.

코드 스 니펫 표시

답변

다음은 비판적이고 간단한 재귀 솔루션입니다.

function cartesianProduct(a) { // a = array of array
    var i, j, l, m, a1, o = [];
    if (!a || a.length == 0) return a;

    a1 = a.splice(0, 1)[0]; // the first array of a
    a = cartesianProduct(a);
    for (i = 0, l = a1.length; i < l; i++) {
        if (a && a.length) for (j = 0, m = a.length; j < m; j++)
            o.push([a1[i]].concat(a[j]));
        else
            o.push([a1[i]]);
    }
    return o;
}

console.log(cartesianProduct([[1,2], [10,20], [100,200,300]]));
// [[1,10,100],[1,10,200],[1,10,300],[1,20,100],[1,20,200],[1,20,300],[2,10,100],[2,10,200],[2,10,300],[2,20,100],[2,20,200],[2,20,300]]

스 니펫 확장

답변

다음은 ECMAScript 2015 생성기 함수 를 사용하는 재귀 적 방법 이므로 한 번에 모든 튜플을 만들 필요가 없습니다.

function* cartesian() {
    let arrays = arguments;
    function* doCartesian(i, prod) {
        if (i == arrays.length) {
            yield prod;
        } else {
            for (let j = 0; j < arrays[i].length; j++) {
                yield* doCartesian(i + 1, prod.concat([arrays[i][j]]));
            }
        }
    }
    yield* doCartesian(0, []);
}

console.log(JSON.stringify(Array.from(cartesian([1,2],[10,20],[100,200,300]))));
console.log(JSON.stringify(Array.from(cartesian([[1],[2]],[10,20],[100,200,300]))));

스 니펫 확장