Algoritmo para generar todas las combinaciones de lista de conjuntos con hasta un elemento por conjunto

Question

Algoritmo para generar todas las combinaciones de lista de conjuntos con hasta un elemento por conjunto

binario
multiconjuntos
algoritmos
Matemáticas
combinatoria

Mahoní

Para una lista dada de conjuntos donde los elementos de los conjuntos no comparten ningún elemento entre los conjuntos, quiero calcular todas las combinaciones posibles donde una combinación puede tener hasta un elemento por conjunto. Por ejemplo:

{{a}, {b1, b2}}

Produciría:

{ Ø, {a}, {b1}, {b2}, {a, b1}, {a, b2}}

Supuse que para cualquier juego múltiple dado con $n$ conjuntos donde conjunto $n$ tiene $k_n$ elementos hay:

(k_{1} + 1) \times (k_{2} + 1) + \dots + (k_{norte} + 1)

$(k_1 + 1) \times (k_2 + 1) + \dots + (k_n + 1)$ posibles combinaciones. Mi enfoque algorítmico hasta ahora me ha llevado a codificar todas las combinaciones posibles manteniendo

n

$n$ registros donde cada registro puede contar desde

0

$0$ a

k_{n} + 1

$k_n + 1$ . Para el ejemplo anterior, esto se vería así:

{0, 0} - Ø
{0, 1} - b1
{0, 2} - b2
{1, 0} - a
{1, 1} - a, b1
{1, 2} - a, b2

Luego uso esos números para asignarlos a los números en los conjuntos. Esto funciona, pero para realizar un seguimiento de qué número debe fluir y cuáles deben restablecerse, tengo que revisar cada número en el registro.

¿Existe una forma más eficiente, por ejemplo, codificar todos los estados diferentes en un solo número? Intenté hacer esto con un número binario e intenté determinar el elemento del conjunto con operaciones bit a bit, pero me encontré con un problema en el que este ejemplo no funciona:

0|00 - Ø
0|01 - b1
0|10 - b2
1|00 - a      <-- the consecutive number here would be 011
1|01 - a, b1
1|10 - a, b2

SlipEterno

¿Por qué necesitas que los números binarios sean consecutivos? Solo cámbialo a

\begin{aligned} 0 & 00 & \emptyset \\ 0 & 01 & {b_{1}} \\ 0 & 10 & {b_{2}} \\ 0 & 11 & inválido \\ 1 & 00 & {a} \\ 1 & 01 & {a, b_{1}} \\ 1 & 10 & {a, b_{2}} \\ 1 & 11 & inválido \end{aligned}

$\begin{array}{r|l-c} 0 & 00 & \emptyset \\ 0 & 01 & \{b_1\} \\ 0 & 10 & \{b_2\} \\ 0 & 11 & \text{invalid} \\ 1 & 00 & \{a\} \\ 1 & 01 & \{a,b_1\} \\ 1 & 10 & \{a,b_2\} \\ 1 & 11 & \text{invalid}\end{array}$

Mahoní

@SlipEternal Entonces podría omitir ciertas iteraciones, pero mi pregunta sería, ¿cómo sé qué números omitir y, por lo tanto, también cuántos pasos más necesito? Parece que el primer registro es cada 4 pasos, lo que tiene sentido dado que necesito dos bits para codificar todos los estados. ¿Precalcularía las combinaciones no válidas?

SlipEterno

Suponga que tiene este algoritmo que codifica y decodifica una combinación particular. Preguntas: ¿Cuál sería la entrada al algoritmo de decodificación? ¿Solo la cadena de bytes codificada? O también estarías pasando

n

$n$ ? Los diversos

k_{i}

$k_i$ ? ¿Todos los elementos de los conjuntos de componentes? ¿Qué pasa con el algoritmo de codificación? ¿Qué información se considera una entrada?

Mahoní

Mi enfoque actual usa una lista de números como entrada para la decodificación donde cada número representa la cantidad de elementos en un conjunto dado, de esa manera puedo seleccionar directamente el elemento que quiero incluir en la combinación. Para la codificación solo cuento de 0 a

(k_{1} + 1) \times \dots \times (k_{2} + 1)

$(k_1 + 1) \times \dots \times (k_2 + 1)$

Carlos

Parece que su entrada es solo una lista de conjuntos, no un conjunto múltiple . ¿Podemos suponer que los conjuntos dados no tienen elementos en común?

Mahoní

@Karl Tienes razón, no pensé en eso, sí, los elementos de los conjuntos no tienen ningún elemento en común.

DanielV

¿Te importa en absoluto el orden en que se enumeran los conjuntos? También es posible que desee migrar esto a cs.stackexchange.com

Mahoní

@DanielV el orden no importa en absoluto. Buen punto, ni siquiera pensé en eso.

DanielV

FWIW, esto es equivalente a enumerar las hojas de un árbol, donde la raíz tiene

| a | + 1

$|a|+1$ bordes que salen de ella representando

{n i l, a_{0}, a_{1}, \dots}

