I am attempting to implement "Heap's Algorithm" (wiki) in Java, which constructs all permutations of a given set. (I am aware that this isn't technically Heap's algorithm because of subtleties pointed out here, but that's not terribly important to me currently).
What I have: I'm starting from a piece of code that works and does what I want:
public static <T> List<T[]> Permutations(T a[]) {
LinkedList<T[]> list = new LinkedList<T[]>();
heapPermutation(a, a.length, a.length, list);
return list;
}
//Generating permutation using Heap Algorithm
public static <T> void heapPermutation(T a[], int size, int n, List<T[]> list)
{
// if size becomes 1 then adds the obtained
// permutation to the list
if (size == 1)
list.add(a.clone());
for (int i=0; i<size; i++)
{
heapPermutation(a, size-1, n, list);
// if size is odd, swap first and last
// element
if (size % 2 == 1)
{
T temp = a[0];
a[0] = a[size-1];
a[size-1] = temp;
}
// If size is even, swap ith and last
// element
else
{
T temp = a[i];
a[i] = a[size-1];
a[size-1] = temp;
}
}
}
public static void main(String[] args) {
Character[] chars = new Character[] {'a','b','c','d'};
List<Character[]> list = Permutations(chars);
for(Iterator<Character[]> i = list.iterator(); i.hasNext();) {
Character[] array = i.next();
for(int j = 0; j < array.length; j++) {
System.out.print(array[j] + " ");
}
System.out.println();
}
}
Again: This code works and outputs exactly what I want.
Good Output:
a b c d
b a c d
c a b d
a c b d
b c a d
c b a d
d b c a
b d c a
c d b a
d c b a
b c d a
c b d a
d a c b
a d c b
c d a b
d c a b
a c d b
c a d b
d a b c
a d b c
b d a c
d b a c
a b d c
b a d c
What I want: I would like to replicate the above code, but to replace all instances of arrays with Lists (or ArrayLists, LinkedLists, etc.).
What I've tried: Here is the modification I've attempted:
public static <T> List<List<T>> Permutations(List<T> a) {
List<List<T>> list = new ArrayList<List<T>>();
heapPermutation(a, a.size(), a.size(), list);
return list;
}
//Generating permutation using Heap Algorithm
public static <T> void heapPermutation(List<T> a, int size, int n, List<List<T>> list)
{
List<T> aTemp = new ArrayList<T>(a);
// if size becomes 1 then adds the obtained
// permutation to the list
if (size == 1) {
list.add(aTemp);
}
for (int i=0; i<size; i++)
{
heapPermutation(aTemp, size-1, n, list);
// if size is odd, swap first and last
// element
if (size % 2 == 1)
{
T temp = aTemp.get(0);
aTemp.set(0, a.get(size-1));
aTemp.set(size-1,temp);
}
// If size is even, swap ith and last
// element
else
{
T temp = aTemp.get(0);
aTemp.set(i, a.get(size-1));
aTemp.set(size-1, temp);
}
}
}
public static void main(String[] args) {
List<Character> list = new ArrayList<Character>();
list.add('a'); list.add('b'); list.add('c'); list.add('d');
System.out.println(Permutations(list));
}
However, unlike the first code block, this doesn't give what I want:
Bad Output:
[[a, b, c, d], [b, a, c, d], [c, b, a, d], [b, c, a, d], [c, b, c, d], [b, c, c, d], [d, b, c, a], [b, d, c, a], [c, b, d, a], [b, c, d, a], [c, b, c, a], [b, c, c, a], [d, d, c, d], [d, d, c, d], [c, d, d, d], [d, c, d, d], [c, d, c, d], [d, c, c, d], [d, d, d, d], [d, d, d, d], [d, d, d, d], [d, d, d, d], [d, d, d, d], [d, d, d, d]]
What is going on in the second code block that makes it not correct? I'm 100% sure it's due to my lack of understanding of some subtleties of Lists in Java, but I have no idea what's the culprit.
Before asking here, I tried the second block of code without adding List<T> aTemp = new ArrayList<T>(a);, and I've also tried tinkering with various parts of it to change instances of a to aTemp and vice versa. Nothing I've tried has worked.
In a comment below, user @GPI pointed out a typo in my even case. After correcting T temp = aTemp.get(0); to T temp = aTemp.get(i);, I have the following output:
[[a, b, c, d], [b, a, c, d], [c, b, a, d], [b, c, a, d], [c, b, c, d], [b, c, c, d], [d, b, c, a], [b, d, c, a], [c, b, d, a], [b, c, d, a], [c, b, c, a], [b, c, c, a], [d, d, c, b], [d, d, c, b], [c, d, d, b], [d, c, d, b], [c, d, c, b], [d, c, c, b], [d, d, d, c], [d, d, d, c], [d, d, d, c], [d, d, d, c], [d, d, d, c], [d, d, d, c]]
Note that this is also incorrect, because it contains a number of duplicates / lists which aren't actually permutations (such as [d, d, d, c]).
As already said, a first quick thing to fix is your typo : the even case should read T temp = aTemp.get(i);
The crux of the matter is that you did not grasp how / when the list/array is modified in place, versus when it is copied over as a result to accumulate.
Without even looking at what your method is doing, we can see that the array version manipulates the array in place, except when its size is one in which case it is copied to the list of results.
In other words, in the array version, it always is the same array that has its items swapped, however deep the recursion goes.
Only when we want to remember a certain permutation of the items do we take a copy of it, to make sure the permutation is frozen (a.clone()), meaning we can still swap items after that without risking any modification of the already accumulated permutations.
The list version, on the other hand, copies its input each time it starts. In other words, at each recursion stage a local copy of the original list is used to swap items. When the recursion unrolls, the current arrangment of items of this copy is lost.
So if you remove the cloning of the list where it is, only keeping it inside the if size == 1) case, you should be OK.
In the end, it's not that there is a subtelty in the list case versus the ararys, just that you moved some "cloning" logic without analyzing the impact.
With that in place, the output becomes :
[[a, b, c, d],
[b, a, c, d],
[c, a, b, d],
[a, c, b, d],
[b, c, a, d],
[c, b, a, d],
[d, b, c, a],
[b, d, c, a],
[c, d, b, a],
[d, c, b, a],
[b, c, d, a],
[c, b, d, a],
[d, a, c, b],
[a, d, c, b],
[c, d, a, b],
[d, c, a, b],
[a, c, d, b],
[c, a, d, b],
[d, a, b, c],
[a, d, b, c],
[b, d, a, c],
[d, b, a, c],
[a, b, d, c],
[b, a, d, c]]