1. Senior Member Join Date
Feb 2010
Location
Ljubljana, Slovenia
Posts
470
Rep Power
11

## 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.  Reply With Quote

2. Member Join Date
Mar 2010
Posts
20
Rep Power
0

## 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>();
}
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>();
}
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);
}
}
}
return newSet;
}

}

}```
Java Code:
```import java.util.ArrayList;

public class NumberSet {

public ArrayList<Integer> numbers = new ArrayList<Integer>();

public NumberSet(int i){
}
public NumberSet(ArrayList<Integer> num,int 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.  Reply With Quote

3. Senior Member Join Date
Feb 2010
Location
Ljubljana, Slovenia
Posts
470
Rep Power
11

## Wow, just wow! Thanks for the code, thanks even more for the explanation!  Reply With Quote

4. Member Join Date
Mar 2010
Posts
20
Rep Power
0

## ur welcome :)  Reply With Quote

#### Posting Permissions

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