N
N
Nikolol2019-04-17 20:57:41
Mathematics
Nikolol, 2019-04-17 20:57:41

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 understandable and not intelligible:
Generation of compositions of a natural number n by a given rank m means: split n into m non-negative integer terms in all possible ways.
In other words, to split n successively written ones into a given number m of parts in all possible ways (empty parts are also allowed).
If zeros are chosen as separator characters, then m parts are generated by m-1 separators, i.e. m-1 with zeros. Thus, the task is reduced to enumeration of bit strings of length q=n+m-1, filtering out those in which the number of zeros is different from m-1.
As an auxiliary algorithm, we 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 first set to zero.
The generated sequence is written b[q-1], ..., b[0], b[q] - for technical purposes only: the generating loop ends as soon as b[q] becomes equal to 1.
while b[q] =0 do
begin
1. print 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

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question