$\{nil, a_0, a_1, \cdots\}$ . Y cada hijo de la raíz tiene

| b | + 1

$|b| + 1$ bordes que salen de ella representando

{n i l, b_{0}, b_{1}, \dots}

$\{nil, b_0, b_1, \cdots\}$ . Etc.

Mahoní

Entonces, ¿otra forma podría ser construir un árbol repasando cada elemento del conjunto e insertarlos para cada nodo y luego atravesar el árbol?

DanielV

@Mahoni No, no, en realidad no construyas el árbol. Sería enorme. No necesitas construir un árbol para atravesarlo. Pero puede usar el algoritmo transversal de árbol básico para enumerar los conjuntos: suba el árbol hasta que pueda ir a la derecha, vaya a la derecha una vez y luego descienda al niño más a la izquierda.

Respuestas (2)

Algoritmo para generar todas las combinaciones de lista de conjuntos con hasta un elemento por conjunto

¿Por qué necesitas que los números binarios sean consecutivos? Solo cámbialo a $\begin{aligned} 0 & 00 & \emptyset \\ 0 & 01 & {b_{1}} \\ 0 & 10 & {b_{2}} \\ 0 & 11 & inválido \\ 1 & 00 & {a} \\ 1 & 01 & {a, b_{1}} \\ 1 & 10 & {a, b_{2}} \\ 1 & 11 & inválido \end{aligned}$ $\begin{array}{r|l-c} 0 & 00 & \emptyset \\ 0 & 01 & \{b_1\} \\ 0 & 10 & \{b_2\} \\ 0 & 11 & \text{invalid} \\ 1 & 00 & \{a\} \\ 1 & 01 & \{a,b_1\} \\ 1 & 10 & \{a,b_2\} \\ 1 & 11 & \text{invalid}\end{array}$
@SlipEternal Entonces podría omitir ciertas iteraciones, pero mi pregunta sería, ¿cómo sé qué números omitir y, por lo tanto, también cuántos pasos más necesito? Parece que el primer registro es cada 4 pasos, lo que tiene sentido dado que necesito dos bits para codificar todos los estados. ¿Precalcularía las combinaciones no válidas?
Suponga que tiene este algoritmo que codifica y decodifica una combinación particular. Preguntas: ¿Cuál sería la entrada al algoritmo de decodificación? ¿Solo la cadena de bytes codificada? O también estarías pasando $n$ ? Los diversos $k_i$ ? ¿Todos los elementos de los conjuntos de componentes? ¿Qué pasa con el algoritmo de codificación? ¿Qué información se considera una entrada?
Mi enfoque actual usa una lista de números como entrada para la decodificación donde cada número representa la cantidad de elementos en un conjunto dado, de esa manera puedo seleccionar directamente el elemento que quiero incluir en la combinación. Para la codificación solo cuento de 0 a $(k_1 + 1) \times \dots \times (k_2 + 1)$
Parece que su entrada es solo una lista de conjuntos, no un conjunto múltiple . ¿Podemos suponer que los conjuntos dados no tienen elementos en común?
@Karl Tienes razón, no pensé en eso, sí, los elementos de los conjuntos no tienen ningún elemento en común.
¿Te importa en absoluto el orden en que se enumeran los conjuntos? También es posible que desee migrar esto a cs.stackexchange.com
@DanielV el orden no importa en absoluto. Buen punto, ni siquiera pensé en eso.
FWIW, esto es equivalente a enumerar las hojas de un árbol, donde la raíz tiene $|a|+1$ bordes que salen de ella representando $\{nil, a_0, a_1, \cdots\}$ . Y cada hijo de la raíz tiene $|b| + 1$ bordes que salen de ella representando $\{nil, b_0, b_1, \cdots\}$ . Etc.
Entonces, ¿otra forma podría ser construir un árbol repasando cada elemento del conjunto e insertarlos para cada nodo y luego atravesar el árbol?
@Mahoni No, no, en realidad no construyas el árbol. Sería enorme. No necesitas construir un árbol para atravesarlo. Pero puede usar el algoritmo transversal de árbol básico para enumerar los conjuntos: suba el árbol hasta que pueda ir a la derecha, vaya a la derecha una vez y luego descienda al niño más a la izquierda.

Mike Earnest · Answer 1

Sí, hay una manera más eficiente. Dejar

norte = (k_{1} + 1) \times \dots \times (k_{norte} + 1)

$N=(k_1+1)\times\cdots\times(k_n+1)$ sea el número de posibles selecciones. dado un entero

A \in {0, 1, \dots, N - 1}

$A\in \{0,1,\dots,N-1\}$ , puede producir directamente la selección de la siguiente manera. usaré

A % m

$A\newcommand\per{\,\%\,}\per m$ para indicar el resto de

A

$A$ dividido por

m

$m$ , y

A / / m

$A\newcommand\quo{/\!\!/}\quo m$ para denotar

⌊ A / m ⌋

$\lfloor A/m\rfloor$ . Eso es,

A / / m

$A\quo m$ es

A / m

$A/m$ redondeado hacia abajo.

