java - 总和为 16 的 int 数组的排列

Question

我有一个方法会根据值返回一个 double 值。数组中的每个整数都介于 1 到 6 之间，表示连续掷骰子。

数组可以是 16 个槽，也可以是 4 个槽，顺序很重要。我不知道如何用 Java 编写代码来查看总计至少为 16 的每个排列。在线查看没有任何帮助。

下面是我可怜的代码

public double findMax() {
    int[] dice = new int[gameBoard.length];
    for(int x : dice) x = 1;
    double max = playGame(dice);
    /* 
    int pos = 0;
    for(int i = 0; i < dice.length; i++) {
        double test = playGame(dice);
        if(test > max) test = max;
    */

    //This is where I need help, to use the int[] dice for all combinations
    //playGame(dice) yields a double
}

Answer 1

有不同的方法可以做到这一点，但递归似乎对我来说是最好的(比如寻路算法)。看起来这应该是 4 到 16 个骰子的排列，总计 16 或更大(如果数组的长度为 16，则每种可能的组合都会产生 16 或更大的值，所以我不确定是什么目的检查该长度的排列会产生)。

我可以使用 ArrayList 或使用字符串来实现解决方案。我不想在递归函数中使用常规数组，因为它们依赖于固定大小。不过一定要添加 import java.util.ArrayList;。

无论如何，这是我使用 ArrayLists 的代码版本。 (注意，我还没有测试这段代码)

public ArrayList<ArrayList<int>> findPermutations( int size ) {

    // To allow the function to work with sizes less than 1
    if ( size < 1 )
        return new ArrayList<ArrayList<int>>();

    ArrayList<ArrayList<int>> permutations = new ArrayList<ArrayList<int>>();

    ArrayList<ArrayList<int>> l1 = findPermutations( new ArrayList<int>(), size, 1 );
    l1.addAll( findPermutations( new ArrayList<int>(), size, 2 ) );
    l1.addAll( findPermutations( new ArrayList<int>(), size, 3 ) );
    l1.addAll( findPermutations( new ArrayList<int>(), size, 4 ) );
    l1.addAll( findPermutations( new ArrayList<int>(), size, 5 ) );
    l1.addAll( findPermutations( new ArrayList<int>(), size, 6 ) );


    for( ArrayList<int> a : l1 ) {
        if ( computeSum( a ) >= 16 ) {
            permutations.add( a );
        }
    }

    return permutations;

}

public ArrayList<ArrayList<int>> findPermutations( ArrayList<int> record, int size, int value ) {


    record.add( value );

    if ( record.size() >= size ) {
        ArrayList<ArrayList<int>> bc = new ArrayList<ArrayList<int>>();
        bc.add( record );
        return bc;
    }

    ArrayList<ArrayList<int>> permutations = findPermutations( record.clone(), size, 1 );
    permutations.addAll( findPermutations( record.clone(), size, 2 ) );
    permutations.addAll( findPermutations( record.clone(), size, 3 ) );
    permutations.addAll( findPermutations( record.clone(), size, 4 ) );
    permutations.addAll( findPermutations( record.clone(), size, 5 ) );
    permutations.addAll( findPermutations( record.clone(), size, 6 ) );

    // For variable size array checking
    if ( record.size() >= 4 ) {
        permutations.add( record );
    }


    return permutations;
}


public int computeSum( ArrayList<int> list ) {

    int total = 0;
    for( int x : list ) {
        total += x;
    }

    return total;

}

当您调用此函数 findPermutations( int size ) 时，您传入大小(数组长度，本质上是游戏板长度)，它将生成所有骰子掷骰组合(特定于顺序)总共至少有 16 个。因为这返回一个 ArrayList，如果你想把它变成一个 double 组，你可以使用 ArrayList 类的 toArray() 函数。

ArrayList<ArrayList<int>> permutations = findPermutations( 16 );
ArrayList<int>[] a = ( ArrayList<int>[] ) permutations.toArray();

这会给你一个 ArrayList 数组

要将其转换为数组的数组，可以使用循环。

int[][] finalVersion = new int[permutations.size()][16];
for( int i = 0; i < permutations.size(); i++ ) {
    finalVersion[i] = ( int[] ) a[i].toArray();
}

这应该有望将其转换回数组数组。

同样，我还没有在代码中对此进行测试，所以要小心错误。我现在将对此进行测试，并在稍后添加另一种不使用 ArrayLists 进行此计算的方法。

编辑:我稍微更改了代码以允许 4 和大小(您只需传入 16)之间的所有排列。