Algorithm for All Multiset Permutations

[bomba923]

Does anyone know of any algorithms that will list all permutations of a given multiset?

 

[-Job-]

I would go for a recursive algorithm. For example, assuming order is irrelevant, if you have a set with a single element A, then the list of permutations is:

_
A

Where _ denotes the empty set.
If you add a second element, B, to the set you can obtain the list of permutations by:

1. Duplicating the previous list
2. Appending the new element, B, to the items of the duplicated list

For example, we started with:

_
A

So first we double up:

_
A
_
A

And append B to the second half:

_
A
B
AB

(where _X = X)

Repeating this process with the element C:
Double up:

_
A
B
AB
_
A
B
AB

And append:

_
A
B
AB
C
AC
BC
ABC

... and so on. So you can turn this into a recursive function, i used Java:

import java.util.*;

public class Test {
	private static void Recursive(char[] s, String[] p, int i){
		if(i > 0){
			Recursive(s, p, i-1);
			//double up
			int mid = new Double(Math.pow(2, i)).intValue();
			for(int x=0; x<mid; x++){
				p[mid+x] = p[x];
			}
			//append
			for(int x=mid; x<2*mid; x++){
				p[x] += s[i];
			}
		}else{
			p[0] = "";
			p[1] = "" + s[0];
		}
	}
	public static void GetPermutations(char[] in, String[] out){
		Recursive(in, out, in.length-1);
	}
	public static void main(String[] args){
		char[] set = new char[]{'a', 'b', 'c', 'd', 'e'};
		String[] perms = new String[new Double(Math.pow(2, set.length)).intValue()];
		GetPermutations(set, perms);
		Arrays.sort(perms, String.CASE_INSENSITIVE_ORDER);
		// print all permutations
		for(int i=0; i<perms.length; i++){
			System.out.println(i + ":   " + perms[i]);
		}
	}
}

Before i print the permutations i sort the array, but this depends on your needs.
A run of the program prints:

0:   
1:   a
2:   ab
3:   abc
4:   abcd
5:   abcde
6:   abce
7:   abd
8:   abde
9:   abe
10:   ac
11:   acd
12:   acde
13:   ace
14:   ad
15:   ade
16:   ae
17:   b
18:   bc
19:   bcd
20:   bcde
21:   bce
22:   bd
23:   bde
24:   be
25:   c
26:   cd
27:   cde
28:   ce
29:   d
30:   de
31:   e

Which looks ok.

 

[Hurkyl]

You listed the subsets of a set, not the permutations of a multiset.

If you had {A, A, B, C}, he's looking for the list

AABC
AACB
ABAC
ACAB
ABCA
ACBA
BAAC
CAAB
BACA
CABA
BCAA
CBAA

 

[-Job-]

You're right, i don't know why i was thinking subsets.
Then 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 each other to leave only unique permutations.
Here's the algorithm in Java:

import java.util.*;

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]);
		}
	}
}

It prints the following:

AABC
AACB
ABAC
ABCA
ACAB
ACBA
BAAC
BACA
BCAA
CAAB
CABA
CBAA