是什么 Java 列表相关的微妙之处导致我的堆算法实现失败?
What Java List-related subtlety is causing my Heap's Algorithm implementation to fail?
我正在尝试实施 "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 ,但目前这对我来说不是很重要)。
我所拥有的:我从一段有效的代码开始:
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();
}
}
再说一次:此代码有效并输出我想要的内容。
输出良好:
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
我想要的:我想复制上面的代码,但是用List
s(或ArrayList
s替换数组的所有实例, LinkedList
s 等).
我尝试过的:这是我尝试过的修改:
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));
}
然而,与第一个代码块不同,这并没有给出我想要的:
错误输出:
[[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]]
第二个代码块中发生了什么导致它不正确?我 100% 确定这是由于我对 Java 中 List
的一些细微之处缺乏理解,但我不知道是什么原因造成的。
在这里问之前,我尝试了第二个代码块 没有 添加 List<T> aTemp = new ArrayList<T>(a);
,我还尝试修改它的各个部分以更改实例a
到 aTemp
,反之亦然。我试过的都没有用。
编辑 1
在下面的评论中,用户@GPI 指出了我的偶数案例中的错字。将 T temp = aTemp.get(0);
更正为 T temp = aTemp.get(i);
后,我得到以下输出:
[[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]]
请注意,这也是不正确的,因为它包含许多实际上不是排列的重复项/列表(例如 [d, d, d, c]
)。
首先,打字错误
如前所述,首先要解决的是您的错字:偶数大小写应为 T temp = aTemp.get(i);
二、克隆
问题的症结在于你没有掌握list/array是如何/何时修改到位,以及什么时候复制过来累积起来的。
即使不看你的方法在做什么,我们也可以看到数组版本就地操作数组,除非它的大小是 1,在这种情况下它被复制到结果列表。
换句话说,在数组版本中,无论递归进行多深,它始终是交换其项目的同一个数组。
只有当我们想记住项目的某个排列时,我们才会复制它,以确保排列被冻结 (a.clone()
),这意味着我们仍然可以在之后交换项目,而不会冒任何修改已经存在的风险累积排列。
另一方面,列表版本会在每次启动时复制其输入。换句话说,在每个递归阶段,原始列表的本地副本用于交换项目。当递归展开时,此副本的当前项目排列将丢失。
因此,如果您删除列表的克隆,只将其保留在 if size == 1)
案例中,您应该没问题。
说到底,list case 和 arary 并没有什么微妙之处,只是你移动了一些“克隆”逻辑而没有分析影响。
有了这个,输出就变成了:
[[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]]
我正在尝试实施 "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
我所拥有的:我从一段有效的代码开始:
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();
}
}
再说一次:此代码有效并输出我想要的内容。
输出良好:
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
我想要的:我想复制上面的代码,但是用List
s(或ArrayList
s替换数组的所有实例, LinkedList
s 等).
我尝试过的:这是我尝试过的修改:
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));
}
然而,与第一个代码块不同,这并没有给出我想要的:
错误输出:
[[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]]
第二个代码块中发生了什么导致它不正确?我 100% 确定这是由于我对 Java 中 List
的一些细微之处缺乏理解,但我不知道是什么原因造成的。
在这里问之前,我尝试了第二个代码块 没有 添加 List<T> aTemp = new ArrayList<T>(a);
,我还尝试修改它的各个部分以更改实例a
到 aTemp
,反之亦然。我试过的都没有用。
编辑 1
在下面的评论中,用户@GPI 指出了我的偶数案例中的错字。将 T temp = aTemp.get(0);
更正为 T temp = aTemp.get(i);
后,我得到以下输出:
[[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]]
请注意,这也是不正确的,因为它包含许多实际上不是排列的重复项/列表(例如 [d, d, d, c]
)。
首先,打字错误
如前所述,首先要解决的是您的错字:偶数大小写应为 T temp = aTemp.get(i);
二、克隆
问题的症结在于你没有掌握list/array是如何/何时修改到位,以及什么时候复制过来累积起来的。
即使不看你的方法在做什么,我们也可以看到数组版本就地操作数组,除非它的大小是 1,在这种情况下它被复制到结果列表。
换句话说,在数组版本中,无论递归进行多深,它始终是交换其项目的同一个数组。
只有当我们想记住项目的某个排列时,我们才会复制它,以确保排列被冻结 (a.clone()
),这意味着我们仍然可以在之后交换项目,而不会冒任何修改已经存在的风险累积排列。
另一方面,列表版本会在每次启动时复制其输入。换句话说,在每个递归阶段,原始列表的本地副本用于交换项目。当递归展开时,此副本的当前项目排列将丢失。
因此,如果您删除列表的克隆,只将其保留在 if size == 1)
案例中,您应该没问题。
说到底,list case 和 arary 并没有什么微妙之处,只是你移动了一些“克隆”逻辑而没有分析影响。
有了这个,输出就变成了:
[[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]]