java - 在 Java 中将可变长度的整数数组倒数到零

Question

我有一个数组，其中包含 3 个文件中的总行数。示例:[3,4,5]。我想生成一个数字序列，以有条不紊的方式将该数组计数为零，为我提供三个文件中的每行组合。此示例使用 3 个文件/长度为 3 的数组，但该算法应该能够处理任意长度的数组。

对于上面的例子，解决方案如下:

[3,4,5]  (line 3 from file 1, line 4 from file 2, line 5 from file 3)  
[3,4,4]  
[3,4,3]  
[3,4,2]  
[3,4,1]  
[3,4,0]  
[3,3,5]  
[3,3,4]  
[3,3,3]  
[3,3,2]  

等等……

我第一次尝试为此递归递减数组中的一个位置，并在该位置达到零时递减它之前的位置。但是，我无法让递减比最后两个位置更远。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

    public class FilePositionGenerator {

        public static void main(String[] args) {
            int[] starterArray = {2, 2, 2};
            int[] counters = starterArray.clone();
            List<Integer> results = new ArrayList<Integer>();

            FilePositionGenerator f = new FilePositionGenerator();
            f.generateFilePositions(starterArray, counters, (starterArray.length - 1), results);
        }//end main

        void generateFilePositions(int[] originalArray, int[] modifiedArray, int counterPosition, List<Integer> results) {

            if (modifiedArray[counterPosition] == 0 && counterPosition > 0) {
                modifiedArray[counterPosition] = originalArray[counterPosition];
                counterPosition = counterPosition - 1;
            } else {
                modifiedArray[counterPosition] = modifiedArray[counterPosition] - 1;
                System.out.println(Arrays.toString(modifiedArray));
                generateFilePositions(originalArray, modifiedArray, counterPosition, results);
            }
        }
    }  

我知道要处理可变长度数组，算法必须是递归的，但我无法完全考虑。所以我决定尝试一种不同的方法。

我第二次尝试生成算法使用双指针方法，该方法将指针保持在当前倒计时位置[最右边的位置]，以及指向下一个非最右边位置(pivotPointer)的指针，该指针将在最右边的位置递减位置达到零。像这样:

import java.util.Arrays;

class DualPointer {
    public static void main(String[] args) {
        int[] counters = {2, 2, 2}; // initialize the problem set
        int[] original = {2, 2, 2}; // clone a copy to reset the problem array
        int[] stopConditionArray = {0, 0, 0};   // initialize an object to show what the stopCondition should be
        int pivotLocation = counters.length - 1;    // pointer that starts at the right, and moves left
        int counterLocation = counters.length - 1;  // pointer that always points to the rightmost position
        boolean stopCondition = false;

        System.out.println(Arrays.toString(counters));
        while (stopCondition == false) {

            if (pivotLocation >= 0 && counterLocation >= 0 && counters[counterLocation] > 0) {
                // decrement the rightmost position
                counters[counterLocation] = counters[counterLocation] - 1;
                System.out.println(Arrays.toString(counters));
            } else if (pivotLocation >= 0 && counters[counterLocation] <= 0) {
                // the rightmost position has reached zero, so check the pivotPointer
                // and decrement if necessary, or move pointer to the left
                if (counters[pivotLocation] == 0) {
                    counters[pivotLocation] = original[pivotLocation];
                    pivotLocation--;
                }
                counters[pivotLocation] = counters[pivotLocation] - 1;
                counters[counterLocation] = original[counterLocation]; // reset the rightmost position
                System.out.println(Arrays.toString(counters));
            } else if (Arrays.equals(counters, stopConditionArray)) {
                // check if we have reached the solution
                stopCondition = true;
            } else {
                // emergency breakout of infinite loop
                stopCondition = true;
            }

        }
    }
}

运行后，你可以看到两个明显的问题:

[2, 2, 2]  
[2, 2, 1]  
[2, 2, 0]  
[2, 1, 2]  
[2, 1, 1]  
[2, 1, 0]  
[2, 0, 2]  
[2, 0, 1]  
[2, 0, 0]  
[1, 2, 2]  
[1, 2, 1]  
[1, 2, 0]  
[0, 2, 2]  
[0, 2, 1]  
[0, 2, 0]  

第一，当 pivotPointer 和 currentCountdown 相隔不止一个数组单元格时，pivotPointer 不会正确递减。其次，在行 counters[pivotLocation] = counters[pivotLocation] - 1; 处有一个 arrayIndexOutOfBounds 如果固定，使算法无法正常运行。

如有任何帮助，我们将不胜感激。

Answer 1

我会建议一种不同的方法。

递归的想法是减少每次递归调用中问题的大小，直到您达到一个微不足道的情况，在这种情况下您不必进行另一个递归调用。

当你第一次为n个元素的数组调用递归方法时，你可以循环迭代最后一个索引(n-1)的值范围，进行递归调用以生成数组的所有组合前 n-1 个元素，并组合输出。

这是一些部分 Java/部分伪代码:

第一次调用:

List<int[]> output = generateCombinations(inputArray,inputArray.length);

递归方法List<int[]> generateCombinations(int[] array, int length) :

List<int[]> output = new ArrayList<int[]>();
if length == 0 
    // the end of the recursion
    for (int i = array[length]; i>=0; i--)
        output.add (i)
else
    // the recursive step
    List<int[]> partialOutput = generateCombinations(array, length - 1)
    for (int i = array[length]; i>=0; i--)
        for (int[] arr : partialOutput)
            output.add(arr + i)
return output

递归方法返回一个List<int[]> .这意味着在“output.add (i)”中，您应该创建一个具有单个元素的 int 数组并将其添加到列表中，而在 output.add(arr + i) 中您将创建一个 arr.length+1 元素的数组，并将 arr 的元素复制到其中，然后是 i。