Thread: Permutations

Page 1 of 2 12 LastLast
Results 1 to 10 of 12
  1. #1 Permutations 
    Renown Programmer and Respected Member
    Maxi's Avatar
    Join Date
    Jun 2008
    Posts
    3,197
    Thanks given
    281
    Thanks received
    1,095
    Rep Power
    1366
    I needed some snippet to get the collection of all permutations of any collection of objects and there were no ready to use snippets within 5 minutes of searching google, so I wrote this myself and here it is in case you need it.

    Code:
    import java.util.ArrayList;
    import java.util.Arrays;
    
    /**
     * Generates all permutations of a certain array of values.
     * @author Maxime Meire
     *
     * @param <T> The type of the elements to be permuted.
     */
    public class Permutations<T> {
    	
    	private ArrayList<ArrayList<T>> permutations;
    	
    	public Permutations(T[] values) {
    		permute(values);
    	}
    	
    	private ArrayList<ArrayList<T>> permute(ArrayList<ArrayList<T>> permutations, ArrayList<T> permutation, ArrayList<T> values) {
    		if (values.isEmpty()) {
    			permutations.add(permutation);
    			return permutations;
    		}
    		for (int i = 0; i < values.size(); i++) {
    			ArrayList<T> newValues = new ArrayList<T>();
    			newValues.addAll(values);
    			T value = newValues.remove(i);
    			ArrayList<T> newPermutation = new ArrayList<T>();
    			newPermutation.addAll(permutation);
    			newPermutation.add(value);
    			permute(permutations, newPermutation, newValues);
    		}
    		return permutations;
    	}
    	
    	private ArrayList<ArrayList<T>> permute(T[] values) {
    		ArrayList<ArrayList<T>> permutations = new ArrayList<ArrayList<T>>();
    		permute(permutations, new ArrayList<T>(), new ArrayList<T>(Arrays.asList(values)));
    		return this.permutations = permutations;
    	}
    	
    	public ArrayList<ArrayList<T>> getPermutations() {
    		return permutations;
    	}
    	
    	public void printPermutations() {
    		System.out.println("PRINTING " + permutations.size() + " PERMUTATIONS:");
    		for (ArrayList<T> p : permutations) {
    			String s = "";
    			T value;
    			for (int i = 0; i < p.size(); i++) {
    				value = p.get(i);
    				s += value.toString() + (i == p.size() - 1 ? "" : ",");
    			}
    			System.out.println(s);
    		}
    	}
    
    }
    Reply With Quote  
     

  2. Thankful users:


  3. #2  
    Banned

    Join Date
    Jan 2010
    Posts
    3,664
    Thanks given
    533
    Thanks received
    918
    Rep Power
    0
    Very nice, your rank is well deserved.
    Reply With Quote  
     

  4. #3  
    Valar Morghulis

    Laxika's Avatar
    Join Date
    Sep 2006
    Age
    32
    Posts
    2,813
    Thanks given
    1,804
    Thanks received
    274
    Rep Power
    2128
    I would use a StringBuilder when printing out the permutations, but nice anyways.
    Reply With Quote  
     

  5. #4  
    Banned

    Join Date
    Jan 2012
    Posts
    593
    Thanks given
    527
    Thanks received
    319
    Rep Power
    0
    How could you not find a snippet within 5 minutes...

    Btw you should start using diamond references (since java 6 is just about to reach EOL) & use stringbuilder for your little print method &

    Code:
    ArrayList<T> newValues = new ArrayList<T>();
    to

    Code:
    List<T> newValues = new ArrayList<>();
    (and all others like it)

    2 decouple ur code from the implementation of the list.

    &

    Reply With Quote  
     

  6. #5  
    Renown Programmer and Respected Member
    Maxi's Avatar
    Join Date
    Jun 2008
    Posts
    3,197
    Thanks given
    281
    Thanks received
    1,095
    Rep Power
    1366
    Quote Originally Posted by Bosslad View Post
    How could you not find a snippet within 5 minutes...
    Everything that came up were messy snippets for specific types and a shitload of lines for this simple task, nothing generic ready to go came up which was what I was looking for.

    And yes you're right about using the diamond operator but I still haven't configured my eclipse to use java 7.
    Reply With Quote  
     

  7. #6  
    Registered Member
    Polish Civil's Avatar
    Join Date
    May 2010
    Age
    28
    Posts
    1,345
    Thanks given
    484
    Thanks received
    191
    Rep Power
    463
    Can you tell me what is use for.

    Cant find this in my language. ( translation tells me nothing)

    Thanks.


    nvm got it http://pl.wikipedia.org/wiki/Permutacja


    Reply With Quote  
     

  8. #7  
    ¯̿ ̿|̿ ̿ |̶ ̶ ̶ ̶| |̶͇̿ ̶͇̿ ͇̿ Haskelle

    Join Date
    Nov 2007
    Age
    29
    Posts
    1,227
    Thanks given
    329
    Thanks received
    517
    Rep Power
    1133
    Quote Originally Posted by Bosslad View Post
    How could you not find a snippet within 5 minutes...

    Btw you should start using diamond references (since java 6 is just about to reach EOL) & use stringbuilder for your little print method &

    Code:
    ArrayList<T> newValues = new ArrayList<T>();
    to

    Code:
    List<T> newValues = new ArrayList<>();
    (and all others like it)

    2 decouple ur code from the implementation of the list.

    &

    wait... java compiler doesn't auto-compile to string-builder? ugh noobs
    Monads are just Monoids in the category of Endofunctors. What is the problem?
    Costate Comonad Coalgebra is equivalent of Java's member variable update technology for haskell. Problem?
    Reply With Quote  
     

  9. #8  
    Community Veteran


    Join Date
    Jan 2008
    Posts
    2,659
    Thanks given
    494
    Thanks received
    627
    Rep Power
    980
    Quote Originally Posted by Cups View Post
    wait... java compiler doesn't auto-compile to string-builder? ugh noobs
    Which you shouldn't rely on.

    It's trivial in this case though.
    ~iKilem
    Reply With Quote  
     

  10. #9  
    Banned

    Join Date
    Jan 2012
    Posts
    593
    Thanks given
    527
    Thanks received
    319
    Rep Power
    0
    Quote Originally Posted by Cups View Post
    wait... java compiler doesn't auto-compile to string-builder? ugh noobs
    In this situation it will create a new StringBuilder each loop, copying the characters from s each time, then it'll do the op.

    Whereas if you do it manually you will create a single StringBuilder for all ops.
    Reply With Quote  
     

  11. #10  
    Extreme Donator


    Join Date
    Jul 2009
    Age
    27
    Posts
    4,351
    Thanks given
    826
    Thanks received
    1,239
    Rep Power
    1781
    Quote Originally Posted by Bosslad View Post
    How could you not find a snippet within 5 minutes...

    Btw you should start using diamond references (since java 6 is just about to reach EOL) & use stringbuilder for your little print method &

    Code:
    ArrayList<T> newValues = new ArrayList<T>();
    to

    Code:
    List<T> newValues = new ArrayList<>();
    (and all others like it)

    2 decouple ur code from the implementation of the list.

    &

    I agree with you about the diamond "references," although they're actually called "diamond operators" or "diamond expressions." Not sure where you you got references from.

    Nice job Maxi.

    You can find my GitHub here, for what I'm currently working on.
    Reply With Quote  
     

Page 1 of 2 12 LastLast

Thread Information
Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)


User Tag List

Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •