Создайте массив int из массивов int, который содержит все возможные суммы, которые складываются до заданного числа - PullRequest
Новая
       28

Создайте массив int из массивов int, который содержит все возможные суммы, которые складываются до заданного числа

1 голос
/ 25 ноября 2011

Я полностью новичок в 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

Я уже пытаюсь сделать это, как там Получение всех возможных сумм, которые складываются в данное число , но мне очень трудносделай так 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, но забыл ссылку, поэтому вот его источник: 

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;
}

1 Ответ

1 голос
/ 26 ноября 2011

Это не самый красивый код, но он делает то, что вам нужно, изменив код, на который вы ссылаетесь. Это также довольно быстро. Это можно сделать быстрее, избегая рекурсии (используя стек) и полностью избегая преобразования строк в целые числа. Я могу вернуться и отредактировать эти изменения. Работая на моем довольно устаревшем ноутбуке, он напечатал разделы 50 (все 204226 из них) менее чем за 5 секунд.

Когда partition(N) выходит из этого кода, partitions будет содержать разделы N.

  1. Сначала создается ArrayList строковых представлений сумм в формате с разделителями пробелами (пример: " 1 1 1").

  2. Затем создается двумерный массив целых чисел, который может содержать все результаты.

  3. Он разбивает каждую строку в ArrayList на массив строк, каждая из которых содержит только одно число.
  4. Для каждой строки она создает массив целых чисел, анализируя каждое число в массиве.
  5. Этот массив 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();
            }
        }
    }
...