¿Combinaciones únicas de puntos de datos en dos bandejas?

Question

Tengo un conjunto de datos de tamaño $X$ , digamos que $X = 7$ . Quiero encontrar todas las formas únicas en que los datos pueden ser agrupados en dos bins de un tamaño mínimo de dos. Para el ejemplo en el que $X = 7$ lo he hecho:

 Bin A: 5     4
 Bin B: 2     3

Como los posibles arreglos. Lo que necesito es cuáles son los arreglos reales. Así que si los datos de $X = 7$ allá arriba está $A B C D E F G$ para la primera columna allí entonces necesito:

Combinación 1: Papelera A: A B C D E
Papelera B: F G

Combinación 2: Bin A: A B C D G
Papelera B: F E

Combinación 3: Bin A: A B E D G
Papelera B: F C

etc.

hasta que tenga todas las combinaciones posibles para los datos. Las restricciones que tengo son que un contenedor tiene que tener un tamaño mínimo de 2 y los contenedores no son únicos, por lo que {A B} es lo mismo que {B A}.

Answer 1

Supongamos que esos $n$ son todos distintos, entonces la función que se necesita para generar todas las combinaciones de $C(n,r)$ se llama siguienteCombinación $^{\dagger}$ .

En primer lugar, etiquete cada uno de sus $n$ objetos con un número en $\{1,2,3\dots,n\}$ para que haya una correspondencia uno a uno entre los números y sus objetos. Con algunas reglas, puedes generar todos los $C(n,r)$ combinaciones:

(1) Ya que quiere elegir $r$ de $n$ la secuencia inicial es $123\textrm{...r}$ y también se necesita la secuencia $123\textrm{...n}$ .

(2) Compare su último dígito: el último dígito de su $123\textrm{...r}$ y el último dígito de una la secuencia $123\textrm{...n}$ .

(3) Si son iguales, pasa a comparar el dígito anterior al último y así sucesivamente. Si no lo son, aumenta este dígito en tu $123\textrm{...r}$ por uno, truncar esos dígitos siguientes, y añadir el mismo número de dígitos truncados al dígito que acabas de aumentar, cada uno de esos dígitos es uno más que el dígito de su lado izquierdo. (Mira el ejemplo porque me resulta difícil describirlo bien).

Como puede comprobar, la secuencia $143$ no aparecerá la lista. Así que no volverá a contar la combinación representada por $134$ .

---

Ejemplo:

Considere el caso $C(5,3)$ :

$ n:12345\\ r:123$

Que $5\not=3$ , por lo que la siguiente es $12(3+1)=124$ .

Cuando $r$ es $145$ entonces $5=5,4=4,3\not=1$ Así que $145\to 1\_\ \_\to 2\_\ \_\to 2\ 3\ \_\to 2\ 3\ 4\to 234$ .

Y en realidad se puede empezar desde cualquier secuencia $a_1a_2a_3$ s.t. $a_1<a_2<a_3$ . Así que $245\to345$ y este es el final de $C(5,3)$ ¡!

---

$^{\dagger}$ si quiere sumergirse en los detalles del código, consulte mi pequeño programa en C++ La función tiene sólo quince líneas. Pero en general no importa el lenguaje que haya utilizado, la lógica es la misma, se llama algoritmo .

Answer 2

Lo que necesitamos es dividir el conjunto $A$ con $X$ elementos en dos subconjuntos $C$ y $D$ con al menos dos elementos cada uno.

Para dividir esto en dos conjuntos de tamaño $x$ y $X-x$ podemos seleccionar al azar $x$ elementos. Podemos hacerlo en $\binom{X}{x}$ maneras. Tenga en cuenta que la selección de $X-x$ elementos fuera de $X$ daría el mismo resultado. Por lo tanto, tenemos que hacer agrupaciones para $x\leq \left\lfloor\frac{X}{2}\right\rfloor$

Por último, el número de elementos que se dividen en dos bandejas con al menos dos elementos cada una es igual a

$$\sum_{x=2}^{\left\lfloor\frac{X}{2}\right\rfloor}\binom{X}{x}$$

Por ejemplo, para $X=7$ tenemos $$\sum_{x=2}^{3}\binom{7}{x} = \binom{7}{2}+\binom{7}{3}=21+35=56 $$

El algoritmo podría representarse simplemente con el siguiente código python:

import math

X=7
possibleLengths=range(2, int(math.floor(X/2))+1)

def GetAllPossibleSubsets(prefix, minimumValue, numberOfElements):
  if numberOfElements == 0:
    print prefix
    return
  if X-minimumValue < numberOfElements:
    return 
  for x in range(minimumValue, X):
    GetAllPossibleSubsets(prefix+[x], x+1, numberOfElements-1)

for x in possibleLengths:
  GetAllPossibleSubsets([], 0, x)