Todas las formas de dividir una matriz (combinaciones de elementos) en una partición personalizada

Quiero dividir el conjunto de n elementos en subgrupos de tamaño dado con todas las combinaciones posibles de elementos.

Por ejemplo:

Array: {1,2,3,4} – puede ser n elementos, 1 <n <100. Puede tener duplicados.

Patrón de tamaño dado (solo ejemplo, podría ser diferente): [2 -subarrays, 2-elements]

Resultado Esperado:

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

o

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

etc. Como puede ver, el orden de los elementos en subarrays, o el orden de subarrays en conjuntos de subarrays no importa. Tiene que ser el número mínimo de conjuntos de subarreglos de matriz de entrada.

Tengo que debajo de la solución, pero incluye también permutaciones. Necesito optimizar esto para no generar permutaciones en absoluto. JavaScript no es necesario, cualquier lenguaje servirá. Gracias de antemano por cualquier ayuda.

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

Aquí hay una formulación recursiva que enumera combinaciones de elementos reales. En la lista, [2,2] , cada 2 se considera un elemento diferente. Podemos ingresar patrones arbitrarios como [1,2,3,4,5,6] divididos en todas las combinaciones con el patrón [[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.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); 

Supongo que quieres n combinaciones de una matriz. Usted puede hacer lo siguiente;

 Array.prototype.combinations = function(n){ return this.reduce((p,c,i,a) => p.concat(n > 1 ? a.slice(i+1).combinations(n-1).map(e => [].concat(e,c)) : [[c]]),[]); }; var result = [1,2,3,4].combinations(2); console.log(JSON.stringify(result)); result = [1,2,3,4,5,6].combinations(3); console.log(JSON.stringify(result)); 
Intereting Posts