File Exchange

image thumbnail

PARTITIONS

version 1.1 (3.79 KB) by

Finds all partitions of a set, or only those partitions of a specified length. Includes a viewer.

8 Downloads

Updated

View License

C = PARTITIONS(N), for scalar N, returns all possible partitions of the set given by {1,2,3,...N}.
C = PARTITIONS(N), for vector N, returns the partitions of the vector elements, treated as members of a set.
C = PARTITIONS(N), for cell N, returns the partitions of the cell
elements treated as members of a set.

PARTITIONS(N,K) returns only the partitions of length K.
The results are stored in a cell array. For example:

The 15 partitions set {1 2 3 4}:
{1 2 3 4}
{1 2 3} {4}
{1 2 4} {3}
{1 2} {3 4}
{1 2} {3} {4}
{1 3 4} {2}
{1 3} {2 4}
{1 3} {2} {4}
{1 4} {2 3}
{1} {2 3 4}
{1} {2 3} {4}
{1 4} {2} {3}
{1} {2 4} {3}
{1} {2} {3 4}
{1} {2} {3} {4}

Also included is a viewer function, PARTDISP, which allows for easy viewing of the partitions. The output is a string to the command window.

C = partitions({'peanut','butter','yummy'});
partdisp(C)

The 5 partitions of set {peanut butter yummy}:
{peanut butter yummy}
{peanut butter} {yummy}
{peanut yummy} {butter}
{peanut} {butter yummy}
{peanut} {butter} {yummy}

Please: READ THE HELP BEFORE USING.
Please email me if bugs are found in the code.
Thanks.

Comments and Ratings (6)

Thanks!

Joshua C

The file is excellent, useful, and well documented.

Michael

Very useful function. I made a couple of tweaks.

- I added another "easy case" when N==K to speed up that situation
- I put a "round" at the end of the Stirling function because sometimes I wasn't getting an integer output, for example when I tried stirling(15,15). There may be a better way to handle this than just doing a round.

Excellent, useful file. Well commented and concisely coded.

Loginatorist

Loginatorist (view profile)

An update has been submitted which allows user to enter the set to be partitioned. For example: partitions(['a','b','c'])

Bruno Luong

Bruno Luong (view profile)

It needs some guts to tackle the partitioning problem in a non-recursive way. Matt has done it, great educational code.

Updates

1.1

Added viewer, capability for user to specify set.

MATLAB Release
MATLAB 7.4 (R2007a)
Acknowledgements

Inspired by: Set partition

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video