Permutations

[m00nchile]

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.

[fceruti]

It was real fun to do!

have my 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;
		}

	}

}

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

[m00nchile]

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

[fceruti]

ur welcome :)