Restricted Growth Strings Generator

This online calculator generates restricted growth strings for the given size

This page exists due to the efforts of the following people:

Timur

Timur

Created: 2019-12-22 17:22:15, Last updated: 2020-11-03 14:19:38
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/8531/. Also, please do not modify any references to the original work (if any) contained in this content.

The restricted growth string for a set of n elements is the n-characters string which defines the partition of a set, where each i-th character defines the set block i-th element of a set belongs to.

For example, if we have a set of five elements \{a, b, c, d, e\} and a set partition \{a, c\}, \{b\}, \{d, e\}, the set partition can be defined using the string 01022, which means that a and c belongs to 0-th block, b to 1-st block and d and e to 2-nd block. If the first character is always zero (i.e. first element is always placed to block zero), then characters of the restricted growth string satisfy the inequality
a_i \leq max(a_1, ... a_{i-1}) + 1

Although there are several algorithms to generate all restricted growth strings for given size n of a set, with the above inequality in mind we can write rather trivial recursive algorithm, which is used in the calculator below.

Restricted growth strings are useful for the combinatorial tasks of generating set partitions for a given set.

PLANETCALC, Restricted Growth Strings Generator

Restricted Growth Strings Generator

The file is very large. Browser slowdown may occur during loading and creation.

URL copied to clipboard
PLANETCALC, Restricted Growth Strings Generator

Comments