Efektywny algorytm uzyskiwania kombinacji wszystkich obiektów w obiekcie

Question

Biorąc tablicę lub obiekt za pomocą n kluczy, muszę znaleźć wszystkie kombinacje o długości x.
Podana X jest zmienna. binomial_coefficient(n,x).

Obecnie używam to:

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"]); 

Wyjście jest:

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

Więc jeśli chcę Symbol Newtona x=3 z n=4 wybiorę wszystkie ciągi o długości równej trzem. {abc, abd, acd, bcd}.

Robię to w dwóch etapach.

Czy istnieje skuteczniejszy algorytm o mniejszej złożoności?

Link:.Solution performance (JSPerf)

Answer 1

Twój algorytm jest prawie O(2^n) można wyrzucić wiele kombinacji, ale num elementów będzie (n! * (n-x)!)/x!.

Aby odrzucić bezużyteczne kombinacje, można użyć tablicy indeksowanej.

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));

Na przykład, pierwsze połączenie posiadają indeksy: [0, 1, 2] a elementy ["a", "b", "c"]. Aby obliczyć następną kombinację, otrzyma ostatni indeks 2 i spróbuje zwiększyć, jeśli inkrement jest niższy niż pozycja maksymalna (w tym przypadku 4), następna kombinacja zostanie osiągnięta, ale jeśli nie jest, musi ona zwiększyć do poprzedni indeks.

Answer 2

Moglibyśmy stworzyć tylko te kombinacje jesteśmy zainteresowani również, zamiast klonowania tablic za pomocą kromkę w każdej rozmowie, możemy użyć wskaźnika do oryginalnej tablicy. Oto jedna wersja. Konwersja do rekurencji bez zewnętrznej zmiennej globalnej jest pozostawiona jako ćwiczenie.

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

Można użyć iteracyjnego i rekursywnego podejścia z naciskiem na długość tablicy i wciąż potrzebne elementy.

Zasadniczo combine() pobiera tablicę z wartościami do połączenia i wielkością pożądanych zestawów wyników kombinacji.

Wewnętrzna funkcja c() pobiera tablicę wcześniej utworzonych kombinacji i wartość początkową jako indeks oryginalnej tablicy dla kombinacji. Zwrot jest tablicą z wszystkimi utworzonymi kombinacjami.

Pierwsze wywołanie jest zawsze c([], 0), z powodu pustej tablicy wyników i indeksu początkowego 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

A oto prawdziwa rekurencji.

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)))