Groupings

Groupings[n,k]

gives a list of all possible groupings of 1,…,n taken k at a time.

Groupings[{a1,…,an},k]

gives all possible groupings of a1,…,an taken k at a time.

Groupings[{{a1,a2,…},{b1,b2,…},…},k]

gives the combination of all possible groupings of each of the lists ai,bi,… taken k at a time.

Groupings[aspec,fk]

gives all possible groupings of aspec taken k at a time with the function f applied at each level.

Groupings[aspec,{f1k1,f2k2,…}]

gives all possible groupings in which the function fi is applied to ki elements.

Groupings[aspec,{{f1k1,m1},{f2k2,m2},…}]

allows at most mi occurrences in a given grouping of fi applied to ki elements.

Groupings[aspec,kspec,h]

wraps the function h around each grouping generated.

Details

  • Groupings[n,k] can be thought of as generating a list of k-ary expression trees with n leaves.
  • In Groupings[{a1,…,an},k], the integer n gives the number of leaves on the tree and k gives the number of children of each node.
  • Arities k and ki must be positive integers.
  • With an arity specification f->{k,Orderless}, Groupings returns only one representative for each collection of expressions whose tree structure is equivalent up to permutation of the branches of f.

Examples

open allclose all

Basic Examples  (5)

Construct all binary expression trees with four leaves:

Visualize them:

Construct all ternary trees with leaves in the given list:

Construct groupings from several lists of leaves:

Construct all binary trees with three leaves in the given list:

Use different heads with different arities:

Scope  (8)

Construct binary groupings from tuples of elements:

Construct groupings of mixed arities and with all possible reorderings of the leaves:

Construct groupings with any head and arity:

Construct groupings with different heads of the same arity:

Construct groupings using different arities for the same head:

Construct groupings using different heads with different arities:

By default, Groupings returns all possible permutations of the branches of the trees:

Return representatives of those classes of groupings that cannot be obtained by permutation:

Use any combination of heads, arities, and ordering properties:

Applications  (5)

Combine three 1s using the binary operations +,* in all possible ways:

These are their respective values:

Find out the frequencies of all possible results of combining seven 1s with the binary operations +,*:

For a given integer n, the minimum number of 1s needed to construct n using +,* is called the complexity of n. For example, the complexity of 12 is 7:

Construct all possible expressions formed by some variables and binary functions:

Avoid evaluation of the results:

There are 3840 forms of combining the integers 1, 1, 5, 8 and binary operations +, -, *, /:

Find out their respective results, many of them involving division by 0:

Find out the only combination that produces 10:

The most frequent result is 13:

Construct logical propositions containing two atomic propositions and their negations, using some binary connectives:

Convert to disjunctive normal form:

Those correspond to the 16 Boolean functions with two variables:

Construct all expressions containing these six complex numbers, using binary heads Plus and Times:

The distribution of points is not so regular in general:

Properties & Relations  (5)

A tree with heads of arity k and n leaves has (n-1)/(k-1) internal nodes, so this number must be an integer:

Otherwise the result is an empty list:

In particular, that means that Groupings[n,k] gives {} for k>n:

The number of binary groupings with n leaves is given by the (n-1)^(th) Catalan number:

The number of k-ary groupings with n leaves is related to the Fuss–Catalan number:

3-ary groupings:

4-ary groupings:

Leaves are distributed keeping the order at the deepest level:

Groupings[{a1,…,an},n] returns {{a1,…,an}}:

Possible Issues  (1)

This is interpreted as representing the presence of head h with arity 3 and head List with arity 2:

To have the head h with arity 3 at most twice, use an additional level of list:

Introduced in 2016
 (11.0)