Page 1 of 2
ugh, stupid math!
Posted: Mon Feb 26, 2007 3:21 pm
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
I don't know how to work the equation. I know what a factorial is, but my calculator won't go that large.
Posted: Mon Feb 26, 2007 3:35 pm
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
Posted: Mon Feb 26, 2007 3:41 pm
by s.dot
well if you continued that out.. that would be N factorial'd.. but that's only part of the equation!
Posted: Mon Feb 26, 2007 3:41 pm
by RobertGonzalez
Based on that formula, wouldn't it look like:
63!/(63 - 6)! => 63!/57!
A geeks perspective on your problem
Posted: Mon Feb 26, 2007 3:43 pm
by s.dot
I think it would be..
63*6 = 63!/57!
but I can't figure that out.
Posted: Mon Feb 26, 2007 3:45 pm
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
Posted: Mon Feb 26, 2007 3:51 pm
by s.dot
well if you substitute N and R
the equation would look exactly like this
(63)6 = 63!/(63-6)!
Posted: Mon Feb 26, 2007 3:52 pm
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:
Which any fool with a calculator could tell you is:
/ Just kidding about that any fool with a calculator bit.

Posted: Mon Feb 26, 2007 3:52 pm
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."
Posted: Mon Feb 26, 2007 3:53 pm
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)!.
Posted: Mon Feb 26, 2007 3:55 pm
by s.dot
ah, i got ya
good job moose, everah, & feyd
Posted: Mon Feb 26, 2007 3:58 pm
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.
Posted: Mon Feb 26, 2007 4:25 pm
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];
}
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.
Posted: Mon Feb 26, 2007 4:31 pm
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
Posted: Tue Feb 27, 2007 11:00 am
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!