Учитывая числа от 1 до k, выберите d много чисел, чтобы их сумма равнялась v

Question

Я пытаюсь найти количество различных векторов в наборе, который имеет следующие свойства:

• Набор состоит из k чисел, начиная с 1 до k + 1
• D - количество элементов, которые можно выбрать
• V - сумма элементов

Примеры
k = 3, d = 3, v = 6, результат 7;
<1, 2, 3>, <1, 3, 2>, <2, 1, 3>, <2, 2, 2>, <2, 3, 1>, <3, 1, 2>, <3 , 2, 1>

k = 4, d = 2, v = 7, результат 2;
<3, 4>, <4, 3>
В этом случае <2, 5> недопустимо, потому что 5 превышает значение k.

Я хочу выяснить, существует ли математическая формула для вычисления результата. Если нет формулы, насколько эффективно этот алгоритм может быть реализован? Я нашел довольно загадочную реализацию, но мне интересно, можно ли ее улучшить.

public static int NumberOfDistinctVectors(int k, int d ,int v) {
  if((v > k * d) || (v < d)) return 0;
  if(d == 1 || v == d) return 1;
  if(v == d + 1) return d;

  int alpha = 1, beta = 0;
  if(1 < v + k - k * d) 
    alpha = v + k - k * d;

  if(k < v - d + 1)
    beta = k;
  else
    beta = v - d + 1;

  int sum = 0;
  for(int i = alpha; i <= beta; i++) {
    sum += NumberOfDistinctVectors(k, d-1, v-i);
  }

  return sum;
}

Answer 1

Проблема очень связана со следующим:

Какое количество комбинаций для распределения b идентичных объектов в c группах где ни одна группа не содержит более n объектов?

что обсуждается здесь

Просто представьте, что ваши числа сделаны из объекта (+1). Так что в вашем случае

• c = d, потому что каждая группа соответствует одному из ваших чисел
• b = v-d, поскольку вам нужно поместить хотя бы один (+1) объект в каждую из d групп
• n = k-1, так как мы предполагаем, что (+1) уже есть в каждой группе, и не хотим становиться больше, чем k

Найдите код ниже (используя appache-commons для c(N,K))

public static int NumberOfDistinctVectors(int k, int d ,int v) {

    return combinations(v-d, d, k-1);
}

//combinations to distribute b identical objects to c groups 
//where no group has more than n objects
public static int combinations(int b, int c, int n)
{
    int sum = 0;
    for(int i = 0; i <= c; i++)
    {
        if(b+c-1-i*(n+1) >= c-1)
            sum += Math.pow(-1, i) * CombinatoricsUtils.binomialCoefficient(c, i)
                   * CombinatoricsUtils.binomialCoefficient(b+c-1-i*(n+1), c-1);
    }
    return sum;
}

Позвольте мне также процитировать оригинальный ответ:

"действительно ли это более полезно, чем повторение другой вопрос "

Answer 2

Вот еще один способ подсчета, который может быть более эффективным. Он основан на формуле для перестановок с повторением . Я добавил комментарии в коде, надеясь, что ему будет легче следовать.

public static int NumberOfDistinctVectors2(int k, int d, int v)
{
    return NumberOfDistinctVectors2_rec(1, 0, k, d, v, 1, 1);
}

public static int NumberOfDistinctVectors2_rec(
    int i,     /* Current number being added */
    int j,     /* Amount of already picked numbers */
    int k,     /* Maximum number that can be picked */
    int d,     /* Total amount of numbers to pick */
    int v,     /* Remaining value */
    long num,  /* Numerator in "permutations with repetition" formula */
    long den)  /* Denominator in "permutations with repetition" formula */
{
    // Amount of remaining numbers to pick
    int rem = d - j;
    // Remaining value is too big or too small
    if (v < i * rem || v > k * rem) return 0;
    // If no numbers to add then we are done
    if (rem == 0) return Math.toIntExact(num / den);
    // If only one number to add this can be used as a "shortcut"
    if (rem == 1) return d * Math.toIntExact(num / den);

    // Counted permutations
    int count = 0;
    // Maximum amount of repetitions for the current number
    int maxRep = Math.min(v / i, rem);
    // Factor to multiply the numerator
    int numFactor = 1;
    // Factor to multiply the denominator
    int denFactor = 1;
    // Consider adding repetitions of the current number
    for (int r = 1; r <= maxRep; r++)
    {
        // The numerator is the factorial of the total amount of numbers
        numFactor *= (j + r);
        // The denominator is the product of the factorials of the number of repetitions of each number
        denFactor *= r;
        // We add "r" repetitions of the current number and count all possible permutations from there
        count += NumberOfDistinctVectors2_rec(i + 1, j + r, k, d, v - i * r, num * numFactor, den * denFactor);
    }
    // Consider permutations that do not include the current number
    count += NumberOfDistinctVectors2_rec(i + 1, j, k, d, v, num, den);
    return count;
}

