1
$\begingroup$

I'm trying to write a code to generate incremental sequences of numbers such as:

0 + 1 + 3 + 5 + 1 = 9 
0 + 5 + 1 + 1 + 1 = 8 
0 + 1 + 1 + 2 + 1 = 5

I have 3 constraints:

1) I need to have limited number of addends (here it is =5)

2) final sum must be smaller than certain limit ( here limit is <9)

3) addends must be random

As for now, I generate sequences randomly and select only suitable ones. For 2-digit numbers and for long sequences (>8) my algorithm takes significant time.

Is there a better algorithm for such problem?

As least could you tell me, what branch of CS is studying such problems?

UPDATE (algorithm):

0) array = [0,]; // initial array
1) if sum(array) > 99, go to 6)
2) generate random number in [1..99], let's say rand = 24
3) rand = array[-1] + rand // add random number to last value of array
4) array.push(rand) // add the random number to array
5) goto 1)
6) if length(array) < 5, goto 0) // 5 is desired sequence length
$\endgroup$
  • $\begingroup$ It seems your question boils down to finding a "good" mapping between a bit space $\{0,1\}^m$ and $B_{n, a} = \{ x \in \mathbb{R}^n \mid \lVert x \rVert_1 \le a \} \cap \mathbb{N}^n$, "good" meaning $m$ is (closest as possible to) a multiple of $|B_{n,a}|$. I'm unsure whether this is not better posed as a math (e.g., combinatorics) question. $\endgroup$ – dkaeae Jun 13 at 7:05
  • $\begingroup$ What does bit space represents? $\endgroup$ – microspace Jun 13 at 8:11
  • $\begingroup$ In this case, it's just a general name for $\{ 0,1\}^m$, that is, the set of words over $\{0,1\}$ (i.e., binary words) of length $m$. $\endgroup$ – dkaeae Jun 13 at 8:24
  • $\begingroup$ thank you! now I know that my question refers to Partitioning - fundamental problem in number theory. $\endgroup$ – microspace Jun 13 at 11:35
  • $\begingroup$ "For 2-digit numbers and for long sequences (>8) my algorithm takes significant time." Can you explain your algorithm in more detail? How can it takes significant time? A simple program should be able to generate more than ten of thousands of such sequences. $\endgroup$ – Apass.Jack Jun 13 at 11:39
0
$\begingroup$

A simple remedy

The reason why your algorithm produces desired sequences in a very low rate might be that you are generating random numbers that are so large on average that it is not easy for the sum of them to be smaller than the limit 100. A simple remedy is to change line 2) of your pseudocode to

2) generate random number between 1 and 55, let's say rand = 24

Here the upper limit, 55 is a number near 48 = 99//4 *2, where 4 = 5 - 1 is the number of numbers to be generated (it seems you require the first number must be 0) and 99//4 is about the average of each number. Then the algorithm will be much more likely succeed without going back to line 0). It is possible that the upper limit should be slightly bigger than 2 times the average to approximate the maximum rate of production. I profiled a few times so as to determine that 55 is the fastest number. You can experiment to find what is the best limit.

As successive differences

Here is another way to generate the desired sequences with length $m$ and sum less than $n$. It works well if $n$ is not large, in which case it does not take long to complete the sorting step.

  1. Generate $m$ random numbers between 0 inclusive and $n$ exclusive.
  2. Sort them so we obtain $a[0]\le a[1]\le\cdots\le a[m-1]$.
  3. Return sequence $b[0], b[1], \cdots, b[m-1]$, where $b[0]=a[0]$ and $b[i]=b[i]-a[i-1]$ for all $i\gt1$.

Scaling technique, the fastest way

  1. Generate m random numbers between 0 inclusive and 1, a[0], a[1], ..., a[m-1].
  2. Let s be the sum of them. Compute the scaling factor f = u/s, where u is the given upper limit of the sum.
  3. Let b[i] be a[i] multiplied by f, chopping off the fraction part.
  4. Return sequence b[0], b[1], ..., b[m-1].

You can also try generating m + k of them, following by the same scaling step, but returning only the first m numbers. You can either fix k or even let k be random.


Note that different algorithms generate sequences with different "randomness", which may or may not be significant for your purpose.


You can search for how to generate random sequences with given sum for more methods. If you prefer sum to be less than a given limit, just generate a longer sequence with a sum that is bigger than the given limit. Then take the first m numbers.

$\endgroup$
  • $\begingroup$ I've followed your suggestion and now I generate digits of number seperately. Thank you! $\endgroup$ – microspace Jun 19 at 8:01
0
$\begingroup$
-- generate ALL sequences of n natural numbers with given sum
-- should be called with n<=sum
gen(n,sum):
  for i in 1..sum-n+1:
    -- next number in sequence is i
    gen(n-1,sum-i)  -- generate ALL possible sequences of remaining numbers
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.