Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Multiset Permutations

  1. Dec 31, 2006 #1
    Does anyone know of any algorithms that will list all permutations of a given multiset? :redface:
     
  2. jcsd
  3. Jan 1, 2007 #2

    -Job-

    User Avatar
    Science Advisor

    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 (Text):
    _
    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 (Text):
    _
    A
    So first we double up:
    Code (Text):
    _
    A
    _
    A
    And append B to the second half:
    Code (Text):
    _
    A
    B
    AB
    (where _X = X)

    Repeating this process with the element C:
    Double up:
    Code (Text):

    _
    A
    B
    AB
    _
    A
    B
    AB
     
    And append:
    Code (Text):

    _
    A
    B
    AB
    C
    AC
    BC
    ABC
     
    ... and so on. So you can turn this into a recursive function, i used Java:
    Code (Text):

    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 (Text):

    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.
     
  4. Jan 1, 2007 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  5. Jan 1, 2007 #4

    -Job-

    User Avatar
    Science Advisor

    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 eachother to leave only unique permutations.
    Here's the algorithm in Java:
    Code (Text):

    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 (Text):

    AABC
    AACB
    ABAC
    ABCA
    ACAB
    ACBA
    BAAC
    BACA
    BCAA
    CAAB
    CABA
    CBAA
     
     
    Last edited: Jan 1, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Multiset Permutations
  1. Permutations with BFS (Replies: 4)

Loading...