2D ArrayListコードを2D配列コードに変更する

Question

このコードはオンラインで見つかったので、指定された配列を置換して、与えられた数の可能な組み合わせをすべて返すことができます。誰もこのコードを変更して2D配列を組み込む方法を知っていますか？

public static ArrayList<ArrayList<Integer>> permute(int[] numbers) { 
    ArrayList<ArrayList<Integer>> permutations = new ArrayList<ArrayList<Integer>>(); 

    permutations.add(new ArrayList<Integer>()); 

    for (int i = 0; i < numbers.length; i++) { 

     ArrayList<ArrayList<Integer>> current = new ArrayList<ArrayList<Integer>>(); 
     for (ArrayList<Integer> p : permutations) { 
      for (int j = 0, n = p.size() + 1; j < n; j++) { 
       ArrayList<Integer> temp = new ArrayList<Integer>(p); 
       temp.add(j, numbers[i]); 
       current.add(temp); 
      } 
     } 
     permutations = new ArrayList<ArrayList<Integer>>(current); 
    } 

    return permutations; 
} 

これは私がしようとしたものである：

public static int[][] permute(int[] numbers){ 
    int[][] permutations = new int[24][4]; 
    permutations[0] = new int[4]; 
    for (int i = 0; i < numbers.length; i++) { 
     int[][] current = new int[24][4]; 
     for (int[] permutation : permutations) { 
      for (int j = 0; j < permutation.length; j++) { 
       permutation[j] = numbers[i]; 
       int[] temp = new int[4]; 
       current[i] = temp; 

      } 

     } 
     permutations = current; 
    } 
    return permutations; 

} 

は、しかし、これはすべてゼロを返します。私は24と4を選択しました。なぜなら、それは私が必要とする2D配列のサイズなのですから。 ありがとう

Answer 1

本当に簡単ではありません。元のコードはArrayListのより動的な振る舞いを利用しているので、少し手作業でコーディングする必要があります。あなたのコードには多くの正しい考えがあります。私が見た問題の説明を書こうとしましたが、時間がかかりすぎたので、代わりにコードを修正することにしました。

元のtemp.add(j, numbers[i]);は、配列の最も難しい部分です。これは、要素を右の位置の1つの位置jの位置にプッシュすることを呼び出すためです。私のバージョンでは、ミドルループでtemp配列を1回作成し、一番内側のループで一度に1つの要素をシャッフルします。

public static int[][] permute(int[] numbers) { 
    // Follow the original here and create an array of just 1 array of length 0 
    int[][] permutations = new int[1][0]; 
    for (int i = 0; i < numbers.length; i++) { 
     // insert numbers[i] into each possible position in each array already in permutations. 
     // create array with enough room: when before we had permutations.length arrays, we will now need: 
     int[][] current = new int[(permutations[0].length + 1) * permutations.length][]; 
     int count = 0; // number of new permutations in current 
     for (int[] permutation : permutations) { 
      // insert numbers[i] into each of the permutation.length + 1 possible positions of permutation. 
      // to avoid too much shuffling, create a temp array 
      // and use it for all new permutations made from permutation. 
      int[] temp = Arrays.copyOf(permutation, permutation.length + 1); 
      for (int j = permutation.length; j > 0; j--) { 
       temp[j] = numbers[i]; 
       // remember to make a copy of the temp array 
       current[count] = temp.clone(); 
       count++; 
       // move element to make room for numbers[i] at next position to the left 
       temp[j] = temp[j - 1]; 
      } 
      temp[0] = numbers[i]; 
      current[count] = temp.clone(); 
      count++; 
     } 
     assert count == current.length : "" + count + " != " + current.length; 
     permutations = current; 
    } 
    return permutations; 
} 

temp配列を使用したトリックは、私がorigianlコードと同じ順序で並べ替えを取得しないことを意味します。これが必要条件である場合は、にインデックス01から開始し、逆の方法でループをシャッフルしてpermutationをコピーしてください。 System.arraycopy()は初期コピーを行うことがあります。

Answer 2

ここでの問題は、ArrayList.add(int,value)コマンドの配列バージョンを正しく実装する必要があることです。つまり、System.arraycopy（）を実行し、jの後にあるすべての値を1つ下に押してからjに値を挿入します。現在値を設定しています。しかし、これは順列[j]の値を上書きします。実際には順列[j + 1]に移動していなければなりません。

だからここであなたは：

permutation[j] = numbers[i];  

それは次のようになります。

System.arraycopy(permutation,j, permutations, j+1, permutations.length -j); 
permutation[j] = numbers[i]; 

ArrayList.add（int型、値）のことをしたよう。基本的には誤って.set（）として実装しています。

私は個人的にコードをスクラップし、その値を動的に動的に作成するために何かを実行しますが、さらにいくつかの価値観は、メモリに関しては何か禁止的なことを話しています。順列のn番目のインデックスを見つけることは難しくありません。メモリをまったく割り当てなくても。 （ただし、奇妙なことを起こさずにそのようなことをするつもりなら、配列のコピーが必要です）。

public static int[] permute(int[] values, long index) { 
    int[] returnvalues = Arrays.copyOf(values,values.length); 
    if (permutation(returnvalues, index)) return returnvalues; 
    else return null; 

} 
public static boolean permutation(int[] values, long index) { 
    return permutation(values, values.length, index); 
} 

private static boolean permutation(int[] values, int n, long index) { 
    if ((index == 0) || (n == 0)) return (index == 0); 
    int v = n-(int)(index % n); 
    int temp = values[n]; 
    values[n] = values[v]; 
    values[v] = temp; 
    return permutation(values,n-1,index/n); 
}