Generate random numbers that sum up to n

up vote
4
down vote

favorite

How to generate between 1 and n random numbers (positive integers greater than 0) which sum up to exactly n?

Example results if n=10:

10

2,5,3

1,1,1,1,1,1,1,1,1,1

1,1,5,1,1,1

Each of the permutations should have the same probability of occurring, however, I don't need it to be mathematically precise. So if the probabilities are not the same due to some modulo error, I don't care.

Is there a go-to algorithm for this? I only found algorithms where the number of values is fixed (i.e., give me exactly m random numbers which sum up to n).

edited Nov 16 at 13:55

asked Nov 15 at 20:08

D.R.

9,1631348115

1

@ceejayoz: I thought of this algorithm too, however, it looks like it's way off the "same probability for each permutation", isn't it? There are easily more than 10 permutations, but "10" has a probability of 1/10th. (I know, I said it doesn't have to be mathematically precise, but it shouldn't be way off)
– D.R.
Nov 15 at 20:16

1

Just to clarify - you say "numbers" but your examples are all integer. Are you excluding floating point solutions? Are negative values allowed? How about zeros?
– pjs
Nov 15 at 20:34

2

I'm unsure why people are close-voting the question as "too broad", how can I improve the question? Please leave a comment, thank you!
– D.R.
Nov 16 at 10:51

1

No attempt and no tag to indicate what language you're writing this in. To me, this looks more like a Mathematics question than a programming one.
– Toby Speight
Nov 16 at 11:24

1

@TobySpeight: In the end I want to have C# code, but I've omitted the C# tag as I'm interested in the algorithm and not a specific implementation. Are algorithm questions not part of StackOverflow? As for the attempt, if I can't find an approach myself, I'm not entitled to post here?
– D.R.
Nov 16 at 11:26

|
show 6 more comments

up vote
4
down vote

favorite

How to generate between 1 and n random numbers (positive integers greater than 0) which sum up to exactly n?

Example results if n=10:

10

2,5,3

1,1,1,1,1,1,1,1,1,1

1,1,5,1,1,1

Is there a go-to algorithm for this? I only found algorithms where the number of values is fixed (i.e., give me exactly m random numbers which sum up to n).

edited Nov 16 at 13:55

asked Nov 15 at 20:08

D.R.

9,1631348115

1

@ceejayoz: I thought of this algorithm too, however, it looks like it's way off the "same probability for each permutation", isn't it? There are easily more than 10 permutations, but "10" has a probability of 1/10th. (I know, I said it doesn't have to be mathematically precise, but it shouldn't be way off)
– D.R.
Nov 15 at 20:16

1

Just to clarify - you say "numbers" but your examples are all integer. Are you excluding floating point solutions? Are negative values allowed? How about zeros?
– pjs
Nov 15 at 20:34

2

I'm unsure why people are close-voting the question as "too broad", how can I improve the question? Please leave a comment, thank you!
– D.R.
Nov 16 at 10:51

1

No attempt and no tag to indicate what language you're writing this in. To me, this looks more like a Mathematics question than a programming one.
– Toby Speight
Nov 16 at 11:24

1

@TobySpeight: In the end I want to have C# code, but I've omitted the C# tag as I'm interested in the algorithm and not a specific implementation. Are algorithm questions not part of StackOverflow? As for the attempt, if I can't find an approach myself, I'm not entitled to post here?
– D.R.
Nov 16 at 11:26

|
show 6 more comments

up vote
4
down vote

favorite

How to generate between 1 and n random numbers (positive integers greater than 0) which sum up to exactly n?

Example results if n=10:

10

2,5,3

1,1,1,1,1,1,1,1,1,1

1,1,5,1,1,1

Is there a go-to algorithm for this? I only found algorithms where the number of values is fixed (i.e., give me exactly m random numbers which sum up to n).

edited Nov 16 at 13:55

asked Nov 15 at 20:08

D.R.

9,1631348115

How to generate between 1 and n random numbers (positive integers greater than 0) which sum up to exactly n?

Example results if n=10:

10

2,5,3

1,1,1,1,1,1,1,1,1,1

1,1,5,1,1,1

Is there a go-to algorithm for this? I only found algorithms where the number of values is fixed (i.e., give me exactly m random numbers which sum up to n).

