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.

Ackler

Why [a+b+c+d+e] is missing? – Decisive

@Decisive my mistake :) Edited the question to include the missing permutation. – Ackler

This has to do with partial sums or segment sums, however, that is not an accurate description. – Renaud

The operation creates permutations. Why nit "permute"? – Underlay

off topic here, perhaps this should be on programmers.stackexchange.com ? – Incantation

They are most definitely not permutations of any kind! Permutations are by definition reorderings of the same set of items. Here however, there are no two lists with the same items. – Giddens

CAn you describe what you are doing in a few words? If not can you describe the intent in a few words? It seems that it is doing something like "GetAllJoins" (ie it is getting all the sets derived from applying a join to adjacent elements of the input set or any other set it contains)... I've definitely not seen anything like this before so don't think it has a defined name that is going to be that useful... – Blus

Something like constrained partitioning, except that you only have one group with cardinality > 1 (i.e. I see no [ a+b, c+d, e ]). – Unify

@Iserni - omission on my part. – Ackler

I would call this Order-dependent Integer Partition. It's basically equivalent to all the ways you can write a number as a sum of integers: 1+1+1+1+1 1+1+1+2 1+1+2+1 1+1+3 1+2+1+1 1+2+2 ... – Baun

what program did you use to create the diagrams? – Sharpen

@Sharpen - the diagrams were drawn in Visio (office.microsoft.com/en-gb/visio) – Ackler

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.

Dissimilation

Nice explanation. It may be worth adding that the summation is equal to 2^(n-1). – Kurland

They would indeed appear to be compositions. Thank you :) – Ackler

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.

Angelika

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.

Upperclassman

I wouldn't say it is that descriptive of what it is doing (in that if I saw the name I'd have no idea what I'd expect the function to do - I Can see how the name fits after a lot of though). – Blus

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

Branscum

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.

Ivyiwis