|
|
|Store|
|
|
|
|
|
|
|
|
CTK Exchange
J Jim
guest
|
Jul-07-03, 11:30 AM (EST) |
|
"Is this Permutations?"
|
Hi all, Wanted to find out is this is Permutations? I have 5 Dice (Die) and I want to print out all possible combinations / Permutations for the 5 Dice and their total. i.e. 1 2 3 4 5 sum= 15 6 6 6 6 6 sum= 30 Anybody know how I can do this? Many thanks, Jim |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
RicBrad
Member since Nov-16-01
|
Jul-07-03, 11:31 PM (EST) |
|
1. "RE: Is this Permutations?"
In response to message #0
|
>is this Permutations? If you include order, then this is sort of a permutation problem, but you have to choose values for the dice as well as order them, so its more than that. >I have 5 Dice (Die) Dice: die is singular (think of mice=plural) >and I want to print out all possible >combinations / Permutations for the 5 Dice and their total. Ouch. There are 6^5 = 7776 outcomes (including order) i hope you have a lot of paper. >Anybody know how I can do this? You should be able to write (or get someone nice to write) a simple program to do this. However you should probably take another look at what you are trying to achieve and take a different approach. All the best, Rich |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
Vladimir
Member since Jun-22-03
|
Jul-07-03, 11:31 PM (EST) |
|
2. "RE: Are these Permutations?"
In response to message #0
|
LAST EDITED ON Sep-15-03 AT 08:35 AM (EST) Suppose you have a set of n-elements (these are the 6 different numbers on your die) and you want to pick k-elements from this set (you pick 5 numbers by rolling 5 dice). In how many way this can be done? First, you have to decide if the order in which you pick the elements matters to you. If yes, the choices are called variations, if not, they are called combinations. Second, you have to decide if each element can appear in a particular choice multiple times. If yes, the variations or combinations are with repetition (this is always said), if no, they are without repetition (this is often assumed). Variations (without repetition): n!/(n-k)! Variations with repetition: nk Combinations (without repetition): n!/k!(n-k)! or (n above k) Combinations with repetition: (n+k-1)!/k!(n+k-1-k)! or (n+k-1 above k) Variations (without repetition) for n=k (i.e., you always pick all elements, without repetition, just the order matters) are called permutations. If you roll the same numbers on some dice and you do not care which particular dice yielded these numbers, for example you consider the following 2 patterns the same: 1 2 3 4 5 <- die 6 2 2 6 2 <- rolled numbers 2 6 6 2 2 <- rolled numbers you have combinations with repetition: 10!/5!/5! = 9/2 = 252 ways If you consider the above 2 patterns different, you have variations with repetition: 65 = 7776 ways (about 130 pages to print!) The number of variations with repetition is very easy to see. Assign to the die numbers 1, 2, 3, 4, 5, 6 the sextal system digits 0, 1, 2, 3, 4, 5 (i.e., subtract 1). The number of variations is the count from 0 to (55555))6 or (100000)6 or 65.
|
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
|
Michael Klipper
guest
|
Jul-09-03, 10:42 AM (EST) |
|
3. "RE: Are these Permutations?"
In response to message #2
|
Ok, I imagine that what is wanted is combinations with repetition. Thus, there are 252 items to print. I think the question that is being asked is more: is there an efficient way to loop through these possibilities? In the case of permutations of a fixed set, I saw an algorithm by Kenneth Rosen in his textbook which starts with the identity permutation and systematically progresses through a sequence of permutations, hitting them all. Is there any such method for this problem? |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
|
|
Vladimir
Member since Jun-22-03
|
Jul-09-03, 09:14 AM (EST) |
|
4. "RE: Are these Permutations?"
In response to message #3
|
LAST EDITED ON Sep-15-03 AT 08:42 AM (EST) One possible algorithm:Go through numbers starting from 0 to 65 - 1 and express them in the sextal system. If necessary, pad these sextal numbers with leading zeros to keep the number of digits equal to 5. For each number, see if the 5 digits (0 to 5) are in increasing order. If yes, add 1 to each sextal digit and print the 5 digits (1 to 6). If no, reject the number. Find the highest digit of the rejected number and make all digits right of the highest digit equal to the highest digit. Continue from this number. If you do it by hand, it goes like this: 11111 11112 11113 11114 11115 11116 11121 (reject) -> 11122 11123 11124 11125 11126 11131 (reject) -> 11133 11134 11135 ... 11166 11211 (reject) -> 11222 11223 11224 11225 11226 11231 (reject) -> 11233 ... 66666 This is much faster than comparing the digit order for all number from 0 up to 65 - 1. At the beginning, you accept almost every number, but as you get closer to the end, you jump over greater and greater intervals of numbers not necessary to process. If you do it on a PC, in case you do not know how to convert a decimal number to the sextal system, here is an example - decimal 4343: 60 = 1 61 = 6 62 = 36 63 = 216 64 = 1296 65 = 7776 > 4343, stop 4343/1296 = 3, remainder 455 455/216 = 2, remainder 23 23/36 = 0, remainder 23 23/6 = 3, remainder 5 5/1 = 5 So (4343)10 in the decimal system is (32035)6 in the sextal system. |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
|
|
J Jim
guest
|
Jul-14-03, 09:55 AM (EST) |
|
7. "RE: Are these Permutations?"
In response to message #4
|
Thanks to all for the valuable input. Much appreciated. I am looking for combinations with repetition. I let you know how my program turns out. It is for the Yahtzee game if any of you know it. Thanks, Jim |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
|
Marcus
guest
|
Jul-10-03, 09:05 PM (EST) |
|
5. "RE: Is this Permutations?"
In response to message #0
|
What about you generate all the number from 00000 to 55555 in base 6, and simply do string operations to increment each digit by 1? Of course it will take a while, since there are over 3000 possibiities If you want the permutations, i.e. ordered possibilities. |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
Paul
guest
|
Sep-14-03, 05:59 AM (EST) |
|
10. "RE: Is this Permutations?"
In response to message #0
|
Try Laying out all Die in a continuous counting order. Exp: 11111 21111 22111 22211 22221 22222 12311 12312 And etc. I know it is monotonous, but the outcome will allow you to add the complete sum. |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
You may be curious to visit the old Guest book. Please do not post there.
|Front page|
|Contents|
|Store|
Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
|
|
|