1

少し苦労している問題があります。任意の数の配列と「特異性」と呼ばれる整数が与えられた場合、配列の外積内のその点を表す行を生成する必要があります。配列の長さは常に 2 以上で、各配列の最後の値は常に null です。各配列の最後の要素を除いて、他の要素が null になることはありません。たとえば、配列 {1, 2, null} と {A, B, null} が与えられた場合、外積は実質的に次のようになります。

0: 1 A
1: 1 B
2: 1 null
3: 2 A
4: 2 B
5: 2 null
6: null A
7: null B
8: null null

したがって、たとえば上記の 2 つの配列で「特異性」が 4 の場合、配列 {2, B} が返されます。それは簡単な部分です。以下のコードセクションで、この特定のケースを完了しました。ただし、null のない組み合わせが優先される場合を考えてみましょう。順序は次のようになります。

0: 1 A
1: 1 B
2: 2 A
3: 2 B
4: 1 null
5: 2 null
6: null A
7: null B
8: null null

これまでに実装したアルゴリズムは次のとおりです。上記の最初のケースは問題なく処理されますが、2 番目のケースはどうすればよいかわかりません。「else」句に何が入るかについて何か考えはありますか?

    public static String generateKeyForSource(int specificity, KeySource keySource) {
    if (specificity > keySource.getNumPossibleKeys()) {
        throw new IllegalArgumentException("The specificity " + specificity + " is larger than the max number of possible keys for this KeySource, which is " + keySource.getNumPossibleKeys());
    }
    Object[][] hierarchies = keySource.getHierarchies();
    boolean combinedPrecedence = keySource.isCombinedPrecedence();

    int[] indexes = new int[hierarchies.length];
    int multiplier = 1;

    if (!(combinedPrecedence && specificity >= keySource.getFirstSpecificityContainingNull())) {
        for (int i = hierarchies.length - 1; i >= 0; i--) {
            Object[] hierarchy = hierarchies[i];
            int range;
            if (combinedPrecedence)
                range = hierarchy.length - 1;
            else
                range = hierarchy.length;

            int currentArrayIndex = specificity / multiplier % range;
            indexes[i] = currentArrayIndex;
            multiplier *= hierarchies[i].length;
        }
    }
    else {
        //?????????
    }

    return generateKey(indexes, hierarchies);
}
4

1 に答える 1

1

この種の問題の解決策を探すとき、帰納法はあなたの味方です。

簡単なケースでは、次のようになります

easy( a, i ) ≡ easyHelper( a, a.length, i )  
easyHelper( a, n, i ) ≡ easyInduction( easyHelper, 0 )( a, n, i )

easyInduction( f, b )( a, 0, 0 ) ≡ []  
easyInduction( f, b )( a, 0, i + 1 ) ≡ undefined
easyInduction( f, b )( a, n + 1, i ) ≡
   let t = a[n + 1].length - b
    in f( a, n, ⌊i / t⌋ ) ++ [ a[n + 1][i mod t] ]

難しいケースについては、より強い帰納的な仮定が必要だと思います。つまり、ヘルパー再帰メソッドは、オフセットとタプルへの特異性をマッピングする関数の両方を返す必要があります。関数は、オフセットより下のインデックスに適用されると、すべての配列の外積のメンバを null を削除して返します。オフセットを超えると、null ケースが開始されます。n配列の場合についてこれを知っていれば、次の 3 つのケースを介して、 n + 1 配列の新しいオフセットと新しい関数を作成できます。

  1. あなたは新しいオフセットよりも小さいので、最後の配列の非 null メンバーの簡単なケースのように扱います
  2. あなたは新しいオフセットと新しいオフセットと古いオフセットの合計の間にいるので、最後に null を含む再帰的な結果を返す必要があります
  3. あなたは合計よりも大きいので、再帰呼び出しが古いオフセットを超えたインデックスを使用することを確認することを除いて、再び簡単なケースのように扱います

これが私のテストされていない疑似コードです。

hard( a, i ) ≡ hardHelper( a, a.length ).second( i )
hardHelper( a, 0 ) ≡ ( 1, { case 0 => [] } )
hardHelper( a, n + 1 ) ≡
  let t = a[n + 1].length
  and ( k, f ) = hardHelper( a, n )
  and k' = k * ( t - 1 )
  and f'( i ) =
        if ( i < k' )
        then easyInduction( f, 1 )( a, n + 1, i )
        else if ( k' <= i < k' + k )
        then easyInduction( f, 1 )( a[ 0..n ] ++ [ [ null ] ], n + 1, i - k' )
        else easyInduction( ( b, m, j ) => f( b, m, j + k ), 0 )( a, n + 1, i - k' - k )
   in ( k', f' )
于 2013-10-15T03:42:56.560 に答える