- #1
bomba923
- 763
- 0
Does anyone know of any algorithms that will list all permutations of a given multiset?
_
A
_
A
_
A
_
A
_
A
B
AB
_
A
B
AB
_
A
B
AB
_
A
B
AB
C
AC
BC
ABC
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]);
}
}
}
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
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]);
}
}
}
AABC
AACB
ABAC
ABCA
ACAB
ACBA
BAAC
BACA
BCAA
CAAB
CABA
CBAA
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.
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.
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.
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.
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.