オブジェクトのすべてのアイテムの組み合わせを取得する効率的なアルゴリズム

Question

n個のキーを持つ配列またはオブジェクトを指定すると、長さがxのすべての組み合わせを見つける必要があります。
Xが可変であるとします。 binomial_coefficient(n,x)。

現在、私はこの使用しています：

に

function combine(items) { 
    var result = []; 
    var f = function(prefix, items) { 
     for (var i = 0; i < items.length; i++) { 
      result.push(prefix + items[i]); 
      f(prefix + items[i], items.slice(i + 1)); 
     } 
    } 
    f('', items); 
    return result; 
} 

var combinations = combine(["a", "b", "c", "d"]); 

を出力は、次のとおりです。

["a", "ab", "abc", "abcd", "abd", "ac", "acd", "ad", "b", "bc", "bcd", "bd", "c", "cd", "d"] 

私はn=4から二項係数x=3をしたいのであれば、私は3と同じ長さのすべての文字列を選択します。 {abc、abd、acd、bcd}。

私はこれを2つのステップで行います。

複雑さの少ない効率的なアルゴリズムはありますか？

リンク：Solution performance (JSPerf)

Answer 1

あなたのアルゴリズムはほとんどO(2^n)である、あなたは、組み合わせの多くを捨てることができますが、要素のnumが(n! * (n-x)!)/x!になります。

無駄な組み合わせを破棄するには、インデックス付き配列を使用します。例えば

function combine(items, numSubItems) { 
 
     var result = []; 
 
     var indexes = new Array(numSubItems); 
 
     for (var i = 0 ; i < numSubItems; i++) { 
 
      indexes[i] = i; 
 
     } 
 
     while (indexes[0] < (items.length - numSubItems + 1)) { 
 
      var v = []; 
 
      for (var i = 0 ; i < numSubItems; i++) { 
 
       v.push(items[indexes[i]]); 
 
      } 
 
      result.push(v); 
 
      indexes[numSubItems - 1]++; 
 
      var l = numSubItems - 1; // reference always is the last position at beginning 
 
      while ((indexes[numSubItems - 1] >= items.length) && (indexes[0] < items.length - numSubItems + 1)) { 
 
       l--; // the last position is reached 
 
       indexes[l]++; 
 
       for (var i = l +1 ; i < numSubItems; i++) { 
 
        indexes[i] = indexes[l] + (i - l); 
 
       } 
 
      }   
 
     } 
 
     return result; 
 
    } 
 

 
    var combinations = combine(["a", "b", "c", "d"], 3); 
 
    console.log(JSON.stringify(combinations));

、最初の組み合わせは、インデックスを持っている：[0, 1, 2]および要素["a", "b", "c"]。次のコンビネーションを計算するには、最後のインデックス2を取得し、インクリメントが最大位置（この場合は4）よりも小さい場合は次のコンビネーションに達しますが、そうでなければa前のインデックス。

Answer 2

我々は、我々が興味を持っているだけで、それらの組み合わせを作成することができます。また、むしろ各呼び出しでスライスを使用して配列をクローニングするよりも、我々は元の配列へのポインタを使用することができます。ここに1つのバージョンがあります。それを外部のグローバル変数なしで再帰に変換することは、練習問題として残されています。

function choose(ns,r){ 
 
    var res = []; 
 

 
    function _choose(i,_res){ 
 
    if (_res.length == r){ 
 
     res.push(_res); 
 
     return; 
 

 
    } else if (_res.length + ns.length - i == r){ 
 
     _res = _res.concat(ns.slice(i)); 
 
     res.push(_res); 
 
     return 
 
    } 
 

 
    var temp = _res.slice(); 
 
    temp.push(ns[i]); 
 

 
    _choose(i + 1,temp); 
 
    _choose(i + 1,_res); 
 
    } 
 

 
    _choose(0,[]); 
 
    return res; 
 
} 
 

 
var combinations = choose(["a", "b", "c", "d"], 3); 
 
console.log(JSON.stringify(combinations));

Answer 3

アレイの長さとまだ必要なアイテムにストレスをかけて反復的かつ再帰的なアプローチを使用できます。

基本的にcombine()は、結合する値と必要な組み合わせ結果セットのサイズを持つ配列をとります。

内部関数c()は、以前に作成された組み合わせの配列と、元の配列の組み合わせのインデックスとしての開始値を取ります。戻り値は、すべての組み合わせを持つ配列です。

空の結果配列と開始インデックスが0であるため、最初の呼び出しはすべてc([], 0)です。

function combine(array, size) { 
 

 
    function c(part, start) { 
 
     var result = [], i, l, p; 
 
     for (i = start, l = array.length; i < l; i++) { 
 
      p = part.slice(0);      // get a copy of part 
 
      p.push(array[i]);      // add the iterated element to p 
 
      if (p.length < size) {     // test if recursion can go on 
 
       result = result.concat(c(p, i + 1)); // call c again & concat rresult 
 
      } else { 
 
       result.push(p);      // push p to result, stop recursion 
 
      } 
 
     } 
 
     return result; 
 
    } 
 

 
    return c([], 0); 
 
} 
 

 
console.log(combine(["a", "b", "c", "d"], 3));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 4

そして、ここで本当の再帰です。

function seq(a,b){ 
 
    var res = []; 
 
    for (var i=a; i<=b; i++) 
 
    res.push(i); 
 
    return res; 
 
} 
 

 
function f(n,k){ 
 
    if (k === 0) 
 
    return [[]]; 
 
    
 
    if (n === k) 
 
    return [seq(1,n)]; 
 
    
 
    let left = f(n - 1, k - 1), 
 
     right = f(n - 1, k); 
 
    
 
    for (let i=0; i<left.length; i++) 
 
    left[i].push(n); 
 
    
 
    return left.concat(right); 
 
} 
 

 
console.log(JSON.stringify(f(4,3)))