algorithm random

edited Nov 16 at 13:55

asked Nov 15 at 20:08

D.R.

9,1631348115

edited Nov 16 at 13:55

asked Nov 15 at 20:08

D.R.

9,1631348115

edited Nov 16 at 13:55

asked Nov 15 at 20:08

D.R.

9,1631348115

asked Nov 15 at 20:08

D.R.

9,1631348115

asked Nov 15 at 20:08

D.R.

9,1631348115

1

@ceejayoz: I thought of this algorithm too, however, it looks like it's way off the "same probability for each permutation", isn't it? There are easily more than 10 permutations, but "10" has a probability of 1/10th. (I know, I said it doesn't have to be mathematically precise, but it shouldn't be way off)
– D.R.
Nov 15 at 20:16

1

Just to clarify - you say "numbers" but your examples are all integer. Are you excluding floating point solutions? Are negative values allowed? How about zeros?
– pjs
Nov 15 at 20:34

2

I'm unsure why people are close-voting the question as "too broad", how can I improve the question? Please leave a comment, thank you!
– D.R.
Nov 16 at 10:51

1

No attempt and no tag to indicate what language you're writing this in. To me, this looks more like a Mathematics question than a programming one.
– Toby Speight
Nov 16 at 11:24

1

@TobySpeight: In the end I want to have C# code, but I've omitted the C# tag as I'm interested in the algorithm and not a specific implementation. Are algorithm questions not part of StackOverflow? As for the attempt, if I can't find an approach myself, I'm not entitled to post here?
– D.R.
Nov 16 at 11:26

|
show 6 more comments

1

@ceejayoz: I thought of this algorithm too, however, it looks like it's way off the "same probability for each permutation", isn't it? There are easily more than 10 permutations, but "10" has a probability of 1/10th. (I know, I said it doesn't have to be mathematically precise, but it shouldn't be way off)
– D.R.
Nov 15 at 20:16

1

Just to clarify - you say "numbers" but your examples are all integer. Are you excluding floating point solutions? Are negative values allowed? How about zeros?
– pjs
Nov 15 at 20:34

2

I'm unsure why people are close-voting the question as "too broad", how can I improve the question? Please leave a comment, thank you!
– D.R.
Nov 16 at 10:51

1

No attempt and no tag to indicate what language you're writing this in. To me, this looks more like a Mathematics question than a programming one.
– Toby Speight
Nov 16 at 11:24

1

@TobySpeight: In the end I want to have C# code, but I've omitted the C# tag as I'm interested in the algorithm and not a specific implementation. Are algorithm questions not part of StackOverflow? As for the attempt, if I can't find an approach myself, I'm not entitled to post here?
– D.R.
Nov 16 at 11:26

@ceejayoz: I thought of this algorithm too, however, it looks like it's way off the "same probability for each permutation", isn't it? There are easily more than 10 permutations, but "10" has a probability of 1/10th. (I know, I said it doesn't have to be mathematically precise, but it shouldn't be way off)
– D.R.
Nov 15 at 20:16

Just to clarify - you say "numbers" but your examples are all integer. Are you excluding floating point solutions? Are negative values allowed? How about zeros?
– pjs
Nov 15 at 20:34

I'm unsure why people are close-voting the question as "too broad", how can I improve the question? Please leave a comment, thank you!
– D.R.
Nov 16 at 10:51

No attempt and no tag to indicate what language you're writing this in. To me, this looks more like a Mathematics question than a programming one.
– Toby Speight
Nov 16 at 11:24

@TobySpeight: In the end I want to have C# code, but I've omitted the C# tag as I'm interested in the algorithm and not a specific implementation. Are algorithm questions not part of StackOverflow? As for the attempt, if I can't find an approach myself, I'm not entitled to post here?
– D.R.
Nov 16 at 11:26

|
show 6 more comments

2 Answers
2

active

oldest

votes

up vote
7
down vote

accepted

Imagine the number n as a line built of n equal, indivisible sections. Your numbers are lengths of those sections that sum up to the whole. You can cut the original length between any two sections, or none.

This means there are n-1 potential cut points.

Choose a random n-1-bit number, that is a number between 0 and 2^(n-1); its binary representation tells you where to cut.

0 : 000 : [-|-|-|-] : 1,1,1,1

