1

Нужен алгоритм. Есть размер size и сумма чисел M, нужно найти все варианты перебора чисел с условием, что сумма в строке M.
Например size = 6, а M = 2.
2 0 0 0 0 0
0 2 0 0 0 0
0 0 2 0 0 0
0 0 0 2 0 0
0 0 0 0 2 0
0 0 0 0 0 2
1 1 0 0 0 0
1 0 1 0 0 0
1 0 0 1 0 0
1 0 0 0 1 0
1 0 0 0 0 1
0 1 1 0 0 0
0 1 0 1 0 0
0 1 0 0 1 0
0 1 0 0 0 1
0 0 1 1 0 0
0 0 1 0 1 0
0 0 1 0 0 1
0 0 0 1 1 0
0 0 0 1 0 1
0 0 0 0 1 1

4
  • 1
    А сами-хоть пытались реализовать?
    – selya
    26 дек 2017 в 1:07
  • да, второй день уже, половина минимум теряется где то, если задать M хотя бы 5. А время начинает поджимать сильно.
    – Elizar
    26 дек 2017 в 1:10
  • Покажите ваш вариант решения, я помогу исправить
    – selya
    26 дек 2017 в 1:12
  • не думаю, что кто-то захочет решать за вас задачу. показывайте свое решение и объясните, что именно не можете реализовать. может что-то и придумаем... на вскидку я бы брал два массива размера size. один хранит комбинации, второй - массив множителей. а потом крутил бы цикл от М до 0. массив множителей, соответсвенно, просчитывает метод, который работает как разряды в калькуляторе, не позволяя при любой комбинации подставить число большее, чем size. а дальше дело техники... 26 дек 2017 в 1:34

2 ответа 2

2

Другими словами, вам надо просто перебрать все способы разложить M горошин по size стаканам. Ваши комбинации - это просто способы раскладки: количество горошин в каждом стакане.

Пусть положение каждой горошины определяется значением в диапазоне [0, size) - это номер ее стакана. Всего горошин M. Тогда каждая раскладка горошин однозначно соответствует вектору из M чисел. Можно считать этот вектор M-значной записью числа в size-ричной системе счисления. Однако такая интерпретация раскладок предполагает, что горошины отличаются друг от друга, и раскладки, получающиеся обменом горошин, являются разными. (Это ни что иное, как размещения с повторениями из size по M.)

В этой же задаче горошины считаются неотличимыми друг от друга и раскладки, отличающиеся лишь порядком горошин, являются одинаковыми. (То есть нас интересуют сочетания с повторениями из size по M.) Чтобы исключить из рассмотрения лишние раскладки, можно ограничиться рассмотрением только M-значных чисел в size-ричной системе счисления, у которых цифры в записи не возрастают (если смотреть от младших к старшим).

Получаем алгоритм: перебираем M-значные числа в size-ричной системе счисления, у которых цифры в записи не возрастают. И на основе каждого такого числа строим карту раскладки горошин по стаканам.

"Лобовая" реализация этого алгоритма будет может выглядеть так: перебираем все числа от 0 до Msize-1, проверяем будут ли цифры в size-ричной записи этого числа невозрастающими, и если да, то "расшифровываем" раскладку горошин, соответствующую этому числу. Например, на С++

#include <vector>
#include <iostream>

unsigned pow(unsigned a, unsigned b)
{
  unsigned p = 1;
  for (unsigned n = b; n > 0; --n)
    p *= a;

  return p;
}

bool check_digits(unsigned v, unsigned size)
{
  unsigned prev_digit = -1;
  for (; v > 0; v /= size)
  {
    unsigned digit = v % size;
    if (digit > prev_digit)
      return false;

    prev_digit = digit;  
  }

  return true;
}

std::vector<unsigned> decode(unsigned v, unsigned m, unsigned size)
{
  std::vector<unsigned> r(size);
  for (; m > 0; --m, v /= size)
    ++r[v % size];

  return r;
}

void print(const std::vector<unsigned> &r)
{
  for (unsigned i : r)
    std::cout << i << " ";

  std::cout << std::endl;
}