Dejar $s_1=A\per (k_1+1)$ . Tenga en cuenta que hay $k_1+1$ posibilidades de $s_1$ , entonces $s_1$ define nuestra elección para el primer conjunto.
Dejar $s_2=(A\quo (k_1+1))\per (k_2+1)$ . Del mismo modo, hay $(k_2+1)$ valores posibles para $s_2$ , entonces $s_2$ determina nuestra elección del segundo conjunto.
Dejar $s_3=(A\quo [(k_1+1)(k_2+1)])\per (k_3+1)$ . $s_3$ determina la elección del tercer set.

Etcétera. En general, para calcular $s_j$ de $A$ , para cada $j\in \{1,\dots,n\}$ , calculas el producto $(k_1+1)(k_2+1)\cdots(k_{j-1}+1)$ (cuando $j=1$ , este es un producto vacío, igual a $1$ ), luego calcule la división redondeada hacia abajo de $A$ dividido por ese producto, y finalmente establecer $s_j$ ser el resultado de esa división módulo $(k_j+1)$ .

Esto significa que $A$ te da una lista $(s_1,s_2,\dots,s_n)$ que determina su selección por completo. Cada $A\in \{0,1,\dots,N-1\}$ da una selección única, no se saltan números.

"Eficiente" es una palabra complicada. ¿"Eficiente" en qué sentido? ¿Consumo de espacio? Entonces sí, este algoritmo es el más eficiente. Sin embargo, si se trata de complejidad computacional, esto puede no ser más eficiente. Si el espacio es barato y la potencia computacional es costosa, el algoritmo que sugirió el OP está en camino de ser más eficiente.
La cantidad de operaciones requeridas aumenta con cada elemento, eso es cierto, pero también estaba pensando que el producto acumulado podría memorizarse en cada paso.
Esto es hermoso, acabo de intentarlo. La complejidad del tiempo se limita a algo como: $(k_1 + 1) \times \dots \times (k_n + 1) \times n$ . Mi enfoque fue tratar de hacer uso del espacio, pero creo que perdí la complejidad del tiempo nuevamente cuando trato de determinar qué números tengo que incrementar y fluir, termino teniendo que iterar los registros. Supongo que es un poco más eficiente porque no tengo que repetirlos todos, pero en general me encanta la simplicidad que produce.
Además, ¿hay un nombre para este tipo de enfoque? Estaba tratando de detectar ese patrón cuando miraba los intervalos en los que aumentan los números y se seleccionan diferentes elementos de cada conjunto, pero me preguntaba si esto tiene un nombre.
@Mahoni El mejor nombre que se me ocurre es el sistema de numeración radix mixto . En tu publicación, intentamos binario, donde cada posición es una potencia de $2$ . Mi método es un sistema numérico donde hay un $1$ 's lugar, un $(k_1+1)$ lugar, un $(k_1+1)(k_2+1)$ lugar, etc

Carlos · Answer 2

Esta es una buena tarea para un algoritmo recursivo: Para cada elemento $x$ del primer conjunto, iterar recursivamente a través de las combinaciones de los conjuntos restantes, anteponiendo $x$ a cada uno

También hay una función de biblioteca de Python itertools.productque hace la mayor parte del trabajo:

import itertools
mysets = [[None, "a"], [None, "b1", "b2"]]
for combi in itertools.product(*mysets):
    print(combi)

salidas:

(None, None)
(None, 'b1')
(None, 'b2')
('a', None)
('a', 'b1')
('a', 'b2')

Vi eso, curioso de cómo implementan eso github.com/python/cpython/blob/main/Modules/…
Supongo que el enfoque recursivo es el enfoque de fuerza bruta que toma más tiempo en términos de complejidad de tiempo.
No, el enfoque recursivo es óptimo (lineal en el tamaño de salida).
Generar un producto cartesiano solo es costoso desde el punto de vista computacional debido a la gran cantidad de resultados; un algoritmo razonable de "fuerza bruta" no está haciendo ningún trabajo innecesario.

Algoritmo para generar todas las combinaciones de lista de conjuntos con hasta un elemento por conjunto

Mahoní

SlipEterno

Mahoní

SlipEterno

Mahoní

Carlos

Mahoní

DanielV

Mahoní

DanielV

Mahoní

DanielV

Respuestas (2)

Mike Earnest

SlipEterno

Mahoní

Mahoní

Mahoní

Mike Earnest

Carlos

Mahoní

Mahoní

Carlos

Carlos

juego de busqueda por permutacion

Biyección entre conjuntos y multiconjuntos

Números de Stirling de segundo tipo en Multiset

Cuente el número de cadenas de n bits con un número par de ceros.

Comprobación de Sudoku - sumas suficientes

Considere la siguiente subrutina, ¿cuál es el tiempo de ejecución?

seleccionar secuencia sin "ABCD"

rutas-modificadas-contando-en-un-rectángulo

Personas sentadas alrededor de dos mesas con sillas numeradas

Complejidad del algoritmo: bucle for dentro del bucle while; decreciendo por el factor 2