Алгоритм разбивки на страницы, который не позволяет странице быть слишком большой или маленькой - PullRequest
Новая
       129

Алгоритм разбивки на страницы, который не позволяет странице быть слишком большой или маленькой

0 голосов
/ 12 июля 2020

Я хочу написать алгоритм нумерации страниц, который равномерно распределяет количество элементов на страницу с указанием минимального и максимального количества элементов на странице. По возможности, я хотел иметь максимальное количество элементов на странице, которое она может иметь, не нарушая правила минимума.

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

  describe('paginate()', () => {
    it('puts everything on one page is less than or equal to maximum', () => {
      expect(paginate([1, 2], 1, 8)).toEqual([[1, 2]]);
      expect(paginate([1, 2], 3, 8)).toEqual([[1, 2]]);
      expect(paginate([1, 2], 1, 2)).toEqual([[1, 2]]);
    });

    it('divides everything evenly if there are no remainders on the max', () => {
      expect(paginate([1, 2, 3, 4, 5, 6], 1, 3)).toEqual([
        [1, 2, 3],
        [4, 5, 6],
      ]);
      expect(paginate([1, 2, 3, 4, 5, 6], 1, 2)).toEqual([
        [1, 2],
        [3, 4],
        [5, 6],
      ]);
    });

    it('merges the last page if there is one left over', () => {
      let outcome = paginate([1, 2, 3, 4, 5, 6, 7], 2, 4);
      expect(outcome).toEqual([
        [1, 2, 3, 4],
        [5, 6, 7],
      ]);
      outcome = paginate([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 2, 4);
      console.log('outcome', outcome);
      expect(outcome).toEqual([
        [1, 2, 3, 4],
        [5, 6, 7],
        [8, 9, 10],
      ]); // THIS TEST FAILS
    });

    it('can reduce page sizes if it makes elements evenly distributed', () => {
      let outcome = paginate(_.range(1, 12), 6, 10);
      expect(outcome).toEqual(
        [
          [1, 2, 3, 4, 5, 6],
          [7, 8, 9, 10, 11],
        ],
        JSON.stringify(outcome)
      );
      outcome = paginate(_.range(1, 22), 6, 10);
      expect(outcome).toEqual(
        [
          [1, 2, 3, 4, 5, 6, 7],
          [8, 9, 10, 11, 12, 13, 14],
          [15, 16, 17, 18, 19, 20, 21],
        ],
        JSON.stringify(outcome)
      );
    });
  });

Вот мой код: 

import _ from 'lodash';

export const paginate = <T>(content: T[], min: number, max: number): T[][] => {
  const length = content.length;
  for (let i = max; i > min; i--) {
    if (length % i === 0 || length % i >= min) {
      const result = _.chunk(content, i);
      console.log(result);
      return result;
    }
  }
  console.log('end');
  return _.chunk(content, min);
};

здесь не работает только один из моих тестов, но я не знаю, как его пройти : 

  outcome = paginate([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 2, 4);
  console.log('outcome', outcome);
  expect(outcome).toEqual([
    [1, 2, 3, 4],
    [5, 6, 7],
    [8, 9, 10],
  ]); // THIS TEST FAILS

вывод [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10 ] ] вместо того, что я хочу. Каждый раз, когда я думаю о решении этой проблемы, это срывает очередной тест. Я работаю уже несколько часов и застрял. Я не знаю, как пройти все эти тесты. Кроме того, есть ли какие-то крайние случаи, о которых я, возможно, не подумал?

Я не привязан к подписи I ' мы придумали для этой функции, поэтому, если есть смысл изменить ее, не стесняйтесь. Например, я не совсем уверен, что мне вообще нужно предоставлять минимум.

1 Ответ

1 голос
/ 12 июля 2020

Я хотел бы сделать что-то вроде этого: 

function paginate<T>(arr: T[], maxPerPage: number): T[][] {
    const numPages = Math.ceil(arr.length / maxPerPage);
    const minPerPage = Math.floor(arr.length / numPages);
    const numBigPages = arr.length % numPages;
    console.log(numPages, minPerPage, numBigPages)
    const ret: T[][] = [];
    for (let pageNum = 0, curElem = 0; pageNum < numPages; pageNum++) {
        const numOnThisPage = minPerPage + (pageNum < numBigPages ? 1 : 0);
        ret.push(arr.slice(curElem, curElem + numOnThisPage));
        curElem += numOnThisPage;
    }
    return ret;
}

Идея состоит в том, чтобы запрашивать только максимальное количество элементов на странице maxPerPage и определять количество страниц numPages по деление длины массива на этот максимум, округление до целого числа, если необходимо.

Затем задача состоит в том, чтобы разделить элементы на эти страницы. Опять же, вы можете разделить длину массива на количество страниц (arr.length / numPages) и поместить это количество элементов на каждую страницу. Если это не целое число, тогда некоторые «маленькие» страницы будут иметь целое число меньше, чем это, minPerPage = Math.floor(arr.length / numPages), а некоторые «большие» страницы будут иметь еще одно, minPerPage + 1. Вы можете рассчитать количество больших страниц numBigPages, взяв остаток при делении длины массива на количество страниц. (Если это сбивает с толку, представьте, что вы распределяете по numPages страницам по одному элементу; вы в конечном итоге добавляете minPerPage на каждую страницу, и тогда у вас останутся некоторые остатки. Скорее всего, вы больше не захотите чем один из этих остатков на странице, поэтому количество остатков равно количеству больших страниц numBigPages.)

Итак, как нам распределить остатки на большие страницы? Похоже, вы хотите, чтобы сначала были все большие страницы, а затем все маленькие. Поэтому мы просто следим за тем, чтобы, если номер текущей страницы меньше, чем количество больших страниц, мы делаем ее большой страницей, а в противном случае - маленькой.

Давайте посмотрим, как это работает на ваших примерах: 

const range = (n: number) => Array.from({ length: n }, (_, i) => i + 1);

console.log(JSON.stringify(paginate(range(2), 8))); // [[1,2]]
console.log(JSON.stringify(paginate(range(2), 2))); // [[1,2]]
console.log(JSON.stringify(paginate(range(6), 3))); // [[1,2,3],[4,5,6]]
console.log(JSON.stringify(paginate(range(6), 2))); // [[1,2],[3,4],[5,6]]

console.log(JSON.stringify(paginate(range(7), 4))); // [[1,2,3,4],[5,6,7]]
console.log(JSON.stringify(paginate(range(10), 4))); // [[1,2,3,4],[5,6,7],[8,9,10]]

console.log(JSON.stringify(paginate(range(11), 10))); // [[1,2,3,4,5,6],[7,8,9,10,11]]
console.log(JSON.stringify(paginate(range(21), 10)));
// [[1,2,3,4,5,6,7],[8,9,10,11,12,13,14],[15,16,17,18,19,20,21]]

Это похоже на то, что вы хотели, верно?

Очевидно, что точная реализация этого алгоритма может измениться; если вы хотите использовать loda sh или создать массив с помощью чисто функциональных методов вместо повторения и использования push(), решать вам. Но концепция basi c, похоже, соответствует тому, что вы хотите. В любом случае, надеюсь, это позволит вам продолжить. Удачи!

Детская площадка ссылка на код

...