How many different ways do we have to group them? [duplicate]
This question already has an answer here:
Partition of an Integer + Number of partitions
3 answers
I want to group them in all possible ways.
For example: If we have 5 stones, we will have 7 different ways to group them.
X X X X X
XX X X X
XXX X X
XXX XX
XX XX X
XXXX X
XXXXX
I've been trying to get the algorithm out all day but I can not get it, do you have any idea how to do this?
Thanks
algorithm math
asked Nov 17 '18 at 19:41
Akai shurAkai shur
6910
marked as duplicate by Rory Daulton, James K Polk, Mark Dickinson, Community♦ Nov 17 '18 at 23:10
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
This question already has an answer here:
Partition of an Integer + Number of partitions
3 answers
I want to group them in all possible ways.
For example: If we have 5 stones, we will have 7 different ways to group them.
X X X X X
XX X X X
XXX X X
XXX XX
XX XX X
XXXX X
XXXXX
I've been trying to get the algorithm out all day but I can not get it, do you have any idea how to do this?
Thanks
algorithm math
asked Nov 17 '18 at 19:41
Akai shurAkai shur
6910
marked as duplicate by Rory Daulton, James K Polk, Mark Dickinson, Community♦ Nov 17 '18 at 23:10
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
Can you show some attempts and what was not working with these?
– Willem Van Onsem
Nov 17 '18 at 19:43
1
You can here use a form of dynamic programming for this.
– Willem Van Onsem
Nov 17 '18 at 19:43
This question has been asked here many times before, usually in a different context. Look at this web site for more on this topic of partitions.
– Rory Daulton
Nov 17 '18 at 20:03
Yes, I currently have a formula that works for me in some cases but not very large numbers. The formula that I am implementing recursively is import math n = 10 p = [0,1,2] for i in range (3, n + 1): p.append ((sum (p) + 1-2) / 2 + 2) print (p) The idea is to add the previous possibilities and add the current one.
– Akai shur
Nov 17 '18 at 20:04
add a comment |
This question already has an answer here:
Partition of an Integer + Number of partitions
3 answers
I want to group them in all possible ways.
For example: If we have 5 stones, we will have 7 different ways to group them.
X X X X X
XX X X X
XXX X X
XXX XX
XX XX X
XXXX X
XXXXX
I've been trying to get the algorithm out all day but I can not get it, do you have any idea how to do this?
Thanks
algorithm math
asked Nov 17 '18 at 19:41
Akai shurAkai shur
6910
This question already has an answer here:
Partition of an Integer + Number of partitions
3 answers
I want to group them in all possible ways.
For example: If we have 5 stones, we will have 7 different ways to group them.
X X X X X
XX X X X
XXX X X
XXX XX
XX XX X
XXXX X
XXXXX
I've been trying to get the algorithm out all day but I can not get it, do you have any idea how to do this?
Thanks
This question already has an answer here:
Partition of an Integer + Number of partitions
3 answers
algorithm math
algorithm math
asked Nov 17 '18 at 19:41
Akai shurAkai shur
6910
asked Nov 17 '18 at 19:41
Akai shurAkai shur
6910
asked Nov 17 '18 at 19:41
Akai shurAkai shur
6910
asked Nov 17 '18 at 19:41
Akai shurAkai shur
6910
asked Nov 17 '18 at 19:41
Akai shurAkai shur
6910
6910
marked as duplicate by Rory Daulton, James K Polk, Mark Dickinson, Community♦ Nov 17 '18 at 23:10
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Rory Daulton, James K Polk, Mark Dickinson, Community♦ Nov 17 '18 at 23:10
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
Can you show some attempts and what was not working with these?
– Willem Van Onsem
Nov 17 '18 at 19:43
1
You can here use a form of dynamic programming for this.
– Willem Van Onsem
Nov 17 '18 at 19:43
This question has been asked here many times before, usually in a different context. Look at this web site for more on this topic of partitions.
– Rory Daulton
Nov 17 '18 at 20:03
Yes, I currently have a formula that works for me in some cases but not very large numbers. The formula that I am implementing recursively is import math n = 10 p = [0,1,2] for i in range (3, n + 1): p.append ((sum (p) + 1-2) / 2 + 2) print (p) The idea is to add the previous possibilities and add the current one.
– Akai shur
Nov 17 '18 at 20:04
add a comment |
Can you show some attempts and what was not working with these?
– Willem Van Onsem
Nov 17 '18 at 19:43
1
You can here use a form of dynamic programming for this.
– Willem Van Onsem
Nov 17 '18 at 19:43
This question has been asked here many times before, usually in a different context. Look at this web site for more on this topic of partitions.
– Rory Daulton
Nov 17 '18 at 20:03
Yes, I currently have a formula that works for me in some cases but not very large numbers. The formula that I am implementing recursively is import math n = 10 p = [0,1,2] for i in range (3, n + 1): p.append ((sum (p) + 1-2) / 2 + 2) print (p) The idea is to add the previous possibilities and add the current one.
– Akai shur
Nov 17 '18 at 20:04
Can you show some attempts and what was not working with these?
– Willem Van Onsem
Nov 17 '18 at 19:43
Can you show some attempts and what was not working with these?
– Willem Van Onsem
Nov 17 '18 at 19:43
1
1
You can here use a form of dynamic programming for this.
– Willem Van Onsem
Nov 17 '18 at 19:43
You can here use a form of dynamic programming for this.
– Willem Van Onsem
Nov 17 '18 at 19:43
This question has been asked here many times before, usually in a different context. Look at this web site for more on this topic of partitions.
– Rory Daulton
Nov 17 '18 at 20:03
This question has been asked here many times before, usually in a different context. Look at this web site for more on this topic of partitions.
– Rory Daulton
Nov 17 '18 at 20:03
Yes, I currently have a formula that works for me in some cases but not very large numbers. The formula that I am implementing recursively is import math n = 10 p = [0,1,2] for i in range (3, n + 1): p.append ((sum (p) + 1-2) / 2 + 2) print (p) The idea is to add the previous possibilities and add the current one.
– Akai shur
Nov 17 '18 at 20:04
Yes, I currently have a formula that works for me in some cases but not very large numbers. The formula that I am implementing recursively is import math n = 10 p = [0,1,2] for i in range (3, n + 1): p.append ((sum (p) + 1-2) / 2 + 2) print (p) The idea is to add the previous possibilities and add the current one.
– Akai shur
Nov 17 '18 at 20:04
add a comment |
1 Answer
1
active
oldest
votes
This is equivalent to finding integer partitions of the number of stones you have. For example:
5 = 1 + 1 + 1 + 1 + 1 --> X X X X X
5 = 2 + 1 + 1 + 1 --> XX X X X
5 = 3 + 1 + 1 --> XXX X X
5 = 2 + 2 + 1 --> XX XX X
5 = 4 + 1 --> XXXX X
5 = 3 + 2 --> XXX XX
5 = 5 --> XXXXX
Each line encodes a possible group configuration, where each integer on the right hand side represents the number of stones in a group.
answered Nov 17 '18 at 20:05
arshajiiarshajii
101k18182250
Or the stars and bars problem: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
– slider
Nov 17 '18 at 20:07
1
@slider They're slightly different: in this case we're distributing identical objects into identical bins, whereas stars+bars is distinct bins.
– arshajii
Nov 17 '18 at 20:08
Agreed. Although you just need to account for the permutations of the bins.
– slider
Nov 17 '18 at 20:12
@slider: "just need to account" there is what we use to call "hand-waving". It's not nearly so simple.
– rici
Nov 18 '18 at 2:17
@rici "It's obvious". Ok I may have slightly underestimated the difficulty.
– slider
Nov 18 '18 at 3:23
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
This is equivalent to finding integer partitions of the number of stones you have. For example:
5 = 1 + 1 + 1 + 1 + 1 --> X X X X X
5 = 2 + 1 + 1 + 1 --> XX X X X
5 = 3 + 1 + 1 --> XXX X X
5 = 2 + 2 + 1 --> XX XX X
5 = 4 + 1 --> XXXX X
5 = 3 + 2 --> XXX XX
5 = 5 --> XXXXX
Each line encodes a possible group configuration, where each integer on the right hand side represents the number of stones in a group.
answered Nov 17 '18 at 20:05
arshajiiarshajii
101k18182250
Or the stars and bars problem: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
– slider
Nov 17 '18 at 20:07
1
@slider They're slightly different: in this case we're distributing identical objects into identical bins, whereas stars+bars is distinct bins.
– arshajii
Nov 17 '18 at 20:08
Agreed. Although you just need to account for the permutations of the bins.
– slider
Nov 17 '18 at 20:12
@slider: "just need to account" there is what we use to call "hand-waving". It's not nearly so simple.
– rici
Nov 18 '18 at 2:17
@rici "It's obvious". Ok I may have slightly underestimated the difficulty.
– slider
Nov 18 '18 at 3:23
add a comment |
This is equivalent to finding integer partitions of the number of stones you have. For example:
5 = 1 + 1 + 1 + 1 + 1 --> X X X X X
5 = 2 + 1 + 1 + 1 --> XX X X X
5 = 3 + 1 + 1 --> XXX X X
5 = 2 + 2 + 1 --> XX XX X
5 = 4 + 1 --> XXXX X
5 = 3 + 2 --> XXX XX
5 = 5 --> XXXXX
Each line encodes a possible group configuration, where each integer on the right hand side represents the number of stones in a group.
answered Nov 17 '18 at 20:05
arshajiiarshajii
101k18182250
Or the stars and bars problem: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
– slider
Nov 17 '18 at 20:07
1
@slider They're slightly different: in this case we're distributing identical objects into identical bins, whereas stars+bars is distinct bins.
– arshajii
Nov 17 '18 at 20:08
Agreed. Although you just need to account for the permutations of the bins.
– slider
Nov 17 '18 at 20:12
@slider: "just need to account" there is what we use to call "hand-waving". It's not nearly so simple.
– rici
Nov 18 '18 at 2:17
@rici "It's obvious". Ok I may have slightly underestimated the difficulty.
– slider
Nov 18 '18 at 3:23
add a comment |
This is equivalent to finding integer partitions of the number of stones you have. For example:
5 = 1 + 1 + 1 + 1 + 1 --> X X X X X
5 = 2 + 1 + 1 + 1 --> XX X X X
5 = 3 + 1 + 1 --> XXX X X
5 = 2 + 2 + 1 --> XX XX X
5 = 4 + 1 --> XXXX X
5 = 3 + 2 --> XXX XX
5 = 5 --> XXXXX
Each line encodes a possible group configuration, where each integer on the right hand side represents the number of stones in a group.
answered Nov 17 '18 at 20:05
arshajiiarshajii
101k18182250
This is equivalent to finding integer partitions of the number of stones you have. For example:
5 = 1 + 1 + 1 + 1 + 1 --> X X X X X
5 = 2 + 1 + 1 + 1 --> XX X X X
5 = 3 + 1 + 1 --> XXX X X
5 = 2 + 2 + 1 --> XX XX X
5 = 4 + 1 --> XXXX X
5 = 3 + 2 --> XXX XX
5 = 5 --> XXXXX
Each line encodes a possible group configuration, where each integer on the right hand side represents the number of stones in a group.
answered Nov 17 '18 at 20:05
arshajiiarshajii
101k18182250
answered Nov 17 '18 at 20:05
arshajiiarshajii
101k18182250
answered Nov 17 '18 at 20:05
arshajiiarshajii
101k18182250
answered Nov 17 '18 at 20:05
arshajiiarshajii
101k18182250
101k18182250
Or the stars and bars problem: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
– slider
Nov 17 '18 at 20:07
1
@slider They're slightly different: in this case we're distributing identical objects into identical bins, whereas stars+bars is distinct bins.
– arshajii
Nov 17 '18 at 20:08
Agreed. Although you just need to account for the permutations of the bins.
– slider
Nov 17 '18 at 20:12
@slider: "just need to account" there is what we use to call "hand-waving". It's not nearly so simple.
– rici
Nov 18 '18 at 2:17
@rici "It's obvious". Ok I may have slightly underestimated the difficulty.
– slider
Nov 18 '18 at 3:23
add a comment |
Or the stars and bars problem: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
– slider
Nov 17 '18 at 20:07
1
@slider They're slightly different: in this case we're distributing identical objects into identical bins, whereas stars+bars is distinct bins.
– arshajii
Nov 17 '18 at 20:08
Agreed. Although you just need to account for the permutations of the bins.
– slider
Nov 17 '18 at 20:12
@slider: "just need to account" there is what we use to call "hand-waving". It's not nearly so simple.
– rici
Nov 18 '18 at 2:17
@rici "It's obvious". Ok I may have slightly underestimated the difficulty.
– slider
Nov 18 '18 at 3:23
Or the stars and bars problem: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
– slider
Nov 17 '18 at 20:07
Or the stars and bars problem: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
– slider
Nov 17 '18 at 20:07
1
1
@slider They're slightly different: in this case we're distributing identical objects into identical bins, whereas stars+bars is distinct bins.
– arshajii
Nov 17 '18 at 20:08
@slider They're slightly different: in this case we're distributing identical objects into identical bins, whereas stars+bars is distinct bins.
– arshajii
Nov 17 '18 at 20:08
Agreed. Although you just need to account for the permutations of the bins.
– slider
Nov 17 '18 at 20:12
Agreed. Although you just need to account for the permutations of the bins.
– slider
Nov 17 '18 at 20:12
@slider: "just need to account" there is what we use to call "hand-waving". It's not nearly so simple.
– rici
Nov 18 '18 at 2:17
@slider: "just need to account" there is what we use to call "hand-waving". It's not nearly so simple.
– rici
Nov 18 '18 at 2:17
@rici "It's obvious". Ok I may have slightly underestimated the difficulty.
– slider
Nov 18 '18 at 3:23
@rici "It's obvious". Ok I may have slightly underestimated the difficulty.
– slider
Nov 18 '18 at 3:23
add a comment |
Can you show some attempts and what was not working with these?
– Willem Van Onsem
Nov 17 '18 at 19:43
1
You can here use a form of dynamic programming for this.
– Willem Van Onsem
Nov 17 '18 at 19:43
This question has been asked here many times before, usually in a different context. Look at this web site for more on this topic of partitions.
– Rory Daulton
Nov 17 '18 at 20:03
Yes, I currently have a formula that works for me in some cases but not very large numbers. The formula that I am implementing recursively is import math n = 10 p = [0,1,2] for i in range (3, n + 1): p.append ((sum (p) + 1-2) / 2 + 2) print (p) The idea is to add the previous possibilities and add the current one.
– Akai shur
Nov 17 '18 at 20:04