1 : 001 : [-|-|- -] :  1,1,2

3 : 011 : [-|- - -] :   1,3

5 : 101 : [- -|- -] :   2,2

7 : 111 : [- - - -] :    4

etc.

Implementation in 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))

you can verify it by generating all possible solutions for small n

test(4)

output:

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]

edited Nov 16 at 15:08

Toby Speight

16.2k133965

answered Nov 15 at 21:38

Milo Bem

792418

1

Thanks for adding the explanation - that's a really good answer now. And we don't need to generate all n bits of the decision tree at once - if we have a source of random bits, we can just take them as we need them. That can avoid the overhead of huge arithmetic numbers which we won't be using for arithmetic.
– Toby Speight
Nov 16 at 15:10

1

I love the way you have solved it and I really like how you illustrated the example.
– maytham-ɯɐɥʇʎɐɯ
Nov 16 at 15:16

add a comment |

up vote
0
down vote

Use a modulo.

This should make your day:

#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");

}

Example output:

answered Nov 15 at 20:50

user803422

8872623

1

This seems biased towards the shorter sequences; only one of the example outputs begins with 1, but we'd expect about half of them to begin with 1 if it selected fairly from all possibilities.
– Toby Speight
Nov 16 at 15:14

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53327177%2fgenerate-random-numbers-that-sum-up-to-n%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

up vote
7
down vote

accepted

This means there are n-1 potential cut points.

Choose a random n-1-bit number, that is a number between 0 and 2^(n-1); its binary representation tells you where to cut.

0 : 000 : [-|-|-|-] : 1,1,1,1

1 : 001 : [-|-|- -] :  1,1,2

3 : 011 : [-|- - -] :   1,3

5 : 101 : [- -|- -] :   2,2

7 : 111 : [- - - -] :    4

etc.

Implementation in 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))

you can verify it by generating all possible solutions for small n

test(4)

output:

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]

edited Nov 16 at 15:08

Toby Speight

16.2k133965

answered Nov 15 at 21:38

Milo Bem

792418

1

Thanks for adding the explanation - that's a really good answer now. And we don't need to generate all n bits of the decision tree at once - if we have a source of random bits, we can just take them as we need them. That can avoid the overhead of huge arithmetic numbers which we won't be using for arithmetic.
– Toby Speight
Nov 16 at 15:10

1

I love the way you have solved it and I really like how you illustrated the example.
– maytham-ɯɐɥʇʎɐɯ
Nov 16 at 15:16

add a comment |

up vote
7
down vote

accepted

This means there are n-1 potential cut points.

Choose a random n-1-bit number, that is a number between 0 and 2^(n-1); its binary representation tells you where to cut.

0 : 000 : [-|-|-|-] : 1,1,1,1

1 : 001 : [-|-|- -] :  1,1,2

3 : 011 : [-|- - -] :   1,3

5 : 101 : [- -|- -] :   2,2

7 : 111 : [- - - -] :    4

etc.

Implementation in 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))

you can verify it by generating all possible solutions for small n

test(4)

output:

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]

edited Nov 16 at 15:08

Toby Speight

16.2k133965

answered Nov 15 at 21:38

Milo Bem

792418

1

Thanks for adding the explanation - that's a really good answer now. And we don't need to generate all n bits of the decision tree at once - if we have a source of random bits, we can just take them as we need them. That can avoid the overhead of huge arithmetic numbers which we won't be using for arithmetic.
– Toby Speight
Nov 16 at 15:10

1

I love the way you have solved it and I really like how you illustrated the example.
– maytham-ɯɐɥʇʎɐɯ
Nov 16 at 15:16

add a comment |

up vote
7
down vote

accepted

This means there are n-1 potential cut points.

Choose a random n-1-bit number, that is a number between 0 and 2^(n-1); its binary representation tells you where to cut.

0 : 000 : [-|-|-|-] : 1,1,1,1

1 : 001 : [-|-|- -] :  1,1,2

3 : 011 : [-|- - -] :   1,3

5 : 101 : [- -|- -] :   2,2

7 : 111 : [- - - -] :    4

etc.

Implementation in 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))

you can verify it by generating all possible solutions for small n

test(4)

output:

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]

edited Nov 16 at 15:08

Toby Speight

16.2k133965

answered Nov 15 at 21:38

