Getting all possible arrangements of a string

shxfee

I am trying to get all the possible arrangements of a string. For example if we have the string abc then the program should output this:
abc - acb - bca - bac - cab - cba

i have done it, well kind of. And it is really not working. Because this program is a guess work it takes a long time for a bigger string like abcdefgh and it has other bugs. does anybody have any alternatives to this? 😕

<?php
$words = str_split('abcde'); #this is the string for processing
$length = $i = sizeof($words);
$results = 1;

// Lets first find out how many results we are going to be having
do{
	$results *= $i;
	$i--;
}while($i > 0);
echo "We are going to be having $results different ways for $scrambled.\n\n";
sleep(2);

$have = array();
for ($i=1;$i<=$results;$i++){
	// We should try this until we get a value thats hasnt yet been created
	do{
		shuffle($words);
		$result = implode($words);
	}while(in_array($result, $have));

echo $i.".$result\n";

$have[] = $result;
}
?>

Weedpacket

You could do it recursively. To generate all the permutations of an n-character string, assuming all the characters are distinct, first generate all the permutations of an (n-1)-character string, make n copies of each permutation, and insert the n character in a different position in each copy.

String "abcd"
n=0:""
----
n=1:"a"
a
----
n=2:"ab"
ba
ab
----
n=3:"abc"
cba
bca
bac
cab
acb
abc
----
n=4:"abcd"
dcba
cdba
cbda
cbad
dbca
bdca
bcda
bcad
dbac
bdac
badc
bacd
dcab
cdab
cadb
cabd
dacb
adcb
acdb
acbd
dabc
adbc
abdc
abcd

There are faster iterative approaches based on minimum-change flips, but they're a bit trickier to code; but either way a systematic approach would be more robust than using bogosort.

shxfee

hmm. let me try this on 🆒