java - 创建一个由 int 数组组成的 int 数组，其中包含加起来等于给定数字的所有可能的总和

Question

我是 Java 的新手。我正在编写一个 Android 游戏，我需要生成一个 int 数组数组，其中包含加起来等于给定数字的所有可能总和(不包括包含数字 2 或大于 8 个数字的组合)。

例如: ganeratePatterns(5) 必须返回数组

 [patternNumber][summandNumber] = value

 [0][0] = 5

 [1][0] = 1
 [1][1] = 1
 [1][2] = 1
 [1][3] = 1
 [1][4] = 1

 [2][0] = 3
 [2][1] = 1
 [2][2] = 1

 [3][0] = 4
 [3][1] = 1

我已经尝试这样做了 Getting all possible sums that add up to a given number 但我很难做到这样http://introcs.cs.princeton.edu/java/23recursion/Partition.java.html

解决方案

int n = 10; 
int dimension = 0; 
//First we need to count number of posible combinations to create a 2dimensionarray
for(List<Integer> sumt : new SumIterator(n)) {
  if(!sumt.contains(2) && sumt.size() < 9) {
    dimension++;
  }
}

int[][] combinationPattern = new int[dimension][];
int foo = 0;
for(List<Integer> sum : new SumIterator(n)) {
  if(!sum.contains(2) && sum.size() < 9) {
      System.out.println(sum);
      combinationPattern[foo] = toIntArray(sum);
      foo++;
  }
}

它的工作不是 100% 正确，而且非常漂亮，但对于我的游戏来说已经足够了

我在这里使用了 SumIterator 类 SumIterator.class 我必须将此代码 for(int j = n-1; j > n/2; j--) { 更改为此 for(int j = n-1; j >= n/2; j--) { 因为旧版本不返回所有组合(比如 [5,5] 表示 10)

我使用了 toIntArray 函数。我在 StackOverflow 上创建了 hare，但忘记了链接，所以这里是来源:

public static int[] toIntArray(final Collection<Integer> data){
    int[] result;
    // null result for null input
    if(data == null){
        result = null;
    // empty array for empty collection
    } else if(data.isEmpty()){
        result = new int[0];
    } else{
        final Collection<Integer> effective;
        // if data contains null make defensive copy
        // and remove null values
        if(data.contains(null)){
            effective = new ArrayList<Integer>(data);
            while(effective.remove(null)){}
        // otherwise use original collection
        }else{
            effective = data;
        }
        result = new int[effective.size()];
        int offset = 0;
        // store values
        for(final Integer i : effective){
            result[offset++] = i.intValue();
        }
    }
    return result;
}

Answer 1

这不是最漂亮的代码，但它可以按照您的意愿行事，修改您引用的代码。它也相当快。通过远离递归(使用堆栈)并完全避免字符串到整数的转换，可以使它更快。我可能会回来编辑这些更改。在我相当过时的笔记本电脑上运行，它在 5 秒内打印了 50 的分区(全部 204226)。

当 partition(N) 退出此代码时，partitions 将保存 N 的分区。

1. 首先，它以空格分隔的格式(例如:"1 1 1")构建总和的字符串表示形式的 ArrayList。

2. 然后创建一个二维整数数组，可以保存所有结果。

3. 它将 ArrayList 中的每个字符串拆分为一个字符串数组，每个字符串只包含一个数字。
4. 对于每个字符串，它通过将每个数字解析为一个数组来创建一个整数数组。
5. 然后将此 int 数组添加到二维 int 数组。

如果您有任何问题，请告诉我!

    import java.util.ArrayList;
    public class Partition
    {
        static ArrayList<String> list = new ArrayList<String>();
        static int[][] partitions;

        public static void partition(int n)
        {
            partition(n, n, "");
            partitions = new int[list.size()][0];
            for (int i = 0; i < list.size(); i++)
            {
                String s = list.get(i);
                String[] stringAsArray = s.trim().split(" ");
                int[] intArray = new int[stringAsArray.length];
                for (int j = 0; j < stringAsArray.length; j++)
                {
                    intArray[j] = Integer.parseInt(stringAsArray[j]);
                }
                partitions[i] = intArray;
            }
        }

        public static void partition(int n, int max, String prefix)
        {
            if(prefix.trim().split(" ").length > 8 || (prefix + " ").contains(" 2 "))
            {
                return;
            }
            if (n == 0)
            {
                list.add(prefix);
                return;
            }

            for (int i = Math.min(max, n); i >= 1; i--)
            {
                partition(n - i, i, prefix + " " + i);
            }
        }

        public static void main(String[] args)
        {
            int N = 50;
            partition(N);

            /**
             * Demonstrates that the above code works as intended.
             */
            for (int i = 0; i < partitions.length; i++)
            {
                int[] currentArray = partitions[i];
                for (int j = 0; j < currentArray.length; j++)
                {
                    System.out.print(currentArray[j] + " ");
                }
                System.out.println();
            }
        }
    }