Generation of All Possible Multiselections from a Multiset

Thomas Wieder

Abstract


The concept of a [k1, k2,..., kK]-selection applied on a multiset is introduced and an algorithm is outlined to generate all [k1, k2,..., kK]-selections from a given multiset.

Key words: Multiselection; Mutiset; Contingency matrix; Combinatories

References


Diaconis, P., & Gangolli, A. (1995). Rectengular Arrays with Fixed Margins. In D. Aldous (Ed.), Discrete Probability and Algorithms (pp. 15-41). New York: Springer Verlag.

Greselin, F. (2003). Counting and Enumerating Frequency Tables with Given Margins.

O’Connor, D. (2006). A Minimum Change Algorithm for Generating Lattice Points. Retrieved from http://www.derekroconnor.net.

Saunders, I. (1984). Algorithm AS 205, Enumeration of R x C Tables with Repeated Row Totals. Journal of the Royal Statistical Society: Series C (Applied Statistics), 33(3), 340-352.

Multiselection.mpl can be found at http://thomas-wieder.privat.t-online.de/Multiselection.mpl. The corresponding Maple 13 worksheet is available at http://www.thomas-wieder.privat.t-online.de/ Multiselection.mw.

Sloane, N. J. A., & Wieder, T. (2004). The Number of Hierarchical Orderings. Order, 21(1), 83-89.

Petrovsky, A.B. (2003). Cluster Analysis in Multiset Spaces. Lecture Notes in Informatics, P-30, 109­-119.

Encyclopedia of Integer Sequence (2011). Retrieved from http://ocis.org/A188667.

The formula is attributed to Percy Alexander MacMahon, but I failed to find it in his Combinatory Analysis and in his Collected Papers.

A Maple program which implements the formula (5) can be found at http://thomas-wieder.privat.t­online.de/MacMahonsMultisetFormula.mpl.

Petrovsky, A.B. (2000). Combinatorics of Multisets. Doklady Mathematics, 61(1), 151-154.

Singh, D., Ibrahim, A.M., Yohanna, T., & Singh, J.N. (2007). An Overview Of the Application of Multisets. Novi Sad Journal of Mathematics, 37, 73-92.

Ciobanu, G., & Gontinea, M. (2009). Encodings of Multisets. International Journal of Foundations of Computer Science, 20(3), 381-393.

Hage, J. (2003). Enumerating Submultisets of Multisets. Information Processing Letters, 85, 221-226.

Ruskey, F., & Savage, C. (1996). A Gray Code for the Combinations of a Multiset. European Journal of Combinatorics, 17, 493-500.

Unpublished, the Corresponding Maple 13 Worksheet Including Source Code is Available at http:// www.thomas-wieder.privat.t-online.de/multichoose.mw.


Full Text: PDF

Refbacks

  • There are currently no refbacks.


Reminder
We only use the follwoing mailboxes to deal with issues about paper acceptance, payment and submission of electronic versions of our journals to databases:
pam@cscanada.org
pam@cscanada.net

Copyright © 2010 Canadian Research & Development Center of Sciences and Cultures
Address: 758, 77e AV, Laval, Quebec, Canada H7V 4A8

Telephone: 1-514-558 6138
Http://www.cscanada.net
Http://www.cscanada.org
E-mail:office@cscanada.net office@cscanada.org caooc@hotmail.com