Algorithm to mix any list of string (array)

Question

I need to find out what is the best algorithm to generate a list of all combinations of an array in php.

I want all possible combinations of elements in the original Array. The duplicate question wants only permutations. The difference is that I want to include, for example, "22", while "22" is not in an element in the Array of permutations of this array.

Here is an example :

Input : 1, 2, 3

Then the output will be

Output : 1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33, 111, 112, 113, 121, 123 ... until 333.

This question is different from Finding the subsets of an array in PHP, because this question wants all combinations of the array up to a certain length, not all permutations of the array up to a certain length. In particular, the linked question will for example never return "11" or "332" while this question wants to get these values as output as well.

yeah something like that. I need all any list of combined string from input until all of the string is already used. — Aldry Wijaya
– Aldry Wijaya, Commented Jul 27, 2014 at 12:55
To those who marked this question as duplicate - it is not. If you take the data set the OP has and pass it through the function in the duplicate question, you will NOT get the result the OP wants. Please do not jump the gun and close valid good questions just because its title/content might seem identical... — raidenace
– raidenace, Commented Jul 27, 2014 at 13:27
@AldryWijaya - whooo, you need to chill dude. There is no need for any name calling. I am sure those who marked this as duplicate are neither idiots nor did they have any bad intentions. — raidenace
– raidenace, Commented Jul 27, 2014 at 13:41
OP wants all possible combinations of elements in the original Array. The duplicate question wants only permutations. The difference is that OP wants to include, for example, "22", while "22" is not in an element in the Array of permutations of this array. — Sumurai8
– Sumurai8, Commented Jul 27, 2014 at 14:02

Sumurai8 · Accepted Answer · 2014-07-27 15:38:48Z

2

This problem can be solved by writing a recursive function, where you make an array with combinations up to a certain length based on the array of combinations of a shorter length. There is a special case for the length of 1. In that case, the array of combinations is the same as the original array. For all other lengths we calculate the combination array for strings up to 1 less than the current length, and add all the combinations of the current length.

function combi( $arr, $length ) {
  if( $length == 1 ) {
    return $arr;
  } else {
    $shorter = combi( $arr, $length - 1 );

    $new = Array();
    foreach( $shorter as $prefix ) {
      if( strlen( $prefix ) == $length - 1 ) {
        foreach( $arr as $suffix ) {
          $new[] = $prefix . $suffix;
        }
      }
    }

    return array_merge( $shorter, $new );
  }
}

$a = Array( "1", "2", "3" );

var_dump( combi( $a, count( $a ) ) );

This might not be the fastest approach, since you will be looping through an ever growing list, while most of the elements become irrelevant for generating the new strings. Besides that, if your input is anything else than an array of strings, you end up with a mixed array of strings and whatever the type of element is that you started of with.

This ideone shows this code working.

answered Jul 27, 2014 at 15:38

Sumurai8

20.8k11 gold badges70 silver badges103 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Aldry Wijaya Over a year ago

This is the best algorithm that I ever seen for this case.

Collectives™ on Stack Overflow

Algorithm to mix any list of string (array)

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related