- 732
- 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