Как реализовать генерацию сочетаний без повторений (JS)?

Question

Как лучше реализовать функцию combine с сигнатурой

const array = ['a', 'b', 'c', 'd'];
const k = 3;

const combinations = combine(array, k);

где combinations — все сочетания из array по k (все возможные k-элементные неупорядоченные подмножества без повторений из array)?

Пример ожидаемого возвращённого значения:

const combinations = [
    ['a', 'b', 'c'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd']
];

Answer 1

Решение на основе скрипта некого mgechev:

class Combinatorics {
    /*
     * @param arr {Array} Набор элементов.
     * @param k {Number} Размер каждого сочетания.
     * @return {Array} Возвращает все сочетания.
     */
    static combine = (function () {
        let res = null;
        function combinations(arr, k, start, idx, current) {
            if (idx === k) {
                res.push([...current]);
                return;
            }
            for (let i = start; i < arr.length; i += 1) {
                current[idx] = arr[i];
                combinations(arr, k, i + 1, idx + 1, current);
            }
        }

        return function (arr, k) {
            res = [];
            combinations(arr, k, 0, 0, []);
            const temp = res;
            res = null;
            return temp;
        };
    }());
}


const array = ['a', 'b', 'c', 'd']; // n = array.length = 4
const k = 3;

const combinations = Combinatorics.combine(array, k);
console.log({
    // C^k_n = n! / (!k * (n - k)!)
    expexted: (4 * 3 * 2 * 1)/ ((3 * 2 * 1) * (1)),
    length: combinations.length,
    combinations,
});

Answer 2

Алгоритм Twiddle за авторством Phillip J. Chase, из книги Communications of the Association for Computing Machinery 13:6:368 (1970). Генерирует последовательность комбинаций при помощи замены одного элемента в предыдущей комбинации. Алгоритм не очень простой для понимания, привожу в конце ответа скриншот станицы книги. Ниже мой код генерирует комбинации в виде массива индексов, но их можно замаппить к элементам массива:

function createCombinationsIterator(n, k) {
    let x = 0, y = 0, z = 0;
    let p = new Array(n + 2);
    let c = new Array(k);

    let init = function () {
        let i;
        p[0] = n + 1;
        for (i = 1; i != n - k + 1; i++) {
            p[i] = 0;
        }
        while (i != n + 1) {
            p[i] = i + k - n;
            i++;
        }
        p[n + 1] = -2;
        if (k == 0) {
            p[1] = 1;
        }
        for (i = 0; i < k; i++) {
            c[i] = i + n - k;
        }
    };

    let twiddle = function () {
        let i, j, m;
        j = 1;
        while (p[j] <= 0) {
            j++;
        }
        if (p[j - 1] == 0) {
            for (i = j - 1; i != 1; i--) {
                p[i] = -1;
            }
            p[j] = 0;
            x = z = 0;
            p[1] = 1;
            y = j - 1;
        } else {
            if (j > 1) {
                p[j - 1] = 0;
            }
            do {
                j++;
            } while (p[j] > 0);
            m = j - 1;
            i = j;
            while (p[i] == 0) {
                p[i++] = -1;
            }
            if (p[i] == -1) {
                p[i] = p[m];
                z = p[m] - 1;
                x = i - 1;
                y = m - 1;
                p[m] = -1;
            } else {
                if (i == p[0]) {
                    return false;
                } else {
                    p[j] = p[i];
                    z = p[i] - 1;
                    p[i] = 0;
                    x = j - 1;
                    y = i - 1;
                }
            }
        }
        return true;
    };

    let first = true;
    init();

    return {
        hasNext: function () {
            if (first) {
                first = false;
                return true;
            } else {
                let result = twiddle();
                if (result) {
                    c[z] = x;
                }
                return result;
            }
        },
        getCombination: function () {
            return c;
        }
    };
}

const array = ['a', 'b', 'c', 'd'];
let iterator = createCombinationsIterator(4, 3);
while (iterator.hasNext()) {
    let combination = iterator.getCombination();
    console.log('indexes=' + combination.join(',') + ' mapped=' + combination.map(index => array[index]).join(','));
}

Так же этот алгоритм умеет генерировать комбинации в виде последовательности масок. Возможно в некоторых случаях маски будут полезнее. Пример ниже:

function createCombinationMasksIterator(n, k) {
    let x = 0, y = 0, z = 0;
    let p = new Array(n + 2);
    let b = new Array(n);

    let initTwiddle = function () {
        let i;
        p[0] = n + 1;
        for (i = 1; i != n - k + 1; i++) {
            p[i] = 0;
        }
        while (i != n + 1) {
            p[i] = i + k - n;
            i++;
        }
        p[n + 1] = -2;
        if (k == 0) {
            p[1] = 1;
        }
        for (i = 0; i != n - k; i++) {
            b[i] = 0;
        }
        while (i != n) {
            b[i++] = 1;
        }
    };

    let twiddle = function () {
        let i, j, m;
        j = 1;
        while (p[j] <= 0) {
            j++;
        }
        if (p[j - 1] == 0) {
            for (i = j - 1; i != 1; i--) {
                p[i] = -1;
            }
            p[j] = 0;
            x = z = 0;
            p[1] = 1;
            y = j - 1;
        } else {
            if (j > 1) {
                p[j - 1] = 0;
            }
            do {
                j++;
            } while (p[j] > 0);
            m = j - 1;
            i = j;
            while (p[i] == 0) {
                p[i++] = -1;
            }
            if (p[i] == -1) {
                p[i] = p[m];
                z = p[m] - 1;
                x = i - 1;
                y = m - 1;
                p[m] = -1;
            } else {
                if (i == p[0]) {
                    return false;
                } else {
                    p[j] = p[i];
                    z = p[i] - 1;
                    p[i] = 0;
                    x = j - 1;
                    y = i - 1;
                }
            }
        }
        return true;
    };

    let first = true;
    initTwiddle();

    return {
        hasNext: function () {
            if (first) {
                first = false;
                return true;
            } else {
                let result = twiddle();
                if (result) {
                    b[x] = 1;
                    b[y] = 0;
                }
                return result;
            }
        },
        getCombinationMask: function () {
            return b;
        }
    };
}

let iterator = createCombinationMasksIterator(4, 3);
while (iterator.hasNext()) {
    console.log(iterator.getCombinationMask().join(''));
}

Answer 3

const array = ['a', 'b', 'c', 'd', 'e']; // множество элементов
const k = 4; // размер сочетаний

const combinations = combine2(array, k);
console.log("итого:", combinations);

function combine2(array, k) {
  const n = array.length - 1; // максимальный индекс массива элементов
  const m = k - 1; // максимальный индекс массива-маски сочетания
  const finds = []; // массив всех возможных осчетаний
  const mask = []; // маска сочетания
  let finish = false;
  for (let i = 0; i < k; i++) mask.push(array[i]);
  while (!finish) {
    finish = true;
    const str = mask.join('');
    if (!finds.includes(str)) finds.push(str); // записываем сочетание в массив
    for (let i = 0; i < k; i++) {
      if (mask[m - i] != array[n - i]) {
        // проверяем, остались ли еще сочетания
        finish = false;
        let p = array.indexOf(mask[m - i]);
        mask[m - i] = array[++p]; // изменяем маску, начиная с последнего элемента
        for (let j = m - i + 1; j < k; j++) {
          mask[j] = array[++p];
        }
        break;
      }
    }
  }
  return finds;
}

Answer 4

Рекурсивно через генератор:

function* generateCombs<T>(items: T[], combSize: number): Iterable<T[]> {
  if (combSize < 1) {
    yield [];
    return;
  }

  for (let i = 0; i <= items.length - combSize; i++) {
    const restItems = items.slice(i + 1, items.length);

    for (const comb of generateCombs(restItems, combSize - 1)) {
      yield [items[i] as T, ...comb];
    }
  }
}

БЛОГ НА HUSL

Как реализовать генерацию сочетаний без повторений (JS)?

Ответы (4 шт):