java 获取所有可能的变体(正和负)

Question

假设我有一行数字“1 2 3 4” 我需要获取所有可能的值

1+2+3+4
1+2+3-4
1+2-3+4
1+2-3-4
...
-1-2-3-4

尝试写一个递归 但它有点适用于“1 2”和“1 2 3”

它应该适用于 1 2 3 ... n

checkSum(0, list.size(), list);

private void checkSum(int start, int end, List<Long> list) {

    for (int i = start; i < end; i++){
        list.set(i, list.get(i) * (-1L));
        printLine(list);
        checkSum(i+2, end, list);
    }
}

private void printLine(List<Long> list) {
    for (int i = 0; i < list.size(); i++) {
        if (i > 0)
            if (list.get(i) > 0L)
                System.out.print("+");
        System.out.print(String.valueOf(list.get(i)));
    }
    System.out.println();
}

Answer 1

我有一种方法可以给你一些非常酷的想法。

我没有用递归，递归很好，但是使用时需要小心内存问题。如果您放置一个大列表，您可能会遇到堆栈溢出错误。

好的，我的解决方案利用了二进制系统。

所以，以二进制表示，从 0 数到 8

    0 0 0 0 
    0 0 0 1
    0 0 1 0
    0 0 1 1
    0 1 0 0
    0 1 0 1
    0 1 1 0
    0 1 1 1
    1 0 0 0

你收到了吗？您可以将这些视为负面信号。您可以应用掩码来获取该值。

你的掩码以 1 开头，如下所示:

0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0

通过这种方式您可以测试这些值。

所以，代码:

    public static void listPermutation(List<Long> l) {      
        for (int i = 0; i <= Math.pow(2,l.size()) - 1; i++) {
            List<Long> l2 = new ArrayList<Long>(l);
            applyMask(l2, i);
        }
    }

    public static void applyMask(List<Long> l, long counter) {

        long mask = 1L; 
        for (int i = l.size() - 1; counter >= mask; i--) {
            if ((mask & counter) > 0) // here testing if the bit is 1 or 0
                l.set(i, l.get(i) * -1);

            mask <<= 1;
        }
        printLine(l); // System.out.println(l);
    }

示例，

        List<Long> l = new ArrayList<Long>();
        l.add(1l);
        l.add(2l);
        l.add(3l);
        l.add(4l);

        listPermutation(l);

结果，

1+2+3+4
1+2+3-4
1+2-3+4
1+2-3-4
1-2+3+4
1-2+3-4
1-2-3+4
1-2-3-4
-1+2+3+4
-1+2+3-4
-1+2-3+4
-1+2-3-4
-1-2+3+4
-1-2+3-4
-1-2-3+4
-1-2-3-4

就速度而言，还不错:

        List<Long> l = new ArrayList<Long>();
        l.addAll(Arrays.asList(new Long[] { 1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 10L, 11L, 12L, 13L, 14L, 15L, 16L, 17L, 18L, 19L, 20L, 21L, 22L, 23L, 24L }));

        long initTime = System.currentTimeMillis();
        listPermutation(l);
        long finalTime = System.currentTimeMillis();

        System.out.println(finalTime - initTime + " ms");

        2833 ms

也许(可能)这不是最好的方法，但我相信这会改善你的想法:)