arrays - tablas - matlab insertar tabla

¿Hay un nombre para esta operación de conjunto/matriz?

Question

Dada la matriz de entrada

[a,b,c,d,e]

y una función de ''unirse'' (a,b) => (a+b)

mi código devuelve el siguiente conjunto de matrices, que contiene cada variación posible obtenida al aplicar la función de unión a varios pares de elementos mientras se mantiene el orden:

[
  [a,b,c,d,e],
  [a,b+c,d,e],
  [a,b+c+d,e],
  [a,b,c+d,e],
  [a+b,c,d,e],
  [a+b,c+d,e],
  [a+b+c,d,e],
  [a+b+c+d,e],
  [a,b,c,d+e],
  [a,b+c,d+e],
  [a,b+c+d+e],
  [a,b,c+d+e],
  [a+b,c,d+e],
  [a+b,c+d+e],
  [a+b+c,d+e],
  [a+b+c+d+e],
]

Visualmente, lo que estoy tratando de hacer es esto:

El código funciona pero no tengo idea de cómo llamarlo, y me gustaría usar un nombre que otros desarrolladores familiarizados con esta operación entiendan, en caso de que exista dicho nombre. No es un conjunto de energía, pero es algo similar ... ¿esta operación de conjunto / conjunto particular tiene un nombre?

EDITAR: OK. No son permutaciones ; todas las permutaciones serían matrices de 5 elementos en diferentes órdenes [[a,b,c,d,e], [e,d,c,b,a], [a,d,b,c,e], ...]

No son particiones , ya que cualquier subconjunto solo puede contener elementos adyacentes de la entrada. - En otras palabras, las particiones permitirían esto:

(Esto probablemente se debe a que la teoría de conjuntos puros no tiene noción de un conjunto ordenado).

No son combinaciones, ya que cada elemento de la salida usa a cada miembro del conjunto de entrada exactamente una vez.

Creo que myArray.OrderedPartitions((a,b) => (a+b)) es probablemente un sucinto y explicativo.

Answer 1

¿Qué hay de myArray.possibleChainings () o myArray.possibleLinkings ()?

La idea es que parece que estás encadenando o enlazando al menos dos elementos juntos. Lo encuentro también intuitivo porque no se pueden encadenar o enlazar elementos que no sean vecinos.

Answer 2

Como mbeckish dijo en un comentario, esos conjuntos son (una vez que se fija un orden en el conjunto original) particiones enteras isomorfas a enteras, que aparentemente se conocen como compositions . Hay exactamente 2 ^n-1 composiciones de cada conjunto. Por cada 1 ≤ k ≤ n , existen exactamente (n-1) choose (k-1) composiciones (n-1) choose (k-1) de n elementos en k conjuntos, preservando el orden del conjunto con el que comenzó. Para visualizarlo, piense en los elementos de su conjunto ordenados y en un espacio entre los elementos que son vecinos en ese orden; piensa en tu ejemplo como A|B|C|D|E Notarás que hay exactamente n-1 fronteras posibles. Para crear una composición k, solo necesita elegir k-1 de esos bordes posibles, que pueden o no ser la forma en que generó sus conjuntos. Sumando todo (n-1) choose (k-1) para k de 1 a n luego nos da 2 ^n-1 como el número de composiciones posibles.

Answer 3

Después de su edición, estas son todas las particiones de una matriz (y su recuento es 2 ^ (n-1), porque puede reemplazar cualquier divisor (dos puntos) por joiner (+)).

Nota: estas son particiones de matriz, no particiones establecidas.

Answer 4

Es un árbol dirigido que apunta lejos del nodo raíz:

Es importante tener en cuenta que no declara que el orden de sus conjuntos sea importante, solo que el orden se mantiene con cada conjunto. El código de Python para generar sus "particiones" a través de su "unirse":

A = map(list, list(''abcde''))

def join(A):
    B = []
    for x1,x2 in zip(A,A[1:]):
        B.append((x1,x2,sorted(list(set(x1+x2)))))
    return B
def label(x):
    return ''+''.join(x)

# Draw the graph with networkx
import networkx as nx
G = nx.DiGraph()

while len(A)>1:
    B = join(A)
    for x1,x2,pair in B:
        print label(x1), label(pair)
        G.add_edge(label(x1),label(pair))
        G.add_edge(label(x2),label(pair))
    A = [x[2] for x in B]

nx.write_dot(G,''test.dot'')

# Render the graph to an image
import os
os.system(''dot -Tpng test.dot > test.png'')

Answer 5

[La edición principal del póster hizo que mi respuesta quedara obsoleta, se trataba de la pregunta original publicada:] La enciclopedia en línea de secuencias de enteros las menciona brevemente como ''subconjuntos de intervalo''. ( http://oeis.org/A000124 ) Me quedaría con este, es bastante descriptivo.