Constant Time Generation of Integer Partitions

Katsuhisa YAMANAKA; Shin-ichiro KAWANO; Yosuke KIKUCHI; Shin-ichi NAKANO

doi:10.1093/ietfec/e90-a.5.888

Constant Time Generation of Integer Partitions

Katsuhisa YAMANAKA, Shin-ichiro KAWANO, Yosuke KIKUCHI, Shin-ichi NAKANO

Full Text Views

0

Share
Cite this

Summary :

In this paper we give a simple algorithm to generate all partitions of a positive integer n. The problem is one of the basic problems in combinatorics, and has been extensively studied for a long time. Our algorithm generates each partition of a given integer in constant time for each without repetition, while best known algorithm generates each partition in constant time on "average." Also, we propose some algorithms to generate all partitions of an integer with some additional property in constant time.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.5 pp.888-895

Publication Date: 2007/05/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e90-a.5.888

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Katsuhisa YAMANAKA, Shin-ichiro KAWANO, Yosuke KIKUCHI, Shin-ichi NAKANO, "Constant Time Generation of Integer Partitions" in IEICE TRANSACTIONS on Fundamentals, vol. E90-A, no. 5, pp. 888-895, May 2007, doi: 10.1093/ietfec/e90-a.5.888.
Abstract: In this paper we give a simple algorithm to generate all partitions of a positive integer n. The problem is one of the basic problems in combinatorics, and has been extensively studied for a long time. Our algorithm generates each partition of a given integer in constant time for each without repetition, while best known algorithm generates each partition in constant time on "average." Also, we propose some algorithms to generate all partitions of an integer with some additional property in constant time.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e90-a.5.888/_p

Copy

@ARTICLE{e90-a_5_888,
author={Katsuhisa YAMANAKA, Shin-ichiro KAWANO, Yosuke KIKUCHI, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Constant Time Generation of Integer Partitions},
year={2007},
volume={E90-A},
number={5},
pages={888-895},
abstract={In this paper we give a simple algorithm to generate all partitions of a positive integer n. The problem is one of the basic problems in combinatorics, and has been extensively studied for a long time. Our algorithm generates each partition of a given integer in constant time for each without repetition, while best known algorithm generates each partition in constant time on "average." Also, we propose some algorithms to generate all partitions of an integer with some additional property in constant time.},
keywords={},
doi={10.1093/ietfec/e90-a.5.888},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - Constant Time Generation of Integer Partitions
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 888
EP - 895
AU - Katsuhisa YAMANAKA
AU - Shin-ichiro KAWANO
AU - Yosuke KIKUCHI
AU - Shin-ichi NAKANO
PY - 2007
DO - 10.1093/ietfec/e90-a.5.888
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E90-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2007
AB - In this paper we give a simple algorithm to generate all partitions of a positive integer n. The problem is one of the basic problems in combinatorics, and has been extensively studied for a long time. Our algorithm generates each partition of a given integer in constant time for each without repetition, while best known algorithm generates each partition in constant time on "average." Also, we propose some algorithms to generate all partitions of an integer with some additional property in constant time.
ER -