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

Question

我有一个数组，其中包含 3 个文件中的总行数。示例：[3,4,5]。我想生成一个数字序列，以有条不紊的方式将该数组计数为零，为我提供三个文件中的每行组合。此示例使用 3 files/length-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, 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

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

Answer 2

递归的有趣之处在于你可以让它完全按照你的意愿去做。在这种情况下，对于计数数组索引 i 处的每个数字，我们希望将其与索引 i + 1 处的每个数字组合，直到到达数组末尾。诀窍是不要 return 索引 i 一旦你运行通过它的所有选项。

JavaScript代码：

var arr = [3,4,5];
var n = arr.length;

function f(cs,i){
  // base case
  if (i == n){
    console.log(cs.join(','));
    return;
  }

  // otherwise
  while (cs[i] >= 0){
    // copy counts
    _cs = cs.slice();

    // recurse
    f(_cs,i + 1);

    // change number at index i
    cs[i]--;
  }
}

f(arr,0);

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

Counting down a variable length array of integers to Zero in Java

java

arrays

algorithm

recursion

counter