cornholio
BAN USERpackage com;
import java.util.ArrayList;
import java.util.List;
public class Permutations {
public <T> List<List<T>> generate(List<T> listOfItems) {
List<List<T>> result = new ArrayList<List<T>>();
if (listOfItems == null) {
return null;
}
if (listOfItems.size() == 0) {
return result;
}
if (listOfItems.size() == 1) {
result.add(listOfItems);
return result;
}
// take out one item from the list
T pulledOutItem = listOfItems.get(0);
// get the sub list without that "pulled out item"
List<T> subList = listOfItems.subList(1, listOfItems.size());
// this method will return the permutations for the remaining items
List<List<T>> generatedListOfListOfItems = generate(subList);
// for each permutation of items
for (List<T> items : generatedListOfListOfItems) {
// clone that items permutation and put the "pulled out item" at
// each index location in the cloned permutation
for (int i = 0; i <= items.size(); i++) {
List<T> clonedItems = clone(items);
clonedItems.add(i, pulledOutItem);
result.add(clonedItems);
}
}
return result;
}
public static void main(String... args) {
List<Integer> listOfItems = new ArrayList<Integer>();
listOfItems.add(1);
listOfItems.add(2);
listOfItems.add(3);
listOfItems.add(4);
List<List<Integer>> listOfListOfItems = new Permutations()
.generate(listOfItems);
for (List<Integer> items : listOfListOfItems) {
for (Integer item : items) {
System.out.print(item + ",");
}
System.out.println("--");
}
}
public <T> List<T> clone(List<T> list) {
List<T> newList = new ArrayList<T>();
newList.addAll(list);
return newList;
}
}
That's the solution I thought of too.. As an optimization for the nested loop i though one could reduce the complexity from O(n squared) to O(nlogn) by searching for the closest number in the list using divide and conquer. Instead of binary search I'd call it the binary find closest value ;)
For e.g.: If you're inside a loop and the current value is 7 and the second list is like this: 1 3 6 8 9. Then using a modified binary search you can find that 6 or 8 is the closest value and accordingly the smallest distance there is 1.
Here's another one in Java. Very similar to what other's have said:
pseudo code:
Actual Code:
Output:
- cornholio August 07, 2014