Code covered by the BSD License  

Highlights from
PARTITIONS

5.0

5.0 | 3 ratings Rate this file 8 Downloads (last 30 days) File Size: 3.79 KB File ID: #24185
image thumbnail

PARTITIONS

by Matt Fig

 

19 May 2009 (Updated 21 May 2009)

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

| Watch this File

File Information
Description

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.

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Set partition

MATLAB release MATLAB 7.4 (R2007a)
Tags for This File  
Everyone's Tags
Tags I've Applied
Add New Tags Please login to tag files.
Comments and Ratings (4)
19 May 2009 Bruno Luong

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

19 May 2009 Matt Fig

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

21 May 2009 Darren Rowland

Excellent, useful file. Well commented and concisely coded.

24 Feb 2010 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.

Please login to add a comment or rating.
Updates
21 May 2009

Added viewer, capability for user to specify set.

Tag Activity for this File
Tag Applied By Date/Time
partition Matt Fig 19 May 2009 10:37:08
restricted growth function Matt Fig 19 May 2009 10:37:08
permutations Matt Fig 19 May 2009 10:37:08
combinatorics Matt Fig 19 May 2009 10:37:08
combinations Matt Fig 19 May 2009 10:37:08
set Matt Fig 21 May 2009 11:20:27

Contact us at files@mathworks.com