3

Possible Duplicates:
Display possible combinations of string
algorithm that will take numbers or words and find all possible combinations

If I have 3 strings, such as:

"abc def xyz"

And I want to find the max number of combinations I can generate by rearranging these strings, e.g:

  • abc xyz def
  • def xyz abc
  • xyz abc def

etc. What's the formula/algorithm for calculating this?

Community
  • 1
  • 1
Ali
  • 261,656
  • 265
  • 575
  • 769
  • possible duplicate of [Display possible combinations of string](http://stackoverflow.com/questions/3200272/display-possible-combinations-of-string) and [a couple others](http://stackoverflow.com/search?q=string+combinations+php), for instance http://stackoverflow.com/questions/1256117/algorithm-that-will-take-numbers-or-words-and-find-all-possible-combinations - I remember some others, but am too lazy to find them now. – Gordon Aug 06 '10 at 17:02
  • Can strings be duplicated? like "abc abc def"? –  Aug 06 '10 at 17:02
  • @Gordon This is not a duplicate of that one. He's just asking for the number of permutations. – Artefacto Aug 06 '10 at 17:12
  • @Artefacto Yes, but I am 100% certain this has been answered before. It's in those *couple other I linked*. Feel free to find a more fitting one or simply ignore I chose to closevote it :) – Gordon Aug 06 '10 at 17:17
  • 1
    @Artefacto. If OP is asking just for a formual for total number, then it is off-topic! In either case, this question ought to be closed. –  Aug 06 '10 at 17:46
  • 2
    @Moron It's not really off-topic because he asks how he can calculate the number in a specific programming language (PHP), i.e. how to implement an algorithm that gives that number. It's difference between asking what's the integral of `f: x->x` between `a` and `b` and asking for an algorithm to determine said integral. – Artefacto Aug 06 '10 at 18:22

4 Answers4

9

This is not a combination but permutation. The algorithm is n! where n is the number of elements.

Why ?

Because you have 3 values to place on three places, so for the first place You have three option, for second only two (becuase You already palace first string) and at the end You have only one option.

3 * 2 * 1 = 3! = 6

But if You can repeate those chooses than you have permutation with repetition

So for first place You can chose from 3 string and for the second also and so one

3 * 3 * 3 = 3^3 = 27

n^k - where n is the number of strings and k - the number of "locations"

And the code algorithm look like this: 

function fact($n)
{
  if ($n == 0)
  {
    return 1;
  }
  else
  {
    return $n * fact($n - 1);
  }
}

This is a recursive example

Damian Leszczyński - Vash
  • 30,365
  • 9
  • 60
  • 95
  • The question does not say anything about distinctness, so not sure you can assume it. Of course, OP seems to have ignored queries regarding that, so... –  Aug 06 '10 at 17:45
1

If I remember correctly it's n! combinations.

so for 9 you would have

9*8*7*6*5*4*3*2 = 362880 combinations

corymathews
  • 12,289
  • 14
  • 57
  • 77
0

Look into permutations. O'Reilley has some good information on this via google. If I have some extra time, I will try and draft up an example for you.

Update

Here is some code, not 100% if it works correctly, but you should be able to modify it to your needs (the core code came from the O'Reilley site, fyi):

<?php
function pc_permute($items, $perms = array( )) {
    if (empty($items)) { 
        print join(' ', $perms) . "\n";
    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $newperms);
         }
    }
}

pc_permute(array('abc', 'xyz', 'def', 'hij'));
?>

EDIT

Just saw that he wanted the algorithm, either or the code should produce the results for other lurkers :) See other answers for the algorithm, which is n!

Jim
  • 18,673
  • 5
  • 49
  • 65
0

3*2*1= 6 factorial!

3 strings = 6 combinations..... 4 strings = 24 combinations.....etc

dewalla
  • 1,317
  • 8
  • 18
  • 42