Jump to content

permutation algorithm


birbal

Recommended Posts

I am trying to figure out the permutated set of R number of element from N number of elements.3p2. eg from the set of a,b,c i want to get the element as ab,ac,cc,ba,ba...so on. How should i approach? is there any algorithm of it to solve it?

Link to comment
Share on other sites

I am trying to figure out the permutated set of R number of element from N number of elements.3p2. eg from the set of a,b,c i want to get the element as ab,ac,cc,ba,ba...so on. How should i approach? is there any algorithm of it to solve it?
I have not tried this, but if it works, please let me know.http://goo.gl/VqQcARoddy
Link to comment
Share on other sites

@iwatao Realy Thanks for the link. that link/resource is awesome. I am not sure i can make it or not.It seems its much complexer than i assumed.If i can make it i will inform you.That links shows the code but i am having trouble to understand that how graph data structure is being implemented in permutation genarating. Can anyone please elaborate how graph is implemented here? It is not clear to me from that page.

Link to comment
Share on other sites

from that link the Dijkstra's algorithm is not that a graph implemented? if i am not mistaking. I researched web and found that graph can be implemented to in this case.It is not my homework.

Link to comment
Share on other sites

Can anyone please elaborate how graph is implemented here? It is not clear to me from that page.
You need to ask a specific question, as it would be too time consuming to run through the entire algorithm.I have run the Djikstra algorithm, since I last suggested the webpage, and it works with the following four limitations:1) It produces an extraneous error message. I am presently trying to figure out what is generating the error message, so that it can be eliminated.2) It uses the split() function which is a member of the POSIX Regex class of functions. According to the manual this class has been deprecated. This problem is easily fixed, however, by substituting the split() function with the explode() function. I also replaced the join() function with the implode() function.3) In its present form the algorithm only generates permutations for the same number of elements as there are elements in the original input array. In other words, it only performs P(n, r) where r = n.4) Finally, it does not allow for repeated elements.My approach to understanding how the algorithm works, has been to take the permutation as a given, and work my way through what follows. What generates the permutation list is repeated runs of the permutation() function with reassignment of the $perm parameter after each run.The rest of the code builds a two-dimensional array with each sub-array of the main array containing one permutation. Before listing the elements of the main array, each subarray is dismantled into a string via the join() or implode() function.Roddy
Link to comment
Share on other sites

@iwato yes i have notice it too what you have mentioned when i ran that code. I was confused with that how that algorithm implementing graph there.as for your point 3 if n=r but i want npr where n[stk]=[/stk]rand as well as i want to show the repeated elements too. eg aa bb will be also valid.I figure out a quite different approach. I write down the structure and the algorithm in paper and seems it going to work though i did not write and run the code.if everything goes well it will solve the point 3 and 4 too...if it works i will inform you.

Link to comment
Share on other sites

If you just want a function that will return all possible elements of some language L = {a : a ∈ S}r, S = {"a", "b", ...} with n elements then you could just use a recursive function, as such:

function combine($set, $r) { // for example, combine(array("a", "b", "c"), 2);	if ($r > 1) {		$result = array();		foreach ($set as $element) {			foreach (combine($set, $r - 1) as $suffix) {				$result[] = $element . $suffix;			}		}		return $result;	} else {		return $set;	}}

Link to comment
Share on other sites

$depth is the number of r elements$content is the n number of elements

<?php$depth=3;$content=array('a','b','c');//var_dump($content);$GLOBALS['maxval']=count($content)-1;$slots=array_fill(0,$depth,0);function permutation(&$slots,$content,$depth){		$pointer=$lastindex=count($slots)-1;		while($slots[$lastindex]<=$GLOBALS['maxval'])		{			# COUNT THE ELEMENTS				if(!isset($counter))				static $counter=0;								$counter++;			$output='';			for($i=0;$i<$depth;$i++)			{				$output.=$content[$slots[$i]];			}			echo $output.'<br/>';			$slots[$lastindex]++;		}		while($slots[$pointer]>=$GLOBALS['maxval'])		{			$slots[$lastindex]=0;			$slots[$pointer]=0;			$pointer--;						if($pointer<0)			return $counter;		}		$slots[$pointer]++;}while(TRUE){$p=permutation($slots,$content,$depth);if($p)break;}echo "TOTAL PERMUTATED ELEMENT: $p<br/>";?>

Thats what i roughly came up with. It showing all the nr elements.Though synook's method is more better and faster. thanks for the helps all

Link to comment
Share on other sites

  • 2 weeks later...
If you just want a function that will return all possible elements of some language L = {a : a ∈ S}r, S = {"a", "b", ...} with n elements then you could just use a recursive function, as such:
function combine($set, $r) { // for example, combine(array("a", "b", "c"), 2);	if ($r > 1) {		$result = array();		foreach ($set as $element) {			foreach (combine($set, $r - 1) as $suffix) {				$result[] = $element . $suffix;			}		}		return $result;	} else {		return $set;	}}

I just wanted to thank Synook for still another great example of recursivity in the W3Schools' PHP forum. I would like to suggest, however, that the function be renamed repermute for the following two reasons:1) In mathematics the term combination refers to special subsets of the sets of values generated by this function.2) As the sets of permutation generated by this function includes the repetition of values, the prefix re- seemed appropriate.This is truly an elegant way of permuting a set of values.Best wishes from Jeddah, Saudi Arabia,Roddy
Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.

×
×
  • Create New...