Permutations algorithms.

RR_QQ

OK, so I have to write a program outputs all the possible permutations of an array of strings. I found a greate function that does EXACTLY what I want here http://www.zend.com/code/codex.php?id=1419&single=1. For example if I have an array 'a', 'b', 'c' the output will be:

a
b
c
ab
ac
ba
bc
ca
cb
abc
acb
bac
bca
cab
cba

This is all fine and dandy until the array gets to be of a size of like 7+. The program is extremely slow if it has to create all permutations for 7+ items in an array. I will need to create permutations for arrays that have sized greater than 7, like size 10, 15 etc. That meas my program will NEVER end running.

Can anyone point me in the right direction? I have been researching all day as well as playing with different ways of speeding up the function but no satisfactory progress yet.

Any pointers will be greatly appreciated!

dougal85

A quick google gives you lots of possables;

http://www.google.com/search?q=Permutations+php

or if you take PHP out and replace with another language you will get many more than you can port to PHP or whatever.

Hope they can help, I'm afraid i don't have time to test them for you 😉 and you didnt give us much indication how long yours takes... how long you need it to take. and so on.

Weedpacket

So I was bored. There are probably much faster methods.

function factorial($n)
{
	static $memo = array(1);
	if(!isset($memo[$n]))
	{
		$memo[$n] = $n*factorial($n-1);
	}
	return $memo[$n];
}


function NthPermutation($n1, $l)
{	$n = $n1;
	$s = $l;
	$permutation=array();
	for($i=count($l)-1; $i>=0; --$i)
	{	$n %= factorial($i+1);
		$ki = intval($n/factorial($i));
		$k = $s[$ki];
		unset($s[$ki]);
		$s = array_values($s);
		$permutation[] = $k;
	}
	return $permutation;
}

$l = range(0,9);
$count = factorial(10);
for($n=0; $n<$count; $n++)
{
	echo join('', NthPermutation($n, $l)),"\n";
}

dougal85

So bored you done it twice?

edit,
oops, i'm sure there was two? did you just delete one? 😛

RR_QQ

Let me try that out...yes I should look for solutions in other languages and then port them to php...thans Weed and Doug...I will keep you posted.

Well as for how long I want it to take..with the function link I provided the program took over 15 minutes on a single string "thisismyhome" - and so i stopped it because i dont know how long it was goign to take. But 15-20 minutes (or more) for each string of unspecified lenght is unacceptable. I need to do this for 50,000+ strings.......What I'm tryign to do is identify what words are in that string (goint to thisismyhome you find 'this', 'is', 'my, 'home' - i'm doing this by using the pspell functions in php)

NogDog

The basic problem is the geometric increase in possible combinations as you increase the number of letters. With 4 letters there are 64 combinations*, but with 8 letters there are 109,600 combinations**. So an algorithm that takes 10 milliseconds per combination would seem fine for 4 letters (only 0.64 seconds to process) would take 1096 seconds (about 18 minutes) with 8 letters.

So say you figured out an algorithm that was 10 times faster, so that 8 letters only took a little under 2 minutes. Just add a couple more letters (10 total), and you are up to 9,864,100*** possible combinations, so the 10-times-faster algorithm would now take 9864 seconds, or over 2-1/2 hours.

4+(43)+(432)+(4321)
8+(87)+(876)+(8765)+...etc....+(87654321)
10+(109)+(1098)+(10987)+...etc....+(1098765432*1)

leatherback

Nog..

I need to sak this.. WHY do you need this?
it very muc sounds like a hacking script to me.

Anyway.. If you need all the combinations.. the time it tak is just the time it takes. Generating the combo's is not going to be the provblem if you want to do something with it too later on..

NogDog

leatherback wrote:
Nog..

I need to sak this.. WHY do you need this?...

I don't want to do this, RR_QQ wants to.

leatherback

NogDog wrote:
I don't want to do this, RR_QQ wants to.

RR_QQ

Wow I never realized that I had to give the reason WHY I want to do something when I post messages on here. I just do. So what? And I wanted some help. If you want, why don't you just send over the FBI and the CIA to find out why I want to do this. Gees now I'm a hacker? hahah. Thanks for your complement!

But to all the others who saw the mathermatical problems and issues associated with what I am trying to do and commented on it thank you very much! I opted instead of coming to a ROUGH estimate of how many words are in a string by starting to develop a method to identify metawords and keywords in a string and eliminate undesirable string from there and give and ESTIMATE of the number of words found. It will be enough for this project.

leatherback

Really no need to be sarcastic. Just that I do not feel to inclined to help somebody to hack their way into some poor bastards server.

Your reply convinces me even more that you are trying to do something dodgy. Otherwise you could easily answer the question. Most people have no problem with explaining what they are doing and why. Often it helps to have this understanding, as 80% of the people go about solving their problem in a complex way, as they are not aware of the simple methods.

I for one cannot imagine why you would need all the permutations of a string. Made me curious, and all i can think of is to try and hack yourselfthrough a list of words.

RR_QQ

