CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about |Store| Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Is this Permutations?"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange Guest book Topic #267
Reading Topic #267
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

  Subject     Author     Message Date     ID  
  RE: Is this Permutations? RicBrad Jul-07-03 1
  RE: Are these Permutations? Vladimir Jul-07-03 2
     RE: Are these Permutations? Michael Klipper Jul-09-03 3
         RE: Are these Permutations? Vladimir Jul-09-03 4
             RE: Are these Permutations? J Jim Jul-14-03 7
         RE: Are these Permutations? Vladimir Jul-11-03 6
             RE: Are these Permutations? Michael Klipper Jul-14-03 8
                 RE: Are these Permutations? Vladimir Jul-16-03 9
  RE: Is this Permutations? Marcus Jul-10-03 5
  RE: Is this Permutations? Paul Sep-14-03 10

Conferences | Forums | Topics | Previous Topic | Next Topic
RicBrad
Member since Nov-16-01
Jul-07-03, 11:31 PM (EST)
Click to EMail RicBrad Click to send private message to RicBrad Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail Vladimir Click to send private message to Vladimir Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail Vladimir Click to send private message to Vladimir Click to view user profileClick to add this user to your buddy list  
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
Vladimir
Member since Jun-22-03
Jul-11-03, 03:45 PM (EST)
Click to EMail Vladimir Click to send private message to Vladimir Click to view user profileClick to add this user to your buddy list  
6. "RE: Are these Permutations?"
In response to message #3
 
   I apologize for giving the conversion example to a math teacher. Did not realize I was no longer replying to Jim.


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
Michael Klipper
guest
Jul-14-03, 06:26 PM (EST)
 
8. "RE: Are these Permutations?"
In response to message #6
 
  

You think I'm a math teacher? I'm flattered, but I'm only a junior in college. Unless you were referring to someone else...


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
Vladimir
Member since Jun-22-03
Jul-16-03, 03:09 PM (EST)
Click to EMail Vladimir Click to send private message to Vladimir Click to view user profileClick to add this user to your buddy list  
9. "RE: Are these Permutations?"
In response to message #8
 
   I got such a strong impression that you were a math teacher from your reply to the topic "false proofs" in the "This and that" conference that I tought you actually said it. But you did not say anything like it. Therefore, my impression was not necessarily correct.


  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

Conferences | Forums | Topics | Previous Topic | Next Topic

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]