int main()
{
  const unsigned M = 2;
  const unsigned SIZE = 6;

  for (unsigned v = 0, max = pow(SIZE, M); v < max; ++v)
    if (check_digits(v, SIZE))
      print(decode(v, M, SIZE));
}

Результат

2 0 0 0 0 0
1 1 0 0 0 0
1 0 1 0 0 0
1 0 0 1 0 0
1 0 0 0 1 0
1 0 0 0 0 1
0 2 0 0 0 0
0 1 1 0 0 0
0 1 0 1 0 0
0 1 0 0 1 0
0 1 0 0 0 1
0 0 2 0 0 0
0 0 1 1 0 0
0 0 1 0 1 0
0 0 1 0 0 1
0 0 0 2 0 0
0 0 0 1 1 0
0 0 0 1 0 1
0 0 0 0 2 0
0 0 0 0 1 1
0 0 0 0 0 2

Но "лобовая" реализация весьма неэффективна именно из-за своей манеры итерировать через все числа, когда нас интересуют далеко не все. Например, для того, чтобы решить задачу для 6 горошин и 6 стаканов эта реализация будет вынуждена сделать 66=46656 итераций, проверяя цифры на каждой из них, в то время как интересующих нас вариантов всего 462. (Не говоря даже об очевидной опасности переполнения при вычислении Msize.)

Более остроумная реализация не будет перебирать все числа, отсеивая ненужные, а сразу будет генерировать именно и только интересующие нас числа с невозрастающими цифрами. Опять же на С++

#include <vector>
#include <iostream>

bool next(std::vector<unsigned> &p, unsigned size)
{
  auto it = p.begin();

  for (; it < p.end(); ++it)
    if (++*it < size)
      break;

  if (it == p.end())
    return false;

  unsigned v = *it;

  while (it != p.begin())
    *--it = v;

  return true;
}

std::vector<unsigned> decode(const std::vector<unsigned> &p, unsigned size)
{
  std::vector<unsigned> r(size);
  for (unsigned i : p)
    ++r[i];

  return r;
}

void print(const std::vector<unsigned> &r)
{
  for (unsigned i : r)
    std::cout << i << " ";

  std::cout << std::endl;
}

int main()
{
  const unsigned M = 2;
  const unsigned SIZE = 6;

  std::vector<unsigned> p(M);
  do
    print(decode(p, SIZE));
  while (next(p, SIZE));
}

M-значное число в size-ричной системе счисления хранится в массиве p. Функция next дает нам следующее число с невозрастающими цифрами.


Ну и напоследок можно заметить, что задача легко решается рекурсивным алгоритмом, который не так интересен, как приведенные выше :)

#include <vector>
#include <iostream>

void print(unsigned m, unsigned size, std::vector<unsigned> &r)
{
  if (size == 1)
  {
    r.push_back(m);

    for (unsigned v : r)
      std::cout << v << " ";
    std::cout << std::endl;

    r.pop_back();
  }
  else
    for (unsigned i = 0; i <= m; ++i)
    {
      r.push_back(i);
      print(m - i, size - 1, r);
      r.pop_back();
    }
}

int main()
{
  const unsigned M = 2;
  const unsigned SIZE = 6;

  std::vector<unsigned> r;
  print(M, SIZE, r);
}
2

вроде работает, может пригодится кому.

public static void allCombinations(int m, int n) {
    int[] combination = new int[n + 1];
    Boolean bool = false;
    int t = m;
    int h = 0;
    do {
        if (bool) {
            if (t > 1) {
                h = 0;
            }
            h++;
            t = combination[h];
            combination[h] = 0;
            combination[1] = t - 1;
            combination[h + 1]++;
        } else {
            combination[1] = m;
            for (int i = 2; i <= n; i++) {
                combination[i] = 0;
            }
        }
        System.out.println(Arrays.toString(combination));
        bool = combination[n] != m;
    } while (bool);
}

public static void main(String[] args) {
    allCombinations(2, 6);
}
2
  • Я тут нашел темку на mathematics. В ваш код сидеть и вникать не хочется, скажите только, у вас логически решено подобным образом, или же иначе?
    – selya
    26 дек 2017 в 3:11
  • Если размер задаёшь меньше 6, выдаёт неправильно, лишний нулевой элемент показывает
    – RodGers
    26 дек 2017 в 3:33

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.