I understand. That you don't understand is not my problem. I said what I am trying to do and the reason why I'm not compelled to tell you why I want to do it is because you immediately think I'm trying to do something illegal. Like I said, report me to the right authorities and problem solved. Thank you!

And again thanks to everyone else for pitching in constructive comments and not needless chatter that does not advance the topic in a discussion into a productive environment. If I am doing anything wrong then I'm sure the forum moderators will rectify things.

Weedpacket

Why do we need to know? Without that context the answers we give, though technically accurate, may be totally inappropriate for the situation. Like leatherback said:

Often it helps to have this understanding, as 80% of the people go about solving their problem in a complex way, as they are not aware of the simple methods.

I couldn't think of a practical application, either. I just didn't say anything.

Besides, your logic is flawed:

RR_QQ wrote:
the reason why I'm not compelled to tell you why I want to do it is because you immediately think I'm trying to do something illegal.

That's just begging the question.

RR_QQ

So I guess you would be content if I said "yes i'm trying to hack". Why in hell would I do that?

You know why I am trying to do this? I have to build a system that will rate strings by the string length and word count in a string. The less words I have and the shorter the string the higher the score. And this is all for work.

Now since my logic is so flawed will now I be asked to tell you what the sytem is for and who I'm building it for and perhaps my social security number? You guys are just ridiculous.

Thanks.

dougal85

lol, Safe to say this thread has gone of the rails.

Thus, all that needs to be said is. RR_QQ if you don't like the help you are getting, go somewhere else to get it.

sid

RR_QQ wrote:
So I guess you would be content if I said "yes i'm trying to hack". Why in hell would I do that?

You know why I am trying to do this? I have to build a system that will rate strings by the string length and word count in a string. The less words I have and the shorter the string the higher the score. And this is all for work.

Now since my logic is so flawed will now I be asked to tell you what the sytem is for and who I'm building it for and perhaps my social security number? You guys are just ridiculous.

Thanks.

you need to chill - the point is that your script is a classic brute force tool.
for my masters thesis i had a very similar task to accomplish like the one you described, however, i can't think of any situation where i would have explicitly needed to know/store all possible permutations... but thats just my 2 cents.

leatherback

RR_QQ wrote:
You know why I am trying to do this? I have to build a system that will rate strings by the string length and word count in a string. The less words I have and the shorter the string the higher the score. And this is all for work.

An here you have exactly the reason I asked WHY you needed all permutations... This is never going to be the most efficient way to achieve the things you are trying to achieve, as you are generating millions, even billions of letter combinations, of which a fraction will be a valid word. All the rest is just memory and processor waisting.

But I suppose I do not need to tell you, as you know it all already.

As for reporting the authorities when I feel someone is trying to hack around a bit: Neuh, not my thing. But I am not going to waste my brain & energy on that. I'd rather help somebody who actually needs something practical done, and appreciates it when somebody tries to think outside the box presented, and tries to improve their logic & application, rather than just the one algorithm at hand.

Have fun

MookM

Assume: I have a number of folders in a main directory. Each folder has at least one or more files in them, in varying sizes. So the total file size contained in each of the folders can vary, like so:

[0] => Folder 1, 701 mb
[1] => Folder 2, 696 mb
[2] => Folder 3, 1.09 gb
[3] => Folder 4, 723 mb
[4] => Folder 5, 3.07 gb
[5] => Folder 6, 699 mb
[6] => Folder 7, 701 mb
[7] => Folder 8, 699 mb
[8] => Folder 9, 700 mb
[9] => Folder 10, 791 mb
[10] => Folder 11, 701 mb
[11] => Folder 12, 701 mb
...

At any given time, my main directory can contain an aggregate of maybe 10 gb or so. Maybe 20 gb. Maybe 40 gb. As I said, it varies.

Now, I want to burn folders and files into a dvd disk. I wish to back up my files, you see.

So my problem is: which combination of the folders gives a 'best fit' into a blank dvd, given that a blank dvd can contain 4.7 gb?

So, for example, I try combining Folders 1, 2, 3, 4 and 12:

[0] => Folder 1, 701 mb
[1] => Folder 2, 696 mb
[2] => Folder 3, 1.09 gb
[3] => Folder 4, 723 mb
[11] => Folder 12, 701 mb

TOTAL: 3.85 GB

Which fits nicely into my blank dvd, sure.

But if I try Folders 7 to 12:

[6] => Folder 7, 701 mb
[7] => Folder 8, 699 mb
[8] => Folder 9, 700 mb
[9] => Folder 10, 791 mb
[10] => Folder 11, 701 mb
[11] => Folder 12, 701 mb

TOTAL: 4.19 GB

I am able to fit more into my dvd and therefore maximize the use of one blank disc. But which other combinations are better?

Granted that via php I can put all folder items in my main directory into an array like above, I need to generate possible combinations of folders per compilation, get the total size of each compilation and compare them with each other. And that's where I'm stumped at.

I think that my problem is essentially the same as RR_QQ's, as far as figuring out different combinations or permutations of my subfolders. And I think it's practical enough for most people.

So any takers?

Weedpacket

MookM wrote:
So any takers?

The search phrase I recommend you try is "bin packing problem", because that's what you're describing.