基于java.util.Stack的笛卡尔积求解算法输出异常问题排查

问题核心 #

你的代码输出错误的根本原因是数组引用复用：Java中数组属于引用类型，String[] tupel2 = tupel1;并没有创建新数组，只是让新变量指向原数组的内存地址。当你循环修改tupel2[l]并压入栈时，栈中所有元素实际都是同一个数组的引用，最终所有结果都会被最后一次修改操作覆盖。

比如处理第一个集合（l=0）时，拆分"k1,k2,k3"后，三次修改并压入栈2的操作，实际都是在修改同一个数组，最终栈2中的三个元素全是[k3, m1,m2, s1]，后续处理自然会出错。

修复方案 #

每次生成新元组时，必须创建原数组的副本，修改副本的对应位置后再压入栈。可以通过Arrays.copyOf()或手动遍历复制数组内容来实现。

修复后的完整代码 #

import java.util.ArrayList;
import java.util.Stack;
import java.util.Arrays; // 新增导入

public class CartesianProduct {

    int k;
    ArrayList<String[]> product = new ArrayList<String[]>();

    public CartesianProduct(ArrayList<String> input) {

        k = input.size();

        Stack<String[]> stack1 = new Stack<String[]>();
        Stack<String[]> stack2 = new Stack<String[]>();

        String[] tupel = new String[k];
        for (int l = 0; l < k; ++l) {
            tupel[l] = input.get(l);
        }
        stack1.push(tupel);
        System.out.println("push on 1: "+tupel[0]+" "+tupel[1]+" "+tupel[2]);

        for (int l = 0; l < k; ++l) {
        
            System.out.println();
            if (l % 2 == 0) {
                while (!stack1.empty()) {
                    String[] tupel1 = stack1.pop();
                    System.out.println("pop from 1: "+tupel1[0]+" "+tupel1[1]+" "+tupel1[2]);       

                    String[] indices = tupel1[l].split(",");
                    
                    for (String index : indices) {
                        // 修复：创建原数组的副本
                        String[] tupel2 = Arrays.copyOf(tupel1, tupel1.length);
                        tupel2[l] = index;
                        stack2.push(tupel2);
                        System.out.println("push on 2: "+tupel2[0]+" "+tupel2[1]+" "+tupel2[2]);
                    }
                }
            } else {
                while (!stack2.empty()) {
                    String[] tupel1 = stack2.pop();
                    System.out.println("pop from 2: "+tupel1[0]+" "+tupel1[1]+" "+tupel1[2]);       

                    String[] indices = tupel1[l].split(",");
                    
                    for (String index : indices) {
                        // 修复：创建原数组的副本
                        String[] tupel2 = Arrays.copyOf(tupel1, tupel1.length);
                        tupel2[l] = index;
                        stack1.push(tupel2);
                        System.out.println("push on 1: "+tupel2[0]+" "+tupel2[1]+" "+tupel2[2]);        
                    }
                }
            }
        }

        if (k % 2 == 0) {
            while (!stack1.isEmpty()) {
                product.add(stack1.pop());
            }
        } else {
            while (!stack2.isEmpty()) {
                product.add(stack2.pop());
            }
        }

    }

    public int getK() {
        return k;
    }

    public ArrayList<String[]> getProduct() {
        return product;
    }

    public static void main(String args[]) {

        ArrayList<String> set = new ArrayList<String>();

        set.add("k1,k2,k3");
        set.add("m1,m2");
        set.add("s1");

        CartesianProduct prod = new CartesianProduct(set);
        System.out.println("k: " + prod.getK());
        for (String[] tupel : prod.getProduct()) {
            System.out.println(tupel[0] + " " + tupel[1] + " " + tupel[2]);
        }
    }
}

修复说明 #

1. 新增java.util.Arrays导入，用于数组复制
2. 删除了原代码中String[] tupel2 = tupel1;的引用赋值，替换为Arrays.copyOf(tupel1, tupel1.length)创建新数组副本
3. 每次修改新数组的对应位置后再压入栈，确保栈中每个元素都是独立的数组对象

修复后，测试用例将输出正确的6种笛卡尔积组合：

k3 m2 s1
k3 m1 s1
k2 m2 s1
k2 m1 s1
k1 m2 s1
k1 m1 s1

内容的提问来源于stack exchange，提问作者Asterix37