Combinazioni, disposizioni e permutazioni in PHP

Question

Qual è il modo più efficace per generare tutte le combinazioni, disposizioni e permutazioni di un array in PHP?

Answer 1

Ecco il codice per ottenere tutte le permutazioni:

http://php.net/manual/en/function.shuffle .php # 90615

Con il codice per ottenere il set di alimentazione, permutazioni sono quelle di lunghezza massima, il set di alimentazione deve essere tutte le combinazioni. Non ho idea di quali disposizioni sono, quindi, se li si può spiegare, che avrebbe aiutato.

Answer 2

È possibile utilizzare questa classe: http://pear.php.net/package/Math_Combinatorics

e utilizzarlo come:

$combinatorics = new Math_Combinatorics;

$words_arr = array(
    'one'   => 'a',
    'two'   => 'b',
    'three' => 'c',
    'four'  => 'd',
    );

for ($i=count($words_arr)-1;$i>=1;$i--) {
    echo '<br><br>' . $i . ':<br>';
    $combinations_arr = $combinatorics->combinations($words_arr, $i);
    foreach ($combinations_arr as $combinations_arr_item) {
        echo implode(', ', $combinations_arr_item) . '<br>';
    }
}

Answer 3

Mi piacerebbe suggerire la mia soluzione di un CombinationsGenerator , che genera combinazioni di elementi di matrice.

è limitato a tutte le combinazioni sono di lunghezza, e non ripete qualsiasi elemento. Ma credo implementazione non sarebbe troppo difficile.

class CombinationsGenerator
{
    public function generate(array $list): \Generator
    {
        if (count($list) > 2) {
            for ($i = 0; $i < count($list); $i++) {
                $listCopy = $list;

                $entry = array_splice($listCopy, $i, 1);
                foreach ($this->generate($listCopy) as $combination) {
                    yield array_merge($entry, $combination);
                }
            }
        } elseif (count($list) > 0) {
            yield $list;

            if (count($list) > 1) {
                yield array_reverse($list);
            }
        }
    }
}

$generator = new \CombinationsGenerator();

foreach ($generator->generate(['A', 'B', 'C', 'D']) as $combination) {
    var_dump($combination);
}

E 'in stile PHP7, utilizza un \Generator perche' credono che ci sono buone ragioni per farlo.

Answer 4

/* Combinations */
function nCr($n, $r)
{
  if ($r > $n)
  {
    return NaN;
  }
  if (($n - $r) < $r)
  {
    return nCr($n, ($n - $r));
  }
  $return = 1;
  for ($i = 0; $i < $r; $i++)
  {
    $return *= ($n - $i) / ($i +1);
  }
  return $return;
}

/* Permutations */
function nPr($n, $r)
{
  if ($r > $n)
  {
    return NaN;
  }
  if ($r)
  {
    return $n * (nPr($n -1, $r -1));
  }
  else
  {
    return 1;
  }
}

Answer 5

ho dovuto modificare la risposta di @ hejdav in modo che include combinazioni parziali, in modo che eroghi pienamente tutti i risultati.

Ho navigato in Internet per questa soluzione e a partire da giugno 2019, credo che questa sia la risposta unica accessibile al pubblico (ovunque) che elenca veramente tutto possibile, non duplicare le possibilità.

class CombinationsGenerator
{
    /**
     * Taken from https://stackoverflow.com/a/39447347/430062.
     * 
     * @param array $list
     * @return \Generator
     */
    public function generate(array $list): \Generator
    {
        // Generate even partial combinations.
        $list = array_values($list);
        $listCount = count($list);
        for ($a = 0; $a < $listCount; ++$a) {
            yield [$list[$a]];
        }

        if ($listCount > 2) {
            for ($i = 0; $i < count($list); $i++) {
                $listCopy = $list;

                $entry = array_splice($listCopy, $i, 1);
                foreach ($this->generate($listCopy) as $combination) {
                    yield array_merge($entry, $combination);
                }
            }
        } elseif (count($list) > 0) {
            yield $list;

            if (count($list) > 1) {
                yield array_reverse($list);
            }
        }
    }
}