Generating Permutations With a ComputerDate: 06/20/2002 at 12:46:34 From: Fred Gonzaga Subject: Statistics (Permutation or Combinations) My teenage nieces keep beating me in the word puzzle 'Jumble'. I've tried using alphabet blocks to be able to shuffle the letters quickly and come up with an answer, but to no avail. Since I have a programming background, I've decided that I will write a computer program which for sure will beat my nieces. But I can not find a formula that I can program which will take a collection of letters (.e.g., 'TCA'), and return all possible permutations, one of which I will recognize as a word (e.g., 'CAT'). Once I program this on the computer, then victory awaits me. Thank you. F. Gonzaga Date: 06/21/2002 at 11:45:08 From: Doctor Ian Subject: Re: Statistics (Permutation or Combinations) Hi Fred, The easiest way to write a program like this is to use recursion. Using the example letters 'c', 'a', and 't', you can start with the empty string, and the letters yet to be assigned: ():(c a t) The recursive step is to check to see if you have any characters remaining in the unassigned list. If you do, then you add each of those letters in turn to the assigned list, and then turn around and send each of those to the same function: ():(c a t) -> (c):(a t) -> (c a):(t) -> (c a t):() Done! -> (c t):(a) -> etc. -> (a):(c t) -> etc. -> (t):(a c) -> etc. (If you haven't done any recursive programming, this is your chance to learn about it!) This is easiest in a language like Lisp, where you can just make up data structures on the fly by constructing nested lists, and which handles allocation and deallocation of memory automatically; and more complicated in a language like C++, where you have to set up structures, pointers to those structures, allocation and deallocation methods, and so on. In fact, an entire Emacs Lisp program to generate the permutations of a set of characters would look like this: (defun extend (s) (mapcar '(lambda (x) (list (append (car s) (list x)) (drop x (cadr s)))) (cadr s))) (defun permute (s) (cond ((null (cadr s)) (list s)) (t (mapcar 'permute (extend s))))) (defun drop (x s) (cond ((null s) s) ((eq x (car s)) (cdr s)) (t (cons (car s) (drop x (cdr s)))))) (mapcar 'permute (list (list ( ) '(a b c d e)))) ^ ^ | | Initial Unassigned (empty) characters string The first function, extend, takes an item that looks like ((a) (b c d)) and turns it into a list of items that looks like (((a b) (c d)) ((a c) (b d)) ((a d) (b c))) The second function, permute, takes a list of these guys, checks each one to see if there are any characters remaining to be distributed. If not, it just returns the finished item, e.g., ((a c b) ()) This is what keeps the recursion from continuing forever. If there are unassigned characters, it extends each item in the list, and then applies itself to the new list. The third function, drop, removes a sincle occurrence of a letter from a list containing multiple occurrences of that letter. This allows the program to handle jumbles like 'haade' ('ahead'). The second step, of course, would be to check the strings you generate this way against some kind of online dictionary. Does this help? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/ Date: 06/21/2002 at 11:54:13 From: Fred Gonzaga Subject: Thank you (Statistics (Permutation or Combinations)) Thank you for your help. Since I do mostly VBA programming, I will have to figure out how I can do recursion in this language. Once again, thank you. Date: 06/21/2002 at 15:04:10 From: Doctor Ian Subject: Re: Thank you (Statistics (Permutation or Combinations)) Hi Fred, I've never used VBA, so I'm not sure if it supports recursion. Some languages don't. However, a simple way to avoid recursion would be to have two arrays, one for incomplete items, e.g., (a c):(b d) and one for complete items, e.g., (a c d b):() Then you loop through the first array, each time removing the first element, and either (1) moving it to the second array, or (2) expanding it, and placing the new elements at the end of the first array. When the first array is empty, the second array should contain all the permutations. You can avoid having to set up data structures by using strings, e.g., ca:bde Then the expansion function looks like this: If there are characters after the colon { for each such character { - remove it from after the colon - place it immediately before the colon - place the item on the end of the incomplete array } } Otherwise { Remove the colon and place the item on the complete array } Have fun. - Doctor Ian, The Math Forum http://mathforum.org/dr.math/ Date: 06/21/2002 at 16:33:55 From: Fred Gonzaga Subject: Thank you (Statistics (Permutation or Combinations)) I know how to use arrays very well, so I think I can do this using the VBA array function. Thanks again. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/