1

私はJavaをまったく使い始めたばかりです。私はAndroidゲームを書いていますが、指定された数になる可能性のあるすべての合計（2を含むまたは8より大きい数を含む組み合わせを除く）を含むint配列の配列を生成する必要があります。

例： 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古いバージョンではすべての組み合わせが返されないため（10の場合は[5,5]など）、このコードfor(int j = n-1; j > n/2; j--) {をこれ に変更する必要があります。for(int j = n-1; j >= n/2; j--) {

そして、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;
}
4

1 に答える 1

2

これは最も美しいコードではありませんが、参照したコードを変更して、希望どおりに動作します。また、かなり高速です。(スタックを使用して) 再帰を避け、文字列から整数への変換を完全に回避することで、高速化できます。戻ってそれらの変更を編集するかもしれません。かなり古いラップトップで実行すると、505 秒以内に (204226 個すべての) パーティションが出力されました。

このpartition(N)コードで終了するpartitionsと、 のパーティションが保持されNます。

  1. 最初に、スペースで区切られた形式 (例: ) の合計の文字列表現の ArrayList を構築します" 1 1 1"。

  2. 次に、すべての結果を保持できる int の 2 次元配列を作成します。

  3. ArrayList 内の各文字列を、それぞれが単一の数値のみを含む文字列の配列に分割します。
  4. String ごとに、各数値を配列に解析して int の配列を作成します。
  5. 次に、この int 配列が int の 2 次元配列に追加されます。

ご不明な点がございましたら、お気軽にお問い合わせください。

    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();
            }
        }
    }
于 2011-11-26T09:15:07.227 に答える