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

155
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;
}

READ ALSO
Как получить ширину React компонентов

Как получить ширину React компонентов

Подскажите - как я могу получить ширину g и text компонентов, чтобы потом на основе их значений вычислить нужный мне угол поворота для rotate

185
Как переписать цикл for в reducer?

Как переписать цикл for в reducer?

господаПрошу помочь со следующим вопросом

182
Запоминание просмотренных элементов JS

Запоминание просмотренных элементов JS

Всем приветНа страницу из бд загружаются данные (как только пользователь доходит до конца, загружаются еще одни)

152
Заполнение массива случайным образом

Заполнение массива случайным образом

Нужно заполнить массив случайным образом в заданном промежутке: элемент добавляется в массив при нажатии на кнопку «ОК»Добавить сортировку...

164