Do you need an algorithm for splitting a natural number n into m parts (zeros are also included) or at least a sketch?

Question

Do you need an algorithm for splitting a natural number n into m parts (zeros are also included) or at least a sketch?

There is an algorithm, but it is not clear and not clear:

Generating compositions of a natural number n by a given rank m means: in all possible ways, divide n into m non-negative integer terms. In other words, divide the n consecutive units into a given number of m parts in all possible ways (empty parts are also allowed). If zeros are chosen as delimiter characters, then m parts are generated by m-1 delimiters, i.e. m-1 zeros. Thus, the task it is reduced to iterating over bit strings of length q=n+m-1, sifting out those in which the number of zeros is different from m-1.

As an auxiliary algorithm, we will need an algorithm for generating all binary sequences of length q. The bit array b[q], b[q-1], ..., b[0] is used, which is initially reset to zero. To write the generated sequence, use b[q-1],..., b[0], b[q] – for technical purposes only: the generating cycle ends as soon as b[q] becomes equal to 1. while b[q]=0 do begin 1. output of the sequence b[q-1],..., b[0]; 2. find the first zero element b[i] from right to left and replace it with one, and erase all elements to the right of it to zero. end

0

алгоритм математика дискретная-математика комбинаторика

Author: Kromster, 2019-04-17

Source

1 answers

score 2 · Accepted Answer

If there are no restrictions on the value of the terms, then the number of partitions is C^m-1_n-1. And it turns out in an obvious way precisely from the approach proposed to you: "divide in all possible ways n consecutive units written in a row into a given number of m parts". This is the method of balls and partitions.

The generation of breaking sequences is easy to organize. The well-known "bitwise" hack looks like this (in C or C++)

unsigned next_combination(unsigned x)
{
  unsigned u = x & -x;
  unsigned v = u + x;
  x = v  + (((v ^ x) / u) >> 2);
  return x;
}

And allows you to generate all bitsets with a fixed number of single bits within a language-supported integer type.

A "non-hack" algorithm is easier to describe without "bit sets". A simple algorithm is the generation of consecutive m-digit numbers in a special number system: the digits of this system lie in the range [1, n) and in each number always go strictly in ascending order. (This is nothing but combinatorial number system, although in in the canonical definition, the numbers usually decrease.) Each digit is the position of the separator between the balls.

For example, for n = 6 and m = 3, we generate 123, 124, 125, 134, 135, 145, 234, 235, ..., 345. Logic sequential generation of such numbers is trivial

#include <stdio.h>
#include <stdlib.h>

#define N 10u
#define M 3u

int main(void) {
  unsigned digits[M];
  unsigned i;

  for (i = 0; i < M; ++i)
    digits[i] = i + 1;

  do {
    unsigned overflow;

    for (i = 0; i < M; ++i)
      printf("[%u]", digits[i]);
    printf("\n");

    for (i = M - 1, overflow = N; i != -1; --i, --overflow)
      if (++digits[i] < overflow)
        break;

    if (i == -1)
      break;

    for (++i; i < M; ++i)
      digits[i] = digits[i - 1] + 1;

  } while (1);
}