Эффективный алгоритм для получения комбинаций всех элементов в объекте

Учитывая массив или объект с 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"]

Поэтому, если мне нужен биномиальный коэффициент x=3 из n=4, я выбираю все строки длиной, равной трем. {abc, abd, acd, bcd}.

Поэтому я делаю это в два этапа.

Есть ли более эффективный алгоритм с меньшей сложностью?

Ссылка: Производительность решения ( JSPerf)


javascript algorithm memoization binomial-coefficients dynamic-programming
person Panos Kal.    schedule 27.07.2017    source источник
comment
Спасибо вам всем. Я создал тест jsperf со всеми ответами здесь после тестирования нескольких значений в разных браузерах и на разных ПК. Я думаю, что у Дэвида есть самое быстрое решение   -  person Panos Kal.    schedule 28.07.2017

Ответы (4)


arrow_upward
1
arrow_downward

Ваш алгоритм почти O(2^n), вы можете отбросить много комбинаций, но количество элементов будет (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), следующая комбинация достигнута, но если это не так, он должен увеличиться до предыдущий индекс.

person David Pérez Cabrera    schedule 27.07.2017

arrow_upward
3
arrow_downward

Вы можете использовать итеративный и рекурсивный подход с упором на длину массива и все еще необходимые элементы.

В основном combine() принимает массив со значениями для объединения и размером требуемых наборов результатов комбинации.

Внутренняя функция c() принимает массив ранее созданных комбинаций и начальное значение в качестве индекса исходного массива для комбинации. Возврат представляет собой массив со всеми составленными комбинациями.

Первый вызов всегда c([], 0) из-за пустого массива результатов и начального индекса 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; }

person Nina Scholz    schedule 27.07.2017

arrow_upward
2
arrow_downward

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

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

person גלעד ברקן    schedule 27.07.2017

arrow_upward
2
arrow_downward

А вот и настоящая рекурсия.

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

person גלעד ברקן    schedule 27.07.2017