[R] Multiset Permutations

From: Stropharia <stevenworthington_at_hotmail.com>
Date: Sun, 06 Apr 2008 13:57:07 -0700 (PDT)

Dear R users,

I want to perform an exact permutation of multisets. I have looked at the coin package, but it doesn't seem to offer what I am looking for. I want to perform permutations (exact - without duplications) on multisets of scalars (e.g., the multiset 0,0,1,2,2). I want to output all the possible permutations into a data frame so that each multiset permutation occupies a row (or column). The output would look something like this:

00122
01220
01210
20201
10202

12200
etc...

There seem to be numerous algorithms in the primary statistical literature for doing this, but they haven't been implemented in R. I've been searching for weeks online and in books for a way of doing this, but the only thing i've come across is a Java script posted anonymously on a forum. I don't know Java at all, so can't make enough sense of it to try a translation into R, but i thought i'd include it below in case someone can glean from this a way of doing it in R. Thanks in advance for any help on this, it is greatly appreciated.

Here are the original (anonymous) poster's comments and code:

"We definitely need to use recursion. There can be up to n! permutations. For example we'll use recursion to generate a tree of n! leaves. Each node is a run of the recursive function. The root node has n children, the nodes at the second level have each n-1 children, the nodes at the third level have n-2 children, etc. Each leaf of this tree will be a permutation. The idea is to add an element to the permutation, remove it from the set, and call the recursive function on that set. Because it's a multiset i'm using a Hashtable to eliminate duplicate entries. A pointer to the Hashtable gets passed along with each recursive call.
The recursive function will know that it's on a "leaf" when the size of the set is 0, at which point it will insert its permutation in the Hashtable. Since identical permutations map to the same "bucket" in the hashtable, they overwrite eachother to leave only unique permutations. Here's the algorithm in Java:"

public class Test {

        public static void PermutationsRecursive(char[] s, String p, Hashtable perms){

		for(int x=0; x<s.length; x++){
			String np = new String(p);
			char[] ns = new char[s.length-1];
			int y = 0;
			for(int z=0; z<s.length; z++){
				if(z != x) ns[y++] = s[z];
			}
			np = np + s[x];
			if(ns.length == 0) perms.put(np, new Boolean(true));
			else PermutationsRecursive(ns, np, perms);
		}

}
public static String[] GetPermutations(char[] in){ int fact = Factorial(in.length); Hashtable perms = new Hashtable(fact); PermutationsRecursive(in, "", perms); Enumeration e = perms.keys(); String[] out = new String[perms.size()]; int i = 0; while(e.hasMoreElements()){ out[i++] = (String) e.nextElement(); } return out;
}
private static int Factorial(int n){ int fact = 1; for(int i=2; i<=n; i++){ fact *= i; } return fact;
}
public static void main(String[] args){ char[] set = new char[]{'A', 'A', 'B', 'C'}; String[] perms = GetPermutations(set); Arrays.sort(perms, String.CASE_INSENSITIVE_ORDER); for(int i=0; i<perms.length; i++){ System.out.println(perms[i]); }
}

}
-------------------------  END JAVA CODE  -----------------------------

This code prints the following:
AABC
AACB
ABAC
ABCA
ACAB
ACBA
BAAC
BACA
BCAA
CAAB
CABA
CBAA

-- 
View this message in context: http://www.nabble.com/Multiset-Permutations-tp16529735p16529735.html
Sent from the R help mailing list archive at Nabble.com.

______________________________________________
R-help_at_r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Received on Sun 06 Apr 2008 - 20:59:22 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Sun 06 Apr 2008 - 23:30:27 GMT.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.

list of date sections of archive