Есть ли имя для этой операции set/array?

Учитывая входной массив

[a,b,c,d,e]

и функция 'join' (a,b) => (a+b)

мой код возвращает следующий массив массивов, содержащий каждую возможную вариацию, полученную применением функции соединения к различным парам элементов при сохранении порядка:

[
  [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],
]

Визуально то, что я пытаюсь сделать, это следующее:

Код работает, но я понятия не имею, как его назвать - и хотел бы использовать имя, которое поймут другие разработчики, знакомые с этой операцией, если такое имя существует. Это не набор мощности, но это нечто похожее... имеет ли эта конкретная операция set/array имя?

ИЗМЕНИТЬ: ОК. Они не являются перестановками; перестановки были бы 5-элементными массивами в разных порядках [[a,b,c,d,e], [e,d,c,b,a], [a,d,b,c,e], ...]

Они не разделы, так как любое подмножество может содержать только смежные элементы ввода. - другими словами, разделы позволят это:

(Вероятно, это связано с теорией чистого множества, не имеющей понятия упорядоченного множества.)

Они не являются комбинациями, поскольку каждый элемент вывода использует каждый член ввода, установленный ровно один раз.

Я думаю, что myArray.OrderedPartitions((a,b) => (a+b)), вероятно, достаточно кратким и объяснительным.

Ответ 1

Как сказано в комментарии mbeckish, эти множества (после того, как порядок на исходном множестве фиксирован) изоморфен упорядочиваемым целым разделам, которые, по-видимому, обычно называются композиции. Существует ровно 2 ^n-1 композиции каждого множества. Для каждого 1 ≤ k ≤ n в композиции k есть ровно (n-1) choose (k-1) композиции элементов n, сохраняя порядок набора, с которого вы начали. Чтобы визуализировать это, подумайте об упорядоченных элементах вашего набора и пространстве между элементами, которые являются соседями в этом порядке; подумайте о своем примере как A|B|C|D|E. Вы заметите, что существует ровно n-1 возможных границ. Чтобы создать k-композицию, вам нужно выбрать только k-1 тех возможных границ, которые могут или не могут быть сгенерированы вами. Суммируя все (n-1) choose (k-1) для k от 1 до n, затем дает нам 2 ^n-1 как число возможных композиций.

Ответ 2

После редактирования - это все разделы массива (и их число равно 2 ^ (n-1), потому что вы можете заменить любой разделитель (двоеточие) на столяр (+)).

Примечание. Это разделы массива, а не заданные разделы.

Ответ 3

[Основное изменение плаката сделало мой ответ устаревшим, это было об оригинальном вопросе:] Онлайновая энциклопедия целочисленных последовательностей кратко упоминает их как "интервальные подмножества". (http://oeis.org/A000124) Я бы придерживался этого, он довольно описательный.

Ответ 4

Это ориентированное дерево, которое указывает на корень node:

Важно отметить, что вы не объявляете порядок своих наборов важным, только тот порядок поддерживается с каждым набором. Код python для создания ваших "разделов" через ваше "соединение":

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')

Ответ 5

Как насчет myArray.possibleChainings() или myArray.possibleLinkings()?

Идея состоит в том, что похоже, что вы цепляете или связываете хотя бы два элемента вместе. Я нахожу это также интуитивным, потому что вы не можете цепи или звенья, которые не являются соседями.