How to calculate the max. number of combinations possible?

php algorithm powerset
Ali picture Ali · Aug 6, 2010 · Viewed 28.7k times · Source

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?

Answer

Damian Leszczyński - Vash picture Damian Leszczyński - Vash · Aug 6, 2010

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

Related questions

List of Big-O for PHP functions

After using PHP for a while now, I've noticed that not all built-in PHP functions are as fast as expected. Consider these two possible implementations of a function that finds if a number is prime using a cached array of …

Read More
Algorithm to get the excel-like column name of a number

I'm working on a script that generate some Excel documents and I need to convert a number into its column name equivalent. For example: 1 => A 2 => B 27 => AA 28 => AB 14558 => UMX I have already written an algorithm …

Read More
PHP algorithm to generate all combinations of a specific size from a single set

I am trying to deduce an algorithm which generates all possible combinations of a specific size something like a function which accepts an array of chars and size as its parameter and return an array of combinations. Example: Let say …

Read More