java - 在给定整数的叉积中生成一行

Question

我遇到了一个有点困扰的问题。给定任意数量的数组和一个称为“特异性”的整数，我需要生成表示数组叉积内该点的行。数组的长度始终至少为 2，并且每个数组的最后一个值始终为 null。除了每个数组中的最后一个元素之外，没有其他元素为空。例如，给定数组 {1, 2, null} 和 {A, B, null}，叉积实际上是:

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

因此，给定“特异性”4(例如上面列出的两个数组)，它应该返回数组 {2, B}。这是最简单的部分。我已经在下面的代码部分中完成了这个特殊案例。但是，请考虑不带空值的组合优先的情况。现在的顺序是:

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

这是我迄今为止实现的算法。上面的第一种情况处理得很好，但我不知道第二种情况该怎么办。关于“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);
}

Answer 1

在寻找此类问题的解决方案时，归纳法是你的 friend 。

对于简单的情况，它看起来像

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

对于困难的情况，我认为你需要一个更强的归纳假设。也就是说，您的辅助递归方法需要返回偏移量和将特定性映射到元组的函数。该函数当应用于偏移量下方的索引时，返回所有删除了空值的数组的叉积成员；高于偏移量时，空情况开始。了解了 n 数组的情况后，您可以通过以下三种情况为 n + 1 数组构造新的偏移量和新函数:

1. 您小于新的偏移量，因此您将其视为最后一个数组的非空成员的简单情况
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' )