Recursive Programming:
Finding all permutations of a factorial.
Hey, I've got a programming question for
you. I need to write something where I can test every possible combination
of certain events. First, though, I need to figure out what every possible
combination is.
For example:
The numbers 1,2,3 can be 1,2,3 or 1,3,2 or
2,3,1 or 2,1,3 or 3,1,2 or 3,2,1. That is 6 possible combinations which
comes from 3*2*1. Above 3 number's it gets hard to impossible to figure
all the combinations manually. The number 5 has 120 possibilities 5*4*3*2*1.
This problem ought to be cake for a computer program if only I could write
it. Help if you can.
Clayton
ascrooks@skn.net
(Download the source code! It's listed at
bottom of page.)
At first I thought that you wanted a algorithm
to find the factorial of a number and since Click & Create can't handle
values greater than 999,999,999 I figured it would be easier just to set
the values than to calculate them. Only the factorials 0! through
12! are less than 999,999,999. But then I read your question again, to
my horror, and found that what you really were looking for was a way to
create a list of all of the solutions or permuatations for a given factorial.
Are you sane? And you want to do this with Click & Create?!?
Well first of all let learn of all here
are some links in case you need to brush up on Combinatorics. It's going
to get complicated around here real quick.
Yahoo's
Mathematics Section:
If you ever want to learn more about Math
you can't go wrong by starting here. There's even a section specifically
on Combinatorics.
Dr.
Math:
If you look around you'll find some facinating
topics and you can even submit your own questions.
Permutation
Engine Exerciser:
This program will find and list all of the
permutations of a factorial. It's a lot easy just to download and run it
then to build one of your own from scratch in Click & Create.
You can also use your favorite search site to
find more information.
Try using these keywords: combinatorics,
permutations, combinations, generating, finding, solving.
Personally I recommend download the Permutation
Engine Exerciser if all you need is a list of solutions. But I still think
the question is interesting programming challenge for Click & Create
so I'll give it a try.
There are two ways one could go about this.
One way would be to design a algorithm that would go through all of the
combinations. Some kind of miricle if you ask me. I spent a while trying
to find a way to do exactly this. It appears to require more programming
expertise that I have right now. If you have any ideas please share them.
It's a lot harder than you might think at first.
Another way would be a Brute Force technique.
Just generate random sets and compare to list of previously generated sets
and see if there is a match. If there isn't add the set. If there is generate
another set. Now doesn't that seem nice and simple. Almost like someone
might be able to do it, huh. Well almost is right.
I had a choice either I could use and Ini
Object or the Combo Box to store my list of generated sets. I choose the
Combo Box because it has a limit of over 32,000 items and that would hold
up to factorial 7 which equals 5,040. I wish I had used the Ini Object
now it had a limit of 64K in file size and that should have been enough
to do some higher factorials. But waiting for your computer to find the
5,040 permutation randomly would take more patience than most of us have.
I wonder how long? I seperated my program into groups so I'll seperate
my answer into the same groups.
Solve Factorial:
Solving the factorial is the easy part. It's
just a matter of having the user select a value from 1 through 7 and store
it in Global Value 1. Now multiply Global Value 1 and Global Value 2. The
Global Value 2 was set to 1 at the Start of the Frame. And now you subtract
one the Global Value 1. You continue doing this as long as the Global Value
1 is greater than 1. When the Global Value 1 equals 1 then the Global Value
2 equals the factorial of the number the user selected.
Write Set / Read Set:
What I needed now was a way to generate sets.
I decided the quickest way would be the create a number of Active Objects
equal to the Value the user selected. Then Spread a Number into the Alterable
Value A of the Active Object. Now all I had to do was Pick an Active Object
at Random and add paste it on the end of a Text Object until I had the
whole set. It makes sense if you study the source code.
Add New Record?:
Here's where I had problems. My plan was
to compare the Text Object's Alterable Text to every line in the Combo
Box. If it wasn't there already add it. If it was there generate a new
set until the number of line equal the value of the factorial of the number
the user selected. The code is there but something is wrong with it.
Any ideas? I'll bribe you. If you make my
program work like it is supposed too, I decide, then I'll give you a month
of free advertising on my Friends page. You can make your own program from
scratch if you like. If you can make a program that can list all of the
permutations of a given factorial without using a Brute Force method or
some other cheat, my decision, then I'll give you two months of free advertising.
If you have any ideas or suggestion let me know them also. I'd appreciated
greatly and I will add your name to my credits page.
I've included the source code for you to
download which should help with your understanding.
factors.zip (4 KB):
Download Click & Create source code for Recursive Programming.
This page and all of
its contents are Copyright 1997-98 by Christopher
Jay Craft.
|