Milo Bem

792418

This means there are n-1 potential cut points.

Choose a random n-1-bit number, that is a number between 0 and 2^(n-1); its binary representation tells you where to cut.

0 : 000 : [-|-|-|-] : 1,1,1,1

1 : 001 : [-|-|- -] :  1,1,2

3 : 011 : [-|- - -] :   1,3

5 : 101 : [- -|- -] :   2,2

7 : 111 : [- - - -] :    4

etc.

Implementation in 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))

you can verify it by generating all possible solutions for small n

test(4)

output:

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]

edited Nov 16 at 15:08

Toby Speight

16.2k133965

answered Nov 15 at 21:38

Milo Bem

792418

edited Nov 16 at 15:08

Toby Speight

16.2k133965

edited Nov 16 at 15:08

Toby Speight

16.2k133965

edited Nov 16 at 15:08

Toby Speight

16.2k133965

answered Nov 15 at 21:38

Milo Bem

792418

answered Nov 15 at 21:38

Milo Bem

792418

answered Nov 15 at 21:38

Milo Bem

792418

1

Thanks for adding the explanation - that's a really good answer now. And we don't need to generate all n bits of the decision tree at once - if we have a source of random bits, we can just take them as we need them. That can avoid the overhead of huge arithmetic numbers which we won't be using for arithmetic.
– Toby Speight
Nov 16 at 15:10

1

I love the way you have solved it and I really like how you illustrated the example.
– maytham-ɯɐɥʇʎɐɯ
Nov 16 at 15:16

add a comment |

1

Thanks for adding the explanation - that's a really good answer now. And we don't need to generate all n bits of the decision tree at once - if we have a source of random bits, we can just take them as we need them. That can avoid the overhead of huge arithmetic numbers which we won't be using for arithmetic.
– Toby Speight
Nov 16 at 15:10

1

I love the way you have solved it and I really like how you illustrated the example.
– maytham-ɯɐɥʇʎɐɯ
Nov 16 at 15:16

Thanks for adding the explanation - that's a really good answer now. And we don't need to generate all n bits of the decision tree at once - if we have a source of random bits, we can just take them as we need them. That can avoid the overhead of huge arithmetic numbers which we won't be using for arithmetic.
– Toby Speight
Nov 16 at 15:10

I love the way you have solved it and I really like how you illustrated the example.
– maytham-ɯɐɥʇʎɐɯ
Nov 16 at 15:16

add a comment |

up vote
0
down vote

Use a modulo.

This should make your day:

#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");

}

Example output:

answered Nov 15 at 20:50

user803422

8872623

1

This seems biased towards the shorter sequences; only one of the example outputs begins with 1, but we'd expect about half of them to begin with 1 if it selected fairly from all possibilities.
– Toby Speight
Nov 16 at 15:14

add a comment |

up vote
0
down vote

Use a modulo.

This should make your day:

#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");

}

Example output:

answered Nov 15 at 20:50

user803422

8872623

1

This seems biased towards the shorter sequences; only one of the example outputs begins with 1, but we'd expect about half of them to begin with 1 if it selected fairly from all possibilities.
– Toby Speight
Nov 16 at 15:14

add a comment |

up vote
0
down vote

Use a modulo.

This should make your day:

#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");

}

Example output:

answered Nov 15 at 20:50

user803422

8872623

Use a modulo.

This should make your day:

#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");

}

Example output:

answered Nov 15 at 20:50

user803422

8872623

answered Nov 15 at 20:50

user803422

8872623

answered Nov 15 at 20:50

user803422

8872623

answered Nov 15 at 20:50

user803422

8872623

1

This seems biased towards the shorter sequences; only one of the example outputs begins with 1, but we'd expect about half of them to begin with 1 if it selected fairly from all possibilities.
– Toby Speight
Nov 16 at 15:14

add a comment |

1

This seems biased towards the shorter sequences; only one of the example outputs begins with 1, but we'd expect about half of them to begin with 1 if it selected fairly from all possibilities.
– Toby Speight
Nov 16 at 15:14

This seems biased towards the shorter sequences; only one of the example outputs begins with 1, but we'd expect about half of them to begin with 1 if it selected fairly from all possibilities.
– Toby Speight
Nov 16 at 15:14

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Cfrgtkky