生成总和为n的随机数

想象一下这个数字 n 作为一条由n个相等的、不可分割的部分组成的线。你的数字是那些部分的长度,这些部分的总和是整体的。可以在任意两个部分之间剪切原始长度,也可以不剪切。

这意味着 N-1 潜在的切入点。

随机选择 N-1 -位号,即介于 零 和 2 ^(n-1) ;它的二进制表示告诉您在哪里剪切。

0 : 000 : [-|-|-|-] : 1,1,1,1
1 : 001 : [-|-|- -] :  1,1,2
3 : 011 : [-|- - -] :   1,3
5 : 101 : [- -|- -] :   2,2
7 : 111 : [- - - -] :    4

等。

在python-3中实现

import random


def perm(n, np):
    p = []
    d = 1
    for i in range(n):
        if np % 2 == 0:
            p.append(d)
            d = 1
        else:
            d += 1
        np //= 2
    return p


def test(ex_n):
    for ex_p in range(2 ** (ex_n - 1)):
        p = perm(ex_n, ex_p)
        print(len(p), p)


def randperm(n):
    np = random.randint(0, 2 ** (n - 1))
    return perm(n, np)

print(randperm(10))

您可以通过为small生成所有可能的解决方案来验证它。 n

test(4)

输出:

4 [1, 1, 1, 1]
3 [2, 1, 1]
3 [1, 2, 1]
2 [3, 1]
3 [1, 1, 2]
2 [2, 2]
2 [1, 3]
1 [4]

使用模件。

这将使您的一天:

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

int main()
{
    srand(time(0));
    int n=10;
    int x=0; /* sum of previous random number */
    while (x<n) {
                int r = rand() % (n-x) + 1;
                printf("%d ", r);
                x += r;
    }
    /* done */
    printf("\n");
}

实例输出:

10
1 1 8 
3 4 1 1 1 
6 3 1 
9 1 
6 1 1 1 1 
5 4 1