ugh, stupid math!

Ye' old general discussion board. Basically, for everything that isn't covered elsewhere. Come here to shoot the breeze, shoot your mouth off, or whatever suits your fancy.
This forum is not for asking programming related questions.

Moderator: General Moderators

User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

ugh, stupid math!

Post by s.dot »

I can't figure this one out.

Permutation without repetition

I have an array of 63 characters. I want to find out how many unique 6-character combinations can be made with these 63 characters, using each character only once in each combination (character can be used again in next combination - but no character can be used twice in the same combination).

I wikipedia'd it, and found this equation.

http://en.wikipedia.org/wiki/Combinatorics
Image

I don't know how to work the equation. I know what a factorial is, but my calculator won't go that large.
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
TheMoose
Forum Contributor
Posts: 351
Joined: Tue May 23, 2006 10:42 am

Post by TheMoose »

Well you have 6 slots, each with a possibility of 63 - N characters, where N is the current slot (0-based). So the formula would look like:
63 x 62 x 61 x 60 x 59 x 58 = 48,920,775,120
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post by s.dot »

well if you continued that out.. that would be N factorial'd.. but that's only part of the equation!
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
RobertGonzalez
Site Administrator
Posts: 14293
Joined: Tue Sep 09, 2003 6:04 pm
Location: Fremont, CA, USA

Post by RobertGonzalez »

Based on that formula, wouldn't it look like:

63!/(63 - 6)! => 63!/57!

A geeks perspective on your problem
Last edited by RobertGonzalez on Mon Feb 26, 2007 3:44 pm, edited 1 time in total.
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post by s.dot »

I think it would be..

63*6 = 63!/57!

but I can't figure that out.
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
TheMoose
Forum Contributor
Posts: 351
Joined: Tue May 23, 2006 10:42 am

Post by TheMoose »

Everah wrote:Based on that formula, wouldn't it look like:

63!/(63 - 6)! => 63!/57!
Yes, but if you look at the similar parts:

57! = 1 x 2 x 3 ..... x 57
63! = 1 x 2 x 2 ..... x 57 x 58 x 59 x 60 x 61 x 62 x 63

Since they are multiplying on both numerator and denominator, you can cancel common portions out, thus leaving 58 x 59 x 60 x 61 x 62 x 63
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post by s.dot »

well if you substitute N and R

the equation would look exactly like this

(63)6 = 63!/(63-6)!
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
RobertGonzalez
Site Administrator
Posts: 14293
Joined: Tue Sep 09, 2003 6:04 pm
Location: Fremont, CA, USA

Post by RobertGonzalez »

The moose had it right --> http://mathforum.org/dr.math/faq/faq.comb.perm.html

From that article you would have:

Code: Select all

63 x 62 x 61 x 60 x 59 x 58 x 57 x 56 x 55 ...
----------------------------------------------
                              57 x 56 x 55 ...
Since the similar parts essentially divide to 1, you are left with:

Code: Select all

63 x 62 x 61 x 60 x 59 x 58
Which any fool with a calculator could tell you is:

Code: Select all

48920775120
/ Just kidding about that any fool with a calculator bit. :wink:
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

Code: Select all

[feyd@home]>php -r "function f($n) { $len = $n; $x = '1'; while(bccomp($len, '1') > 0){$x = bcmul($x, $len); $len = bcsub($len, 1);} return $x;} var_dump(rtrim(bcdiv(f(63), f(63-6), 1000), '0'));"
string(12) "48920775120."
Last edited by feyd on Mon Feb 26, 2007 3:55 pm, edited 1 time in total.
User avatar
RobertGonzalez
Site Administrator
Posts: 14293
Joined: Tue Sep 09, 2003 6:04 pm
Location: Fremont, CA, USA

Post by RobertGonzalez »

scottayy wrote:well if you substitute N and R

the equation would look exactly like this

(63)6 = 63!/(63-6)!
No, you are looking for (n)r. (n)r is defined as n!/(n - r)!. So you are looking for (63)6, or, as an equation, 63!/(63 - 6)!.
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post by s.dot »

ah, i got ya

good job moose, everah, & feyd
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
TheMoose
Forum Contributor
Posts: 351
Joined: Tue May 23, 2006 10:42 am

Post by TheMoose »

The way I learned (made it easier than learning permutations and the like), was to think of it as you have 6 chairs, and 63 people. When you fill the first chair, you only have 62 choices left to fill in the second chair, and 61 for the third, etc. You take each of these total choices and multiply. Don't worry about formulas, make a picture, create your own analogy, whatever makes sense to you, and the logic and numbers will fill themselves in.
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post by s.dot »

so, this goes a bit beyond the general topic :))

is there a better way to get all the permutations without repetition than..

Code: Select all

for($i=0;$i<100000000000000000000000000;$i++)
{
   shuffle($chars);
   $combo = $chars[0].$chars[1].$chars[2].$chars[3].$chars[4].$chars[5];
}
:lol:

Currently that's what i'm doing. And I'm inserting it into a database. Then I'm going to perform a query INSERT INTO `table` (`combo`) VALUES(SELECT DISTINCT `combo` FROM `combos`)

Working... but inefficient, and not guaranteed to get all of the combos.
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post by s.dot »

meh, nevermind, it's not imperative that I get EVERY unique combination
just a couple million of them
and that will do the job
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
TheMoose
Forum Contributor
Posts: 351
Joined: Tue May 23, 2006 10:42 am

Post by TheMoose »

Because I felt challenged to do so:

Code: Select all

$combos = array();
$chars[0] = "a";
$chars[1] = "b";
$chars[2] = "c";
$chars[3] = "d";
$chars[4] = "e";
$chars[5] = "f";
for($i=0; $i<6; $i++) {
	$comboi = $chars[$i];
	for($j=0; $j<6; $j++) {
		if(strpos($comboi, $chars[$j]) === false) {
			$comboj = $comboi . $chars[$j];
			for($k=0; $k<6; $k++) {
				if(strpos($comboj, $chars[$k]) === false) {
					$combok = $comboj . $chars[$k];
					for($l=0; $l<6; $l++) {
						if(strpos($combok, $chars[$l]) === false) {
							$combol = $combok . $chars[$l];
							for($m=0; $m<6; $m++) {
								if(strpos($combol, $chars[$m]) === false) {
									$combom = $combol . $chars[$m];
									for($n=0; $n<6; $n++) {
										if(strpos($combom, $chars[$n]) === false)
											$combos[] = $combom . $chars[$n];
									}
								}
							}
						}
					}
				}
			}
		}
	}
}

foreach($combos as $item) {
	echo $item . "<br>";
}
Yes, it's ugly with that many nested loops, but it works :). You only need to nest a loop for each additional character you want in the final combination (6 characters, 5 nested loops, or 8 characters, 7 nested loops).

That will give you every unique combination of a six character string that can contain letters A-F lowercase. You can obviously modify it to be up to 63 easily, but the logic is there for you :)

View it in action!
Post Reply