将数组（元素组合）划分为自定义分区的所有方法

小编典典

将数组（元素组合）划分为自定义分区的所有方法

algorithm

我想将n个元素的数组划分为具有所有可能的元素组合的给定大小的子数组。

例如：

数组：{1,2,3,4}-可以是n个元素，1 <n <100。它可以有重复项。

给定的大小模式（只是示例，可能会有所不同）： [2 -subarrays, 2-elements]

预期结果：

{1,2}，{3,4}
{1,3}，{2,4}
{1,4}，{2,3}

要么

{2,1}，{3,4}
{1,3}，{4,2}
{3,2}，{1,4}

如您所见，子数组中元素的顺序或子数组集中子数组的顺序无关紧要。它必须是输入数组子数组的最小组数。

我必须了解以下解决方案，但其中还包括排列。我需要对此进行优化，以完全不产生任何排列。JavaScript不是必需品，任何语言都可以。在此先感谢您的帮助。

function getN(n, array, subsets) {

    var f,

        l = array.length,

        indices = [],

        temp;



    array = array.slice();

    while (l--) {

        f = factorial(l);

        indices.push(Math.floor(n / f));

        n %= f;

    }

    temp = indices.map(i => array.splice(i, 1)[0]);

    return subsets

        ? subsets.map((i => l => temp.slice(i, i += l))(0))

        : temp;





}



function factorial(num) {

    var result = 1;

    while (num) {

        result *= num;

        num--;

    }

    return result;

}



var i, l,

    array = ['1', '2', '3', '4'],

    subsets = [2, 2],

    pre = document.getElementById('out');



for (i = 0, l = factorial(array.length); i < l; i++) {

    pre.innerHTML += i.toString().padStart(4) +': ' + JSON.stringify(getN(i, array, subsets)) + '\n';

}


<pre id="out"></pre>

阅读 212

2020-07-28

共1个答案

小编典典

这是一个递归公式，它将枚举实际元素的组合。在列表中[2,2]，每个2被视为一个不同的元素。我们可以输入任意模式，例如[1,2,3,4,5,6]使用pattern划分为所有组合[[x],[x,x],[x,x,x]]。

function f(ns, subs){

  if (ns.length != subs.reduce((a,b) => a+b))

    throw new Error('Subset cardinality mismatch');



  function g(i, _subs){

    if (i == ns.length)

      return [_subs];



    let res = [];

    const cardinalities = new Set();



    function h(j){

      let temp = _subs.map(x => x.slice());

      temp[j].push(ns[i]);

      res = res.concat(g(i + 1, temp));

    }



    for (let j=0; j<subs.length; j++){

      if (!_subs[j].length && !cardinalities.has(subs[j])){

        h(j);

        cardinalities.add(subs[j]);



      } else if (_subs[j].length && _subs[j].length < subs[j]){

        h(j);

      }

    }

    return res;

  }

  let _subs = [];

  subs.map(_ => _subs.push([]));



  return g(0, _subs);

}



console.log('\n[0,1,2,3], [2,2]:');

let str = '';

for (let i of f([0,1,2,3], [2,2]))

  str += '\n' + JSON.stringify(i);

console.log(str);



console.log('\n[0,1,2,3], [1,3]:');

str = '';

for (let i of f([0,1,2,3], [1,3]))

  str += '\n' + JSON.stringify(i);

console.log(str);



console.log('\n[0,1,2,3,4,5,6,7,8,9], [1,2,3,4]:');

str = '';

for (let i of f([0,1,2,3,4,5,6,7,8,9], [1,2,3,4]))

  str += '\n' + JSON.stringify(i);

console.log(str);

2020-07-28