Method to generate every possible combination of a given # of characters...

[superwormy]

Say you're given 5 characters, say they are:

a, d, i, k, z

I need a methodical way to generate every possible unique string using those characters, ie:

adikz
adkzi
akzid

Etc. etc. etc. theres probably lots of them... I can't think of an easy way to do it where I'm not just randomly shuffling an array of letters to come up with combinations... I need to be able to get EVERY combination of letters, it can't be left up to chance.

Any thoughts? Anything, suedo code, a method, whatever is fine, doens't need to be actual code.

[Weedpacket]

Start with an empty string: ""
How many ways are there of inserting a character in a length-0 string? One: "a"
How many ways are there of inserting a character in a length-1 string? Two: "da", "ad".
How many ways are there of inserting a character in a length-2 string? Three: "ida", "dia", "dai".
Etc.

So:

Build an array $a of all the zero-length strings (should be easy)

For each $character of the source string:
  $b=array();
  For each $string in the array $a:
    For each $position in $string (0 to strlen($string) inclusive):
      Insert: $b[]= substr($string,0,$position).$character.substr($string,$position);
    :loop
  :loop
  $a = $b;
:loop

Then because some letters in the source string may be repeated, and we only want
unique results, call array_unique().

[Sxooter]

Easy, assign a number to each character, then for next loop across all the possibilities.

$chars = array("a","d","i","k","z");
for ($i=0;$i<5;$i++){
  for ($j=0;$j<5;$j++){
    for ($k=0;$k<5;$k++){
      for ($l=0;$l<5;$l++){
        for ($m=0;$m<5;$m++){
          $list[] =$chars[$i].$chars[$j].$chars[$k].$chars[$l].$chars[$m];
        }
      }
    }
  }
}

Note that by using a depth variable you could do this with a recursive array for unknown numbers of characters.

If you'd like them random, then shuffle() the array when done, although for large arrays this can be very slow.

If you want ONE at random, initialize the random seed, then do:

print $list[rand(0,count($list)-1)];

[Weedpacket]

Originally posted by Sxooter
Easy, assign a number to each character, then for next loop across all the possibilities....

Problem is that this will produce strings like "ddddd".

[martyn]

Humm, why do you need this?

hacker? Just comes to mind, in theory you can crak FTP server passwords pretty easy but it could take time using a method like this. Still i would like to know what practical use this has.

Always sceptical 😉

[superwormy]

Think 'Scrabble' :-)

It's an extra-credit assignment a friend has for high school and I thought it was interesting. Basically, find a bunch of statistics about the first move of a game of scrabble. To find that, you need to pick your seven letters, then find all combinations of those, then check against dictionary. :-)

[martyn]

Ok, thanks.

Sorry for doubting, but some people these days use innocent people to do some very uninnocent things 😉

[Sxooter]

Originally posted by Weedpacket
Problem is that this will produce strings like "ddddd".

True, but while his example showed that was what he wanted, his words didn't. :-)

Interestingly, the number of combinations arrived at in each instance (with dups and without) are commonly used in Thermal Physics, so now I'm having flashbacks. :-)

[Weedpacket]

Originally posted by Sxooter
True, but while his example showed that was what he wanted, his words didn't. :-)

Interestingly, the number of combinations arrived at in each instance (with dups and without) are commonly used in Thermal Physics, so now I'm having flashbacks. :-)

(SUMn)!/(PRODn!)

Aaah, that takes me back 🙂

[Sxooter]

We were playing "guess the equation" one day a few years ago, where you'd write an equation on the group white board and wait for someone to figure it out. NO ONE ever figured out the name of the Stirling Approximation after I put it up. NO ONE. :-)