Hey, I need some help. My math teacher said that if I could get show him all the possible combinations of scrambling the word PERPENDICULAR then he'd give me an A for both semesters.
I figure this wouldn't be that difficult to program it into an executable file that wil just keep generating the combonations. I know basic.... well... BASIC.
I know that there are over 700 million combonations. I was thinking of something that would just write them into a text file or something. I wasn't planning on printing this. I was planning on giving it to him on a disc or CD or something. Anybody want to lend me a hand?
Need help from you programmers!
Does each solution use all letters, or one or more?
Either way, one tricky thing will be to eliminate all the duplicates, since P, E and R are repeated.
Another tricky thing is that even using the max number of letters in each combination, I think there are over 6 billion possibilities (with duplicates). If one character is 1 byte, the solution wouldn't even fit on a DVD.
Either way, one tricky thing will be to eliminate all the duplicates, since P, E and R are repeated.
Another tricky thing is that even using the max number of letters in each combination, I think there are over 6 billion possibilities (with duplicates). If one character is 1 byte, the solution wouldn't even fit on a DVD.
-
SHIFTrl240
- Posts: 544
- Joined: Mon Jul 07, 2003 4:28 pm
- Car: 1990 SR20 Sil-80
2009 Yamaha RoadStar Warrior
2017 Alfa Romeo Giulia Ti AWD - Contact:
this reminds me of something my biology teacher said to the class on the first day 
"if you can write all the numbers from 1 to a million out on paper for me, you will ace the class"
this girl from a different classroom actually got up to something like 120,000 or something, and spent like 5 hrs a day doing it for a few months.... it was crazy.
"if you can write all the numbers from 1 to a million out on paper for me, you will ace the class"this girl from a different classroom actually got up to something like 120,000 or something, and spent like 5 hrs a day doing it for a few months.... it was crazy.
Loops to make it smaller? Whoah slow down!
There would be a helluva lot of combinations. But if your output is just a text file it would zip up really nice. If i have any free time tonight I'll put something together in C++. I might write a COBOL job. I'll bet our Hoast could take it on in several minutes. I'll get back to you hopefully by monday.
There would be a helluva lot of combinations. But if your output is just a text file it would zip up really nice. If i have any free time tonight I'll put something together in C++. I might write a COBOL job. I'll bet our Hoast could take it on in several minutes. I'll get back to you hopefully by monday.
solution available - the program described here constructs a list of all permutations of a word:
http://www.math.grin.edu/~ston...xhtml
it's written in a dialect of Lisp called Scheme
p.s. i think the number of permutations of a 13 letter word is 13! = 6,227,020,800 (much larger than 700mil), if each character takes 1 byte, then your resulting (uncompressed) text file will be about 87GB
http://www.math.grin.edu/~ston...xhtml
it's written in a dialect of Lisp called Scheme
p.s. i think the number of permutations of a 13 letter word is 13! = 6,227,020,800 (much larger than 700mil), if each character takes 1 byte, then your resulting (uncompressed) text file will be about 87GB
you're right, i didn't take the repeated letters into account. there are 10 unique letters in PERPENDICULAR, so it does make sense that the total is less than my 13! :pfaceRobDET wrote:the reason it is less is becasue some of the letters are repeated. Their are only 9 possible letters.
i don't think n!/(n-r)! works here. take the word DOD for example, there are 3 permutations: DOD, ODD, DDO. according to you there should be 3!/(3-2)! = 6.
i think in this case the correct formula is:
n!/(n1!n2!...nt!)
it's used for counting generalized permutations, it applies if a sequence of n items has n1 identical items of type 1, n2 identical items of type 2, ..., nt identical items of type t.
so for the word DOD:3!/2! = 3
and for the word PERPENDICULAR:13!/(2!2!2!) = 778,377,600
i don't know what gotoxy() is, but it's considered extremely bad practice to use GoTo functions (leads to spaghetti codeVengeance wrote:You would have to use arrays , gotoxy 's and loops..
PERPENDICULAR int z=p,y=e,x=r,w=p,v=e,u=n,t=d..ect
while(x=1, x++, x>13) { gotoxy (12,3); cout<<z<<y<<
}
have fun I started it for you
)here's a famous paper on the subject:http://www.acm.org/classics/oct95/
[quote=" nomuken
and for the word PERPENDICULAR:13!/(2!2!2!) = 778,377,600 [/quote]
I like your theory (law? Did you reverse engineer it or look it up?)
I'm not sure how i'm gonna verify your answer. Thats one Helluva Counter.
I may not see you guys on NICO for a while while my machine Explodes from running this program. (actuially the output is going to be the killer becasue the Cool C++ funtion doesn't have to remember it's state. It's a REALLY cool function, Definately worth looking up.)
and for the word PERPENDICULAR:13!/(2!2!2!) = 778,377,600 [/quote]
I like your theory (law? Did you reverse engineer it or look it up?)
I'm not sure how i'm gonna verify your answer. Thats one Helluva Counter.
I may not see you guys on NICO for a while while my machine Explodes from running this program. (actuially the output is going to be the killer becasue the Cool C++ funtion doesn't have to remember it's state. It's a REALLY cool function, Definately worth looking up.)
found this recursive algorithm in "C/C++ Users Journal"
Just writing a function to generate permutations isn't particularly hard. One easy way to tackle the problem is with a recursive approach. If the string you want to permute is n characters long, you execute a loop that makes one pass per character in the string. Each time through the loop you remove character i from the string, and keep it as a prefix. You then print out all the permutations of the remaining substring concatenated with the prefix. How do you get the list of permutations of the substring? By recursively calling the permutation function. The only additional piece of logic you need to include is the test to see if a substring is only one character long. If it is, you don't need to call the permutation function, because you already have the only permutation of the string.
For example, to print the permutations of "abc", you will first strip off the "a" character, and then get the permutations of "bc". To get those permutations, you will first strip off the "b" character, and get a resulting permutation list of "c". You then strip off the "c" character, and get a resulting permutation of "b". The results when combined with the prefix character of "a" give strings "abc" and "acb".
You then repeat the process for prefix "b" and substring "ac", then for prefix "c" and substring "ab".
the implementation given in C++ is only 23 lines long :pface
Just writing a function to generate permutations isn't particularly hard. One easy way to tackle the problem is with a recursive approach. If the string you want to permute is n characters long, you execute a loop that makes one pass per character in the string. Each time through the loop you remove character i from the string, and keep it as a prefix. You then print out all the permutations of the remaining substring concatenated with the prefix. How do you get the list of permutations of the substring? By recursively calling the permutation function. The only additional piece of logic you need to include is the test to see if a substring is only one character long. If it is, you don't need to call the permutation function, because you already have the only permutation of the string.
For example, to print the permutations of "abc", you will first strip off the "a" character, and then get the permutations of "bc". To get those permutations, you will first strip off the "b" character, and get a resulting permutation list of "c". You then strip off the "c" character, and get a resulting permutation of "b". The results when combined with the prefix character of "a" give strings "abc" and "acb".
You then repeat the process for prefix "b" and substring "ac", then for prefix "c" and substring "ab".
the implementation given in C++ is only 23 lines long :pface
-
Rockenreno
- Posts: 2891
- Joined: Sun Jan 05, 2003 5:48 pm
- Car: 1997 BMW M3
- Contact:
-
Stuntman240
- Posts: 198
- Joined: Tue Aug 05, 2003 9:01 am
- Car: 91 coupe
-
nametakennow
- Posts: 10024
- Joined: Sat Aug 24, 2002 4:14 pm
- Car: '06 MINI Cooper S
running the program that uses the recursive algorithm (so slow :pface ) that i showed above. so far taking over 6 hours on an Alpha EV67 with 1GB of RAM.
so far the resulting text file is a little over 16GB, and looks like this:
-----------------------------------PERPENDICULARPERPENDICULRAPERPENDICUALRPERPENDICUARLPERPENDICURLAPERPENDICURALPERPENDICLUARPERPENDICLURAPERPENDICLAURPERPENDICLARU...
ECPDPRIRAUNLEECPDPRIRAULENECPDPRIRAULNEECPDPRIRALENUECPDPRIRALEUNECPDPRIRALNEUECPDPRIRALNUEECPDPRIRALUENECPDPRIRALUNEECPDPRIERNULA-----------------------------------
so far the resulting text file is a little over 16GB, and looks like this:
-----------------------------------PERPENDICULARPERPENDICULRAPERPENDICUALRPERPENDICUARLPERPENDICURLAPERPENDICURALPERPENDICLUARPERPENDICLURAPERPENDICLAURPERPENDICLARU...
ECPDPRIRAUNLEECPDPRIRAULENECPDPRIRAULNEECPDPRIRALENUECPDPRIRALEUNECPDPRIRALNEUECPDPRIRALNUEECPDPRIRALUENECPDPRIRALUNEECPDPRIERNULA-----------------------------------