Простой способ разбить его на части - сложить счет в виде частей.(Для моих примеров я использовал индекс на основе 1)
Допустим, вам дан кортеж (меньше цифр, но тот же принцип) (2, 3, 4).Его позиция - это просто сумма:
- (1, x, y) - всех чисел, которые вписываются в это
- (2, 2, x)
- (2, 3, x) - где x <4 </li>
, и вы можете это выяснить итеративно.
Теперь, для D = 3 цифры и K элементов, вы можетевытяните шаблон и посмотрите, как он растет:
K = 1
1 1 1
K = 2
1 1 1
1 1 2
1 2 2
2 2 2
K = 3
1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3
для каждой итерации вы фактически берете предыдущие группировки (включая пустую группировку) и добавляете дополнительное число - как впоследовательность треугольных чисел.Вы даже можете думать об этом рекурсивно, увеличивая первую цифру - в приведенном выше примере с D = 3, K = 3 вы можете переназначить символы материала, который не начинается с «1», и, таким образом,они не содержат никаких «1» - D по-прежнему 3, но K теперь 2:
K = 3 (ignoring 1's)
2 2 2
2 2 3
2 3 3
3 3 3
становится:
K = 2
1 1 1
1 1 2
1 2 2
2 2 2
Это то, как вы бы добавили к K.(Для D = 3 обратите внимание, что это треугольные числа.)
Как насчет добавления цифры?Ну, для K = 3, D = 3, вы можете себе представить, учитывая это:
K = 3
1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3
и добавить цифру перед ними.Вы можете добавить «1» перед всеми ними.Вы можете добавить только «2» перед «2» или выше, и «3» к тому, у которого только «3».Теперь вы можете увидеть рекурсивную структуру.
Для простого примера, чтобы найти индекс (2, 4, 4) с D = 3, K = 5:
index( 2, 4, 4 ) =
# number of leading 1's, and re-index
index( 3, 3 ) + count( D = 2, K = 5 ) =
index( 3, 3 ) + 15 =
# number of leading 1's and 2's, and re-index
index( 1 ) + count( D = 1, K = 4 ) + count( D = 1, K = 3 ) + 15 =
index( 1 ) + 4 + 3 + 15 = index( 1 ) + 22 =
22
Такindex (2, 4, 4) = 22 * 1034 *
Теперь сложная часть вычисляет счет (D, K), который на самом деле просто C (K + D - 1, D).Теперь вы можете обобщить это на K = 15, D = 7.
// This is actually 0-based.
// Really should use an array or something to make it easy to generalize,
// so I'm going to skip a lot of cut and paste
private static int getEntryAt( int i, int j, int k, int l, int m, int n, int o ) {
int D = 7, K = 15;
int total = 0;
if ( i > 0 ) {
for ( int index = 0; index < i; index++ ) {
total += count( D, K - index );
}
}
j -= i, k -= i, l -= i, m -= i, n -= i, o -= i;
D--;
K -= i;
// repeat for j, k, ...
return count;
}