Получить наибольшее количество строго равномерно расположенных элементов массива до 'N'

Question

Я хочу получить N элементов из массива, чтобы элементы равномерно располагались между собой. В качестве ограничения я также хочу, чтобы элементы first и last всегда выбирались.

Другие крайние случаи включают:

• N <= 2, который просто возвращает первый и последний элементы.
• N >= Length, который просто возвращает полный массив.

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

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

Например, для L = 6 и N = 3 в произвольной форме:
A = [ 0, 1, 2, 3, 4, 5 ]
R = [ 0, 2, 5 ] или R = [ 0, 3, 5 ]

Однако ни один из результатов не является строго равномерно распределенным, так как для L = 6, N = 3 такой результат просто невозможен.

То, что я ищу, это свободный переменная N . Другими словами, чтобы уменьшить N до ближайшего числа, которое делает проблему возможной.
В случае L = 6, N = 3, это число будет N = 2, что приведет к R = [ 0, 5 ].

Я мог бы сделать решение методом проб и ошибок с ответами из ранее упомянутых ответов (просто тестирование и уменьшение N на 1), но я пытаюсь думать более производительного решения.

Последнее замечание: я ищу идеи, и, таким образом, псевдокод полностью подойдет! Однако я собираюсь реализовать это в Javascript, поэтому, пожалуйста, не полагайтесь на другие специфичные для языка функции c.

Редактировать: Фактические элементы массива могут не быть числами (и нет гарантий порядка).

Answer 1

Для данного Length действительные значения N равны fac+1, где fac - это коэффициент Length-1.

Сначала рассмотрим случаи ребер: 1 и Length-1, очевидно, являются факторами, что дает N=2 и N=Length.

Если Length-1 простое, то это единственные варианты, как в случае с Length=6 в приведенном вами примере.

Для Length=7, {0, 1, 2, 3, 4, 5, 7}, факторы (1,2,3,6), поэтому параметры N=2,3,4,7:

{0, 7}
{0, 3, 7}
{0, 2, 4, 7}
{0, 1, 2, 3 4, 5, 7}

Итак, для заданных Length и N определите наибольшее значение M, такое, что M <= N и M-1 коэффициент Length-1. Примерно так (Java) будет работать:

static int maxN(final int len, final int n)
{
    int maxN = n;
    while((len-1) % (maxN-1) != 0) 
        maxN -= 1;
    return maxN;
}

Могут быть более эффективные подходы.