Вот небольшой класс, тестирующий его, где этот метод выглядит значительно быстрее ( см. В Rextester ).

class NumberOfDistinctVectorsTest
{
    // Original method
    public static int NumberOfDistinctVectors(int k, int d ,int v)
    {
        if((v > k * d) || (v < d)) return 0;
        if(d == 1 || v == d) return 1;
        if(v == d + 1) return d;

        int alpha = 1, beta = 0;
        if(1 < v + k - k * d) 
            alpha = v + k - k * d;

        if(k < v - d + 1)
            beta = k;
        else
            beta = v - d + 1;

        int sum = 0;
        for(int i = alpha; i <= beta; i++)
        {
            sum += NumberOfDistinctVectors(k, d-1, v-i);
        }

        return sum;
    }

    // New method
    public static int NumberOfDistinctVectors2(int k, int d, int v)
    {
        return NumberOfDistinctVectors2_rec(1, 0, k, d, v, 1, 1);
    }

    public static int NumberOfDistinctVectors2_rec(int i, int j, int k, int d, int v, long num, long den)
    {
        int rem = d - j;
        if (v < i * rem || v > k * rem) return 0;
        if (rem == 0) return Math.toIntExact(num / den);
        if (rem == 1) return d * Math.toIntExact(num / den);

        int count = 0;
        int maxRep = Math.min(v / i, rem);
        int numFactor = 1;
        int denFactor = 1;
        for (int r = 1; r <= maxRep; r++)
        {
            numFactor *= (j + r);
            denFactor *= r;
            count += NumberOfDistinctVectors2_rec(i + 1, j + r, k, d, v - i * r, num * numFactor, den * denFactor);
        }
        count += NumberOfDistinctVectors2_rec(i + 1, j, k, d, v, num, den);
        return count;
    }

    public static void main(final String[] args)
    {
        // Test 1
        System.out.println(NumberOfDistinctVectors(3, 3, 6));
        System.out.println(NumberOfDistinctVectors2(3, 3, 6));
        // Test 2
        System.out.println(NumberOfDistinctVectors(4, 2, 7));
        System.out.println(NumberOfDistinctVectors2(4, 2, 7));
        // Test 3
        System.out.println(NumberOfDistinctVectors(12, 5, 20));
        System.out.println(NumberOfDistinctVectors2(12, 5, 20));
        // Test runtime
        long startTime, endTime;
        int reps = 100;
        startTime = System.nanoTime();
        for (int i = 0; i < reps; i++)
        {
            NumberOfDistinctVectors(12, 5, 20);
        }
        endTime = System.nanoTime();
        double t1 = ((endTime - startTime) / (reps * 1000.));
        startTime = System.nanoTime();
        for (int i = 0; i < reps; i++)
        {
            NumberOfDistinctVectors2(12, 5, 20);
        }
        endTime = System.nanoTime();
        double t2 = ((endTime - startTime) / (reps * 1000.));
        System.out.println("Original method: " + t1 + "ms");
        System.out.println("New method: " + t2 + "ms");
    }
}

Выход:

7
7
2
2
3701
3701
Original method: 45.64331ms
New method: 5.89364ms

---

РЕДАКТИРОВАТЬ: Новый тест (запустить на JDoodle с Apache Commons 3.6.1), включая ответ SaiBot :

import org.apache.commons.math3.util.CombinatoricsUtils;

public class NumberOfDistinctVectorsTest
{
    // Original method
    public static int NumberOfDistinctVectors(int k, int d ,int v)
    {
        if((v > k * d) || (v < d)) return 0;
        if(d == 1 || v == d) return 1;
        if(v == d + 1) return d;

        int alpha = 1, beta = 0;
        if(1 < v + k - k * d) 
            alpha = v + k - k * d;

        if(k < v - d + 1)
            beta = k;
        else
            beta = v - d + 1;

        int sum = 0;
        for(int i = alpha; i <= beta; i++)
        {
            sum += NumberOfDistinctVectors(k, d-1, v-i);
        }

        return sum;
    }

    // jdehesa method
    public static int NumberOfDistinctVectors2(int k, int d, int v)
    {
        return NumberOfDistinctVectors2_rec(1, 0, k, d, v, 1, 1);
    }

    public static int NumberOfDistinctVectors2_rec(int i, int j, int k, int d, int v, long num, long den)
    {
        int rem = d - j;
        if (v < i * rem || v > k * rem) return 0;
        if (rem == 0) return Math.toIntExact(num / den);
        if (rem == 1) return d * Math.toIntExact(num / den);

        int count = 0;
        int maxRep = Math.min(v / i, rem);
        int numFactor = 1;
        int denFactor = 1;
        for (int r = 1; r <= maxRep; r++)
        {
            numFactor *= (j + r);
            denFactor *= r;
            count += NumberOfDistinctVectors2_rec(i + 1, j + r, k, d, v - i * r, num * numFactor, den * denFactor);
        }
        count += NumberOfDistinctVectors2_rec(i + 1, j, k, d, v, num, den);
        return count;
    }

    // SaiBot method
    public static int NumberOfDistinctVectors3(int k, int d ,int v)
    {
        return combinations(v-d, d, k-1);
    }

    //combinations to distribute b identical objects to c groups 
    //where no group has more than n objects
    public static int combinations(int b, int c, int n)
    {
        int sum = 0;
        for(int i = 0; i <= c; i++)
        {
            if(b+c-1-i*(n+1) >= c-1)
                sum += Math.pow(-1, i) * CombinatoricsUtils.binomialCoefficient(c, i)
                       * CombinatoricsUtils.binomialCoefficient(b+c-1-i*(n+1), c-1);
        }
        return sum;
    }

    public static void main(final String[] args)
    {
        // Test 1
        System.out.println(NumberOfDistinctVectors(3, 3, 6));
        System.out.println(NumberOfDistinctVectors2(3, 3, 6));
        System.out.println(NumberOfDistinctVectors3(3, 3, 6));
        // Test 2
        System.out.println(NumberOfDistinctVectors(4, 2, 7));
        System.out.println(NumberOfDistinctVectors2(4, 2, 7));
        System.out.println(NumberOfDistinctVectors3(4, 2, 7));
        // Test 3
        System.out.println(NumberOfDistinctVectors(12, 5, 20));
        System.out.println(NumberOfDistinctVectors2(12, 5, 20));
        System.out.println(NumberOfDistinctVectors3(12, 5, 20));
        // Test runtime
        long startTime, endTime;
        int reps = 100;
        startTime = System.nanoTime();
        for (int i = 0; i < reps; i++)
        {
            NumberOfDistinctVectors(12, 5, 20);
        }
        endTime = System.nanoTime();
        double t1 = ((endTime - startTime) / (reps * 1000.));
        startTime = System.nanoTime();
        for (int i = 0; i < reps; i++)
        {
            NumberOfDistinctVectors2(12, 5, 20);
        }
        endTime = System.nanoTime();
        double t2 = ((endTime - startTime) / (reps * 1000.));
        startTime = System.nanoTime();
        for (int i = 0; i < reps; i++)
        {
            NumberOfDistinctVectors3(12, 5, 20);
        }
        endTime = System.nanoTime();
        double t3 = ((endTime - startTime) / (reps * 1000.));
        System.out.println("Original method: " + t1 + "ms");
        System.out.println("jdehesa method: " + t2 + "ms");
        System.out.println("SaiBot method: " + t3 + "ms");
    }
}

Выход:

7
7
7
2
2
2
3701
3701
3701
Original method: 97.81325ms
jdehesa method: 7.2753ms
SaiBot method: 2.70861ms

Время не очень стабильно в JDoodle (я использовал его, потому что он учитывает зависимости Maven), но в целом метод SaiBot является самым быстрым на сегодняшний день.