主页 / 问题 / 1205413
Accepted
Артём Ионаш
Asked:2021-11-16 19:28:00 +0000 UTC2021-11-16 19:28:00 +0000 UTC

如何实现不重复的组合生成？

  • 772

combine用签名（JavaScript）实现函数的最佳方法是什么

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

const combinations = combine(array, k);

k数组的combinations所有组合在哪里（所有可能的k元素无序子集，没有来自数组的重复）？

预期返回值的示例：

const combinations = [
    ['a', 'b', 'c'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd']
];
алгоритм

3 个回答

  1. Phillip J. Chase的 Twiddle 算法，来自计算机协会通讯 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(''));
}

    算法描述

    • 8
  2. Best Answer

    TypeScript中的解决方案：

    const combine = <T>(arr: T[], k: number, withRepetition = false) => {
  const combinations: T[][] = []
  const combination: T[] = Array(k)
  const internalCombine = (start: number, depth: number): void => {
    if (depth === k) {
      combinations.push([...combination])
      return
    }
    for (let index = start; index < arr.length; ++index) {
      combination[depth] = arr[index]
      internalCombine(index + (withRepetition ? 0 : 1), depth + 1)
    }
  }
  internalCombine(0, 0)
  return combinations
}

    JavaScript解决方案：

    const combine = (arr, k, withRepetition = false) => {
  const combinations = []
  const combination = Array(k)
  const internalCombine = (start, depth) => {
    if (depth === k) {
      combinations.push([...combination])
      return
    }
    for (let index = start; index < arr.length; ++index) {
      combination[depth] = arr[index]
      internalCombine(index + (withRepetition ? 0 : 1), depth + 1)
    }
  }
  internalCombine(0, 0)
  return combinations
}

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

const combinations = combine(array, k)
console.log({ combinations: combinations.map(c => c.join()) })

    注：解决方案是基于某mgechev的脚本。

    • 4 

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

    • 2

相关问题