Algorithm for All Multiset Permutations

In summary, we discussed the use of a recursive algorithm to list all permutations of a given multiset. The algorithm involves duplicating the previous list of permutations and appending the new element to the duplicates. This process is repeated with each added element until all permutations are obtained. For a multiset of n elements, this algorithm has a time complexity of O(n!). Additionally, we explored using a Hashtable to eliminate duplicate entries and only retain unique permutations.
  • #1
bomba923
763
0
Does anyone know of any algorithms that will list all permutations of a given multiset? :redface:
 
Technology news on Phys.org
  • #2
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:
Code:
_
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:
Code:
_
A
So first we double up:
Code:
_
A
_
A
And append B to the second half:
Code:
_
A
B
AB
(where _X = X)

Repeating this process with the element C:
Double up:
Code:
_
A
B
AB
_
A
B
AB

And append:
Code:
_
A
B
AB
C
AC
BC
ABC

... and so on. So you can turn this into a recursive function, i used Java:
Code:
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:
Code:
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.
 
  • #3
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
 
  • #4
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:
Code:
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:
Code:
AABC
AACB
ABAC
ABCA
ACAB
ACBA
BAAC
BACA
BCAA
CAAB
CABA
CBAA
 
Last edited:

1. What is an "Algorithm for All Multiset Permutations"?

An "Algorithm for All Multiset Permutations" is a set of instructions or steps that are used to generate all possible combinations or arrangements of a given set of elements, taking into account repeated elements. This algorithm is commonly used in computer science and mathematics for solving problems related to permutations and combinations.

2. How does the Algorithm for All Multiset Permutations work?

The Algorithm for All Multiset Permutations works by systematically generating all possible arrangements of elements in a multiset. It does this by using a recursive approach, where it repeatedly breaks down the multiset into smaller subsets and then combines them to generate all possible permutations. This process continues until all possible permutations have been generated.

3. What is the time complexity of the Algorithm for All Multiset Permutations?

The time complexity of the Algorithm for All Multiset Permutations is O(n!), where n is the number of elements in the multiset. This means that the time taken to generate all permutations grows exponentially with the increase in the number of elements in the multiset.

4. Can the Algorithm for All Multiset Permutations handle repeated elements?

Yes, the Algorithm for All Multiset Permutations is specifically designed to handle repeated elements in a multiset. It takes into account the repeated elements and generates all possible permutations while ensuring that each element appears in the correct frequency in each permutation.

5. In what applications can the Algorithm for All Multiset Permutations be used?

The Algorithm for All Multiset Permutations has various applications in computer science and mathematics, such as in solving problems related to permutations and combinations, in data compression and encryption, and in generating test cases for software testing. It can also be used in fields like genetics, where it is used to study gene sequences and variations.

Similar threads

  • Programming and Computer Science
Replies
9
Views
1K
  • Programming and Computer Science
Replies
8
Views
2K
  • Programming and Computer Science
Replies
3
Views
892
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
7
Views
449
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Programming and Computer Science
Replies
4
Views
2K
  • Programming and Computer Science
Replies
6
Views
932
Replies
9
Views
945
  • Calculus and Beyond Homework Help
Replies
1
Views
552
Back
Top