Today's Question:  What's your opinion about Alibaba mooncake incident?        GIVE A SHOUT

Technical Article => Programming =>  Java

Permutation implementation in Java

  sonic0002      2015-03-26 02:18:14      4,356    4    2

Permutation is a very basic and important mathematic concept we learned in school. It has very practical applications in real world. For example, in football.

In simple, permutation describes all possible ways of doing something. For example, there are six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). In general, for n items, there are n! number of permutations to arrange these items. How can we implement this algorithm in programming programming language such as Java? Below is a simple code snippet which uses the recursive method. It's quite self-explained.

import java.io.FileNotFoundException;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class Permutation {
    //The entry of the permutation method
    public static <T> List<T[]> permute(T[] arr){
        List<T[]> result = new ArrayList<T[]>();
        permute(new ArrayList(), Arrays.asList(arr), result);
        return result;
    }
     
    // This is the actual method doing the permutation
    // The rationale here is pre will contain the elements which have been permuted,
    // cur will contain the elements to be permuted. If the cur contains no element,
    // the pre will contain the permuted elements, hence it will be outputed.
    // For example : assume we have [1, 2, 3], at the beginning, pre will be empty and
    // cur will contain [1, 2, 3], in the first loop, pre will become [1] and cur will
    // be [2, 3], then in the recursive permute(0 call, pre will be [1, 2] and cur will
    // be [3]....when cur contains no element, pre will be [1, 2, 3] and it will be out.
    // Then we are going to next loop ...
    private static <T> void permute(List pre, List cur, List<T[]> out){
        int size = cur.size();
         
        if(size == 0){
            out.add((T[])pre.toArray());
        } else {
            for(int i=0; i<size; ++i){
                List tmpPre = new ArrayList(pre);
                List tmpCur = new ArrayList(cur);
                tmpPre.add(cur.get(i));
                tmpCur.remove((T)cur.get(i));
                 
                permute(tmpPre, tmpCur, out);      
            }
        }
    }
     
    //Print each row of the permuted values
    public static <T>  void print(List<T[]> list, OutputStream out, char delim){
        try{
            for(T[] i : list){
                int count = 0;
                for(T t : i){
                    if(++count == i.length){
                        out.write((t.toString()).getBytes());
                    } else{
                        out.write((t.toString()+delim).getBytes());
                    }
                }
                out.write("\n".getBytes());
            }
        } catch (Exception ex){
            ex.printStackTrace();
        }
    }
 
    public static void main(String[] args) throws FileNotFoundException {
        Integer[] ints = new Integer[] {1, 2, 3, 4};
        Permutation.print(Permutation.permute(ints), System.out, ',');
         
        Character[] chars = {'a', 'b', 'c', 'd', 'e'};
        Permutation.print(Permutation.permute(chars), new PrintStream("permute.txt"), ' ');
         
        String[] strs = {"abc", "123"};
        Permutation.print(Permutation.permute(strs), System.err, ' ');
    }
}

After calling Permutation.permute(), you will get a result set which contains all the permutations of the items you want to permute. Thereafter the result set can be printed out or written in a file. The delimiter can also be specified to separate the items in each permutation.

This implementation can be reimplemented in other languages as well. Here is one implemented with JavaScript.

JAVA PERMUTATION IMPLEMENTATION SAMPLE

  SAVE AS PDF   MARK AS READ   MARK AS IMPORTANT

  RELATED


  4 COMMENTS


Strongme [Reply]@ 2015-03-27 01:32:17

T[] is not compiled correctlly?

Is there a specific version of java?

sonic0002 [Reply]@ 2015-03-27 04:06:16

Sorry, it's our internal WYSIWYG editor problem. Have fixed it. You should be able to compile it now.

strongme [Reply]@ 2015-03-27 05:22:33

I mean i typed the code into my ide not copy 

what,s the version of your java?

 

sonic0002 [Reply]@ 2015-03-27 06:23:20

I am using Java 80:

C:\Program Files\Java\jre1.8.0_31\bin>java -version
java version "1.8.0_31"
Java(TM) SE Runtime Environment (build 1.8.0_31-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.31-b07, mixed mode)

I have tested it with Java 70 as well.


  WRITE ARTICLE

How recursion works

By sonic0002