Results 1 to 4 of 4

Thread: Permutations

  1. #1
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default Permutations

    This may not really be a programming question, more of a math question. What I'm trying to do, is take an arbitrary n, and generate permutations by taking n/2 numbers from the set {1,2,3,...,n}, with the condition, that there are no repetitions (example for n = 4: [1,2] and [2,1] would be considered repetitions).
    Now, I'm not looking for completed code, just a few ideas on how to set about this problem without using brute-force, since this is exactely what I want to avoid. I have been doing a lot of thinking about this, but still haven't come up with anything other than filtering.

  2. #2
    fceruti is offline Member
    Join Date
    Mar 2010
    Posts
    20
    Rep Power
    0

    Default

    It was real fun to do!

    have my code:

    Java Code:
    import java.util.ArrayList;
    
    public class Principal {
    	
    	
    	public static void main(String args[]){
    		
    		ArrayList<ArrayList<NumberSet>> sets = getSets(4,3);
    		
    		for(ArrayList<NumberSet> buffer : sets){
    			for(NumberSet num : buffer){
    				System.out.print("(");
    				for(Integer i : num.numbers){
    					System.out.print(" "+i+" ");
    				}
    				System.out.print(") ");
    			}
    		}
    		
    	}
    
    	public static ArrayList<ArrayList<NumberSet>> getSets(int n, int layer) {
    		if (layer == 1) {
    			ArrayList<ArrayList<NumberSet>> sets = new ArrayList<ArrayList<NumberSet>>(
    					n);
    			for (int i = 0; i < n; i++) {
    				NumberSet simpleSet = new NumberSet(i);
    				ArrayList<NumberSet> buffer = new ArrayList<NumberSet>();
    				buffer.add(simpleSet);
    				sets.add(buffer);
    			}
    			return sets;
    		} else {
    			ArrayList<ArrayList<NumberSet>> smallerSets = getSets(n, layer - 1);
    			ArrayList<ArrayList<NumberSet>> newSet = new ArrayList<ArrayList<NumberSet>>();
    			for(int i=0;i<n;i++){
    				ArrayList<NumberSet> newList  = new ArrayList<NumberSet>();
    				newSet.add(newList);
    			}
    			for (int i = 0; i < n; i++) {
    				ArrayList<NumberSet> buffer = smallerSets.get(i);
    				for (int j = 0; j < buffer.size(); j++) {
    					for (int k = j; k < n; k++) {
    						NumberSet newNumSet = new NumberSet(buffer.get(j).numbers, k);
    						newSet.get(k).add(newNumSet);
    					}
    				}
    			}
    			return newSet;
    		}
    
    	}
    
    }
    Java Code:
    import java.util.ArrayList;
    
    
    public class NumberSet {
    	
    	public ArrayList<Integer> numbers = new ArrayList<Integer>();
    	
    	public NumberSet(int i){
    		this.numbers.add(i);
    	}
    	public NumberSet(ArrayList<Integer> num,int newInt){
    		this.numbers.addAll(num);
    		this.numbers.add(newInt);
    	}
    	
    }
    The basic idea is that you should recursively make the sets. First you make all the posible 1 item set in a 1-dimensional space (layer). Then you add a layer and pick all the possible combinations without repetition of the given sets with the the numbers in the layer. Repeat this until you have completed all your layers (or group size).

    The trick is that you keep track of which is the biggest number in the set, and then you know you shouldnt combine it with anything that is lower than that.

    For example:

    say i call the algorithm with n = 4 and layer = 3

    you can see the hole problem as this (pick one number per row each time):

    0 1 2 3
    0 1 2 3
    0 1 2 3

    then starts the recursion which hits bottom on the final line

    numbers ----> 0--------1--------2--------3
    sets-created-> (0)------(1)------(2)------(3)

    this was the case layer == 1, so this result is given to the method call which has layer = 2, and you can see.


    numbers --> 0--------1--------2--------3
    sets-given-> (0)------(1)------(2)------(3)

    new-Sets--> (0,0)------(0,1)------(0,2)------(0,3)
    -------------------------(1,1)------(1,2)------(1,3)
    ------------------------------------(2,2)------(2,3)
    ------------------------------------------------(3,3)

    then you mix this set with the last layer


    srry if im not making myself clear, but feel free to ask =P
    Last edited by fceruti; 03-25-2010 at 02:31 PM.

  3. #3
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Wow, just wow! Thanks for the code, thanks even more for the explanation!

  4. #4
    fceruti is offline Member
    Join Date
    Mar 2010
    Posts
    20
    Rep Power
    0

Similar Threads

  1. Find all permutations of a number
    By matzahboy in forum New To Java
    Replies: 6
    Last Post: 12-02-2008, 04:59 AM

Posting Permissions

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