Создание строки в кросс-продукте с целым числом

Question

У меня проблема, с которой я немного борюсь. Учитывая произвольное количество массивов и целое число, называемое «специфичностью», мне нужно сгенерировать строку, представляющую эту точку в поперечном произведении массивов. Массивы всегда имеют длину не менее 2, а последнее значение каждого массива всегда равно нулю. Никакие другие элементы никогда не имеют значения, кроме последнего в каждом массиве. Например, учитывая массивы {1, 2, нуль} и {A, B, NULL}, векторное произведение будет эффективно быть:

0: 1 А
1: 1 B
2: 1 нуль
3: 2 A
4: 2 B
5: 2 нуль
6: обнулить
7: нуль-Б
8: Null Null

Таким образом, учитывая 'специфичность' 4, например, с два перечисленных выше массива, он должен rn назад массив {2, B}. Это легкая часть. Я завершил этот конкретный случай в разделе кода ниже. Однако рассмотрим случай, когда комбинации без нулей имеют приоритет. Упорядочение теперь будет:

0: 1 А
1: 1 B
2: 2 A
3: 2 Б
4: 1 нуль
5: 2 нуль
6: обнулить
7: нуль B
8: Null Null

Вот алгоритм я реализовал до сих пор. Первый случай выше обрабатывается просто отлично, но я не знаю, что делать для второго случая. Любые мысли о том, что будет включено в предложение «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

Индукция - ваш друг, ища решения этой проблемы.

Для удобного случая, это выглядит как

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

Для трудного случая, я думаю, нужно более сильное предположение индукции. То есть, ваш вспомогательный рекурсивный метод должен возвращать как привязки, так и функции, связанные с привязкой к кортежам. Функция, применяемая к индексам ниже offset, возвращает член перекрестного произведения всех массивов с удаленными нулями; выше смещения начинаются нулевые случаи.Зная это для случая п массивов, вы можете построить новое смещение и новая функция для п + 1 массивов, с помощью следующих трех случаев:

1. вы меньше, чем новое смещения, поэтому вы относитесь к нему как к легкому случаю для ненулевых членов последнего массива
2. вы находитесь между новым смещением и суммой новых и старых смещений, поэтому вы должны вернуть рекурсивный результат с нулем на end
3. вы больше, чем сумма, поэтому вы снова относитесь к нему как к легкому случаю, за исключением того, что в рекурсивных вызовах там используются индексы beyon d старое смещение

Вот мой непроверенный psuedo-код.

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')