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

146

16 мая 2022, 00:10

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

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

Алгоритм 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 2

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

class Combinatorics {
  /*
   * @param arr {Array} Набор элементов.
   * @param k {Number} Размер каждого сочетания.
   * @return {Array} Возвращает все сочетания.
   */
  static combine = (() => {
    let res = null
    const 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 (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: combinations.map(c => c.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;
}