Все возможные комбинации N чисел для суммирования X

Question

Я должен написать программу, которая дает n, target и max, возвращает все числовые комбинации размера n, которые суммируются в target, где ни одно число не может быть больше max

Пример:

target = 3
max = 1
n = 4

Вывод:

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

Это очень простой пример, но может быть очень большой набор возможных комбинаций для более сложныхcase.

Я ищу любую алгоритмическую подсказку, но реализация Java была бы идеальной.

Answer 1

Вот Java-версия:

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

public class Main {

    public static void main(String[] args) {
        List<int[]> solutions = generate(3, 1, 4);
        for(int[] c: solutions) {
            System.out.println(Arrays.toString(c));
        }
    }  

    public static List<int[]> generate(int target, int max, int n) {
        return generate(new ArrayList(), new int[0], target, max, n);
    }

    private static List<int[]> generate(List<int[]> solutions, 
            int[] current, int target, int max, int n) {        
        int sum = Arrays.stream(current).sum();
        if (current.length == n) {
            if (sum == target) {
                solutions.add(current);
            }
            return solutions;
        }
        if (sum > target) {
            return solutions; 
        }
        for(int i=0; i <= max; i++) {
            int[] next = Arrays.copyOf(current, current.length + 1);
            next[current.length] = i; 
            generate(solutions, next, target, max, n);
        }
        return solutions; 
    }
}

Answer 2

Это может быть ресурсоемким, но вот мое решение

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

public class Combinations {
    public static void main(String[] args) {

       List<Integer[]> finalPatternList = getCombinations(6, 10, 12);
    }

    static List<Integer[]> getCombinations(int n, int target, int max) {

        /*
            first generate all the combinations on the given n
         */

        List<Integer[]> allCombinationsList = new ArrayList<>();

        //generate the digits list
        List<Integer> digitList = new ArrayList<Integer>();
        for (int i = 0; i <= max; i++) {
            digitList.add(i);
        }
        //generate the number system
        int powerBase = digitList.size();
        int maxPower = n ;
        int totalCombinations = (int) Math.pow(powerBase, maxPower);

        //generating default array
        for (int i = 0; i < totalCombinations; i++) {
            Integer pattern[] =new Integer[n];;
            allCombinationsList.add(pattern);
        }

        //filling the Columns one by one

        for (int i =n  ; i >= 1 ; i -- ){
            int currentColumn = i - 1;
            int noOfIterations =(int) Math.pow(max + 1,  n - i);
            populateRows(allCombinationsList ,digitList ,currentColumn ,noOfIterations );
        }
         /*
           example :

              [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]
              ............

              current row variable is the array index
              if currentRow = 3,
                 pattern 1 - its 0
                 pattern 2 - its 1
                 pattern 3 - its 0
              if currentRow = 2 ,
                 pattern 1 - its 0
                 pattern 2 - its 0
                 pattern 3 - its 1


              iterations means the number of consecutive digits appear on each column
              in column 1 - its 1
              in column 2 - its 2
              in column 3 - its 4


         */




        /*
            select the patterns that match the target
         */

        List<Integer[]> finalPatternList = new ArrayList<>();
        for (Integer[] currentArray : allCombinationsList){

            int sum = 0 ;
            for (int i =0 ; i < currentArray.length ; i++ ){
                sum +=currentArray[i] ;
            }
            if (sum == target) finalPatternList.add(currentArray);

        }
        for (Integer a[] : finalPatternList) {
            System.out.println(Arrays.toString(a));
        }

        return finalPatternList;


    }

    static void populateRows(List<Integer[]> combinationList, List<Integer> digitList, int currentColumn, int iterations) {

        int combinationListPosition = 0;
        while (combinationListPosition < combinationList.size()) {
            int digitListPosition = 0;
            while (digitListPosition < digitList.size()) {
                int currentIteration = 0;
                while (currentIteration < iterations) {

                    if (combinationListPosition == combinationList.size()){
                        // end the loop when all combinations are filled
                        System.out.println();
                         return;
                    }

                    combinationList.get(combinationListPosition)[currentColumn] = digitList.get(digitListPosition);
                    currentIteration++;
                    combinationListPosition ++ ;
                }
                digitListPosition ++ ;
            }
        }




    }
}

Answer 3

Моя идея состояла в том, чтобы генерировать перестановки в сокращении в стиле BFS всякий раз, когда мы выходим за пределы одного из наших условий. Еще одна хитрость - когда мы достигнем цели, нам нужно заполнить все остальное нулями. Вот реализация Python, потому что у меня нет установленной Java прямо сейчас. Это должно быть достаточно легко перевести

def sums(n, target, max, arr=[], sum=0):
    if len(arr) > n or sum > target: 
        return 
    if sum == target:
        print arr + [0 for _ in range(n - len(arr))]
        return 
    for i in range(max) + 1: 
        sums(n, target, max, arr + [i], sum + i)

Образец sums(4, 3, 1)

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