Zhikai Wang Homepage

Heteroclinic.net logo

www.heteroclinic.net

	Fundamental Combinatorics Programming I 20140915 Loop permutation. package net.heteroclinic.experiment.lambdatest; /** * * @author zhikai * Given third party license acknowledged and this header kept or quoted, you can utilize this program at will. */ public class LoopPerm { public static void perm(int[] a, int segmentLength) { if (segmentLength <= 1) { for (int i : a) System.out.print(i + " "); System.out.println(); return; } for (int i = segmentLength - 1; i >= 0; i--) { int tmp = a[segmentLength - 1]; a[segmentLength - 1] = a[i]; a[i] = tmp; perm(a, segmentLength - 1); tmp = a[segmentLength - 1]; a[segmentLength - 1] = a[i]; a[i] = tmp; } } public static void main(String[] args) { int[] a = { 1 }; perm(a, a.length); a = new int[] { 1, 2 }; perm(a, a.length); a = new int[] { 1, 2 ,3}; perm(a, a.length); } }
	Fundamental Combinatorics Programming II 20140915 Ccompute k-combinations of a set. package net.heteroclinic.experiment.lambdatest; import java.util.ArrayList; import java.util.List; /** * @author Zhikai Wang/www.heteroclinic.net * This class is an example/exercise to provide a code base to compute k-combinations of a set. * Given third party license acknowledged and this header kept or quoted, you can utilize this program at will. * Juggling elements among: * [spared][selected][remaining] */ public class KCombinationByChooseSpare { // Print a List public static void printList (List<Integer> l) { for (int i:l) System.out.print(i+ " "); System.out.println(); } // Moving the elements frequently at random positions proves in-line array impractical. public static void choose ( List<Integer> spared, List<Integer> choices, List<Integer> remaining, int K) { // END conditions for the recursion // 1. The choices suffice // 2. The remaining choices do not allow more sparing // May check always. if ( choices.size() >= K ) { // Print choices printList (choices); return; } else if ( remaining.size() <= K - choices.size()) { // Print remaining + choices List<Integer> pl = new ArrayList<Integer>(); pl.addAll(choices); pl.addAll(remaining); printList (pl); return; } // For the first element of the remaining if ( remaining.size() <= 0) return; int firstOfRemaining = remaining.get(0); // Choose it, call choose to pick one more choices.add(firstOfRemaining); remaining.remove(new Integer(firstOfRemaining)); List<Integer> ns = new ArrayList<Integer>(); ns.addAll(spared); List<Integer> nc = new ArrayList<Integer>(); nc.addAll(choices); List<Integer> nr = new ArrayList<Integer>(); nr.addAll(remaining); choose ( ns,nc, nr, K); // Spare it, call choose to pick one more spared.add(firstOfRemaining); choices.remove(new Integer(firstOfRemaining)); ns = new ArrayList<Integer>(); ns.addAll(spared); nc = new ArrayList<Integer>(); nc.addAll(choices); nr = new ArrayList<Integer>(); nr.addAll(remaining); choose ( ns,nc, nr, K); } public static void main(String[] args) { List<Integer> a = new ArrayList<Integer>(); for (int i = 1; i<=5 ; i++) { a.add(i); } choose (new ArrayList<Integer>(),new ArrayList<Integer>(), a,2); } }
	Fundamental Combinatorics Programming III 20140915 Ccompute all k-combinations of a set. package net.heteroclinic.experiment.lambdatest; import java.util.ArrayList; import java.util.List; /** * @author Zhikai Wang/www.heteroclinic.net * This class is an example/exercise to provide a code base to compute all k-combinations of a set. * Given third party license acknowledged and this header kept or quoted, you can utilize this program at will. */ public class ComputeAllKCombinationOfASet { // Print a List public static void printList (List<Integer> l) { for (int i:l) System.out.print(i+ " "); System.out.println(); } // Moving the elements frequently at random positions proves in-line array impractical. public static void choose ( List<Integer> spared, List<Integer> choices, List<Integer> remaining, int K) { // END conditions for the recursion // 1. The choices suffice // 2. The remaining choices do not allow more sparing // May check always. if ( choices.size() >= K ) { // Print choices printList (choices); return; } else if ( remaining.size() <= K - choices.size()) { // Print remaining + choices List<Integer> pl = new ArrayList<Integer>(); pl.addAll(choices); pl.addAll(remaining); printList (pl); return; } // For the first element of the remaining if ( remaining.size() <= 0) return; int firstOfRemaining = remaining.get(0); // Choose it, call choose to pick one more choices.add(firstOfRemaining); remaining.remove(new Integer(firstOfRemaining)); List<Integer> ns = new ArrayList<Integer>(); ns.addAll(spared); List<Integer> nc = new ArrayList<Integer>(); nc.addAll(choices); List<Integer> nr = new ArrayList<Integer>(); nr.addAll(remaining); choose ( ns,nc, nr, K); // Spare it, call choose to pick one more spared.add(firstOfRemaining); choices.remove(new Integer(firstOfRemaining)); ns = new ArrayList<Integer>(); ns.addAll(spared); nc = new ArrayList<Integer>(); nc.addAll(choices); nr = new ArrayList<Integer>(); nr.addAll(remaining); choose ( ns,nc, nr, K); } public static void computeAllKCombinationOfASet (List<Integer> l ) { for (int i = 0; i <=l.size(); i++) { List<Integer> b = new ArrayList<Integer>(); b.addAll(l); choose (new ArrayList<Integer>(),new ArrayList<Integer>(), b,i); } } public static void main(String[] args) { List<Integer> a = new ArrayList<Integer>(); for (int i = 1; i<=3 ; i++) { a.add(i); } computeAllKCombinationOfASet (a ); } }
	Fundamental Combinatorics Programming IV 20140915 Compute k-permutation of a set by permute k-combination. package net.heteroclinic.experiment.lambdatest; import java.util.ArrayList; import java.util.List; /** * @author Zhikai Wang/www.heteroclinic.net * This class is an example/exercise to provide a code base to compute k-permutation of a set by permute k-combination. * Why we do this, it looks like subset operation destroy the permutation group. So guess the swap subgroup and one element is not reflective. * Given third party license acknowledged and this header kept or quoted, you can utilize this program at will. */ public class ComuteKPermutation { public static void perm(int[] a, int segmentLength) { if (segmentLength <= 1) { for (int i : a) System.out.print(i + " "); System.out.println(); return; } for (int i = segmentLength - 1; i >= 0; i--) { int tmp = a[segmentLength - 1]; a[segmentLength - 1] = a[i]; a[i] = tmp; perm(a, segmentLength - 1); tmp = a[segmentLength - 1]; a[segmentLength - 1] = a[i]; a[i] = tmp; } } // Moving the elements frequently at random positions proves in-line array impractical. public static void chooseForPermutation ( List<Integer> spared, List<Integer> choices, List<Integer> remaining, int K) { // END conditions for the recursion // 1. The choices suffice // 2. The remaining choices do not allow more sparing // May check always. if ( choices.size() >= K ) { // Permute choices int [] array = new int[choices.size()]; for (int i = 0; i< array.length; i++) { array[i] = choices.get(i); } perm(array, array.length); return; } else if ( remaining.size() <= K - choices.size()) { // Permute remaining + choices List<Integer> pl = new ArrayList<Integer>(); pl.addAll(choices); pl.addAll(remaining); // Permute pl int [] array = new int[pl.size()]; for (int i = 0; i< array.length; i++) { array[i] = pl.get(i); } perm(array, array.length); return; } // For the first element of the remaining if ( remaining.size() <= 0) return; int firstOfRemaining = remaining.get(0); // Choose it, call choose to pick one more choices.add(firstOfRemaining); remaining.remove(new Integer(firstOfRemaining)); List<Integer> ns = new ArrayList<Integer>(); ns.addAll(spared); List<Integer> nc = new ArrayList<Integer>(); nc.addAll(choices); List<Integer> nr = new ArrayList<Integer>(); nr.addAll(remaining); chooseForPermutation ( ns,nc, nr, K); // Spare it, call choose to pick one more spared.add(firstOfRemaining); choices.remove(new Integer(firstOfRemaining)); ns = new ArrayList<Integer>(); ns.addAll(spared); nc = new ArrayList<Integer>(); nc.addAll(choices); nr = new ArrayList<Integer>(); nr.addAll(remaining); chooseForPermutation ( ns,nc, nr, K); } public static void main(String[] args) { List<Integer> a = new ArrayList<Integer>(); for (int i = 1; i<=5 ; i++) { a.add(i); } chooseForPermutation (new ArrayList<Integer>(),new ArrayList<Integer>(), a,3); } }