Array permutation

0

Ladies and gentlemen, I would like to generate an anagram of possible combinations. Ex: "123456" would generate: 1234 2341 6531 5431 1243 1342 or 12 43 56 23 14 16, whether or not repeated,  and so on, I know how to get the number of combinations by factorial, but I do not know how to start the algorithm to generate the combinations, I've read quite a lot about combinatorial analysis, permutation, etc., but I still can not implement the algorithm. If anyone can only give me a light to start it would be GREAT! can be in pseudocode itself.

would pass a String and the size. Ex: where size would be ten hundred or thousands.

            class Permutacao
    {
      public $resul;
      private $cont;

      function __construct()
      {
        $this->resul = array();
      }

      public function permuta($array, $indice)
      {

        if($indice == count($array)){

          $this->cont++;
          array_push($this->resul, $this->arraytemp);
        }
        else{

          for ($i=0; $i < count($array); $i++) {
            $valida = false;

            for ($j=0; $j < $indice; $j++) {

              if($this->arraytemp[$j] == $array[$i]) $valida = true;
            }

            if (!$valida) {
              echo $indice." ";
              $this->arraytemp[$indice] = $array[$i];
              $this->permuta($array, $indice + 1);
            }
          }
        }
      }

    }
    echo "<pre>";
    $permuta = new Permutacao();
    $permuta->permuta(array(1,2,3,4), 0);
    print_r($permuta->resul);

UPDATE: Searching found this simpler way to implement, my biggest difficulty is to understand the algorithm, as I pass the "$ index = 0" it gets to 3 and then returns to 1 etc., and if the array with repeated values it returns nothing! 1,1,2,3, it would have to return

1,1,3

1,1,2

2,1,1 etc.

    
asked by anonymous 04.05.2016 / 18:15

2 answers

0

I have decided as follows:

private function get_permutations(array $arr = array(), $max_length = NULL){
                if(count($arr) == 1 || ($max_length !== NULL && $max_length <= 1)){
                    return array_values($arr);
                }

                $return_array = array();

                foreach($arr as $key => $val){

                    $temp_arr = $arr;
                    unset($temp_arr[$key]);
                    $temp = call_user_func('NomeDaClasse::'.__FUNCTION__, $temp_arr, $max_length !== NULL ? $max_length - 1 : NULL);
                    for($x = 0; $x < count($temp); $x++){
                        $temp[$x] = $val.$temp[$x];
                    }

                    $return_array = array_merge($return_array, $temp);
                }
                return $return_array;
            }
    
18.05.2016 / 15:44
-1

What about?

function sampling($chars, $size, $combinations = array()) {

# if it's the first iteration, the first set 
# of combinations is the same as the set of characters
if (empty($combinations)) {
    $combinations = $chars;
}

# we're done if we're at size 1
if ($size == 1) {
    return $combinations;
}

# initialise array to put new values in
$new_combinations = array();

# loop through existing combinations and character set to create strings
foreach ($combinations as $combination) {
    foreach ($chars as $char) {
        $new_combinations[] = $combination . $char;
    }
}

# call same function again for the next iteration
return sampling($chars, $size - 1, $new_combinations);

}

// example
$chars = array('a', 'b', 'c');
$output = sampling($chars, 2);
var_dump($output);
/*
array(9) {
  [0]=>
string(2) "aa"
  [1]=>
string(2) "ab"
 [2]=>
string(2) "ac"
 [3]=>
string(2) "ba"
[4]=>
string(2) "bb"
[5]=>
string(2) "bc"
[6]=>
string(2) "ca"
[7]=>
string(2) "cb"
[8]=>
string(2) "cc"
 }
*/

Other Examples in:

link

    
11.05.2016 / 19:48