Is there a name for this set/array operation?

Question

Given the input array

[a,b,c,d,e]

and a 'join' function (a,b) => (a+b)

my code returns the following array of arrays, containing each possible variation obtained by applying the join function to various pairs of elements whilst maintaining the order:

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

Visually, what I'm trying to do is this:

The code works but I have no idea what to call it - and would like to use a name that other developers familiar with this operation will understand, should such a name exist. It's not a power set but it is something similar... does this particular set/array operation have a name?

EDIT: OK. They're not permutations; permutations would all be 5-element arrays in different orders [[a,b,c,d,e], [e,d,c,b,a], [a,d,b,c,e], ...]

They're not partitions, since any subset can only contain adjacent elements of the input. - in other words, partitions would allow this:

(This probably arises from pure set theory having no notion of an ordered set.)

They're not combinations since every element of the output uses every member of the input set exactly once.

I think myArray.OrderedPartitions((a,b) => (a+b)) is probably a suitably succinct and explanatory.

Answer 1

As mbeckish said in a comment, those sets are (once an order on the original set is fixed) isomorphic to order-dependent integer partitions, which apparently are commonly referred to as compositions. There are exactly 2^n-1 compositions of every set. For every 1 ≤ k ≤ n, there are exactly (n-1) choose (k-1) compositions of n elements into k sets, preserving the order of the set you started out with. To visualize it, think of the elements of your set put in order and a space between elements that are neighbours in that order; think of your example as A|B|C|D|E. You will notice that there are exactly n-1 possible borders. To create a k-composition, you need only choose k-1 of those possible borders, which may or may not be the way you generated your sets. Summing all (n-1) choose (k-1) for k from 1 to n then gives us 2^n-1 as the number of possible compositions.

Answer 2

After your edit - these are all partitions of an array (and their count is 2^(n-1), because you can replace any divider(colon) by joiner(+)).

Note - these are array partitions, not set partitions.

Answer 3

[The poster's major edit made my answer obsolete, this was about the original question posted:] The online encyclopedia of integer sequences mentions these briefly as 'interval subsets'. (http://oeis.org/A000124) I would stick with this one, it's quite descriptive.

Answer 4

It's a directed tree that points away from the root node:

It's important to note that you do not declare the order of your sets important, only that order is maintained with each set. The python code to generate your "partitions" via your "join":

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

How about myArray.possibleChainings() or myArray.possibleLinkings() ?

The idea is that it looks like you are chaining or linking at least two elements together. I find it also intuitive because you cannot chain or link elements together which are not neighbors.