Results 1 to 4 of 4
Thread: Permutations
 03252010, 12:24 PM #1Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 8
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 bruteforce, 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.
 03252010, 02:25 PM #2Member
 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>(); 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 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 > 0123
setscreated> (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 > 0123
setsgiven> (0)(1)(2)(3)
newSets> (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 =PLast edited by fceruti; 03252010 at 02:31 PM.
 03252010, 04:54 PM #3Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 8
Wow, just wow! Thanks for the code, thanks even more for the explanation!
 03252010, 09:58 PM #4Member
 Join Date
 Mar 2010
 Posts
 20
 Rep Power
 0
Similar Threads

Find all permutations of a number
By matzahboy in forum New To JavaReplies: 6Last Post: 12022008, 04:59 AM
Bookmarks