Michael.J.Keating
BAN USERpublic static List<ArrayList<String>> getPermutations(
List<ArrayList<String>> lists) {
List<ArrayList<String>> currentPermutations =
new ArrayList<ArrayList<String>>();
// generate new permutations one list at a time
for (ArrayList<String> list : lists) {
currentPermutations =
generatePermutations(currentPermutations, list);
}
return currentPermutations;
}
private static List<ArrayList<String>> generatePermutations(
List<ArrayList<String>> currentPermutations,
ArrayList<String> list) {
// we'll be creating a whole new set of permutations from
// currentPermutations and the 'list' of new items
List<ArrayList<String>> newPermutations =
new ArrayList<ArrayList<String>>();
for (String item : list) {
if (currentPermutations.isEmpty()) {
// first generated list - just add the single items
ArrayList<String> newPermutation = new ArrayList<String>();
newPermutation.add(item);
newPermutations.add(newPermutation);
}
else {
// create a new permutation list based
// on the old list plus our new item
for (ArrayList<String> curList : currentPermutations) {
if (!curList.contains(item)) {
ArrayList<String> newPermutation =
new ArrayList<String>(curList);
newPermutation.add(item);
newPermutations.add(newPermutation);
}
}
}
}
return newPermutations;
}
public static void getPermutationsTest() {
List<ArrayList<String>> permutations =
new ArrayList<ArrayList<String>>();
ArrayList<String> list = new ArrayList<String>();
list.add("a1");
list.add("a2");
permutations.add(list);
list = new ArrayList<String>();
list.add("b1");
list.add("b2");
list.add("b3");
permutations.add(list);
list = new ArrayList<String>();
list.add("c1");
list.add("c2");
permutations.add(list);
permutations = Util.getPermutations(permutations);
for (ArrayList<String> permutation : permutations) {
System.out.println(permutation);
}
}
// Output:
// [a1, b1, c1]
// [a2, b1, c1]
// [a1, b2, c1]
// [a2, b2, c1]
// [a1, b3, c1]
// [a2, b3, c1]
// [a1, b1, c2]
// [a2, b1, c2]
// [a1, b2, c2]
// [a2, b2, c2]
// [a1, b3, c2]
// [a2, b3, c2]
Nice job, Music. Looks a lot like my solution above :)
- Michael.J.Keating October 15, 2013Just to clarity: Is this to determine all PAIRS that sum to K as in the output example? Or all combinations (as in the question):
If input array is {1,2,3,4,5,6} and K is 7
then O/P should be
1 6
3 4
2 5
1 2 4
Why not just allow each node to carry the 'current min value' in addition to its own value. This way the head node (or the top of the stack) always knows the min value. See my solution above.
- Michael.J.Keating October 14, 2013public class MinStack {
private Node _head;
public void push(int value) {
Node node = new Node();
node.value = value;
if (_head == null) {
node.minValue = node.value;
_head = node;
}
else {
node.minValue =
node.value < _head.minValue ? node.value : _head.minValue;
node.next = _head;
_head = node;
}
}
public int pop() {
if (_head == null)
return -1;
Node node = _head;
_head = node.next;
return node.value;
}
public int min() {
if (_head == null)
return -1;
return _head.minValue;
}
private class Node {
int value;
int minValue;
Node next;
}
}
My thoughts are to provide access methods in the base class that are protected. This will provide access to sub-classes without exposing them to the public.
- Michael.J.Keating